Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Getting phi of a large number

  1. Apr 29, 2009 #1
    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?
     
  2. jcsd
  3. Apr 29, 2009 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    phi(p^a) = (p-1)(p^(a-1)) for p prime
     
  4. Apr 30, 2009 #3
    also since phi is multiplicative phi(a*b) = phi(a)*phi(b) when gcd(a,b)=1
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Getting phi of a large number
Loading...