Getting phi of a large number

  • Thread starter hanelliot
  • Start date
  • #1
18
0

Main Question or Discussion Point

phi(20^100)
= phi(4^100 * 5^100)
= phi(2^200 * 5^100)
= (2^200 - 2^199)(5^100 - 5^99)
= 2^199(2-1) * 5^99(5-1)
= 2^199 * 5^99 * 4
= 2^201 * 5^99.

I don't understand line 4-7. Can anyone explain?
 

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,820
0
phi(p^a) = (p-1)(p^(a-1)) for p prime
 
  • #3
107
1
also since phi is multiplicative phi(a*b) = phi(a)*phi(b) when gcd(a,b)=1
 

Related Threads for: Getting phi of a large number

  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
2
Views
4K
Replies
1
Views
5K
  • Last Post
Replies
3
Views
9K
Replies
12
Views
8K
  • Last Post
Replies
1
Views
3K
Replies
13
Views
15K
  • Last Post
Replies
6
Views
2K
Top