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

Homework Help: Euler's Phi function Number Theory

  1. Sep 27, 2006 #1
    Ok the question is as follows:

    Given gcd(a,b)=d, show that Phi(ab)= (d*phi(a)phi(b))/phi(d)



    I know that if gcd(a,b)=1 then phi(ab)=Phi(a)phi(b) but im just stuck here. Any help would be greatly appreciated!
     
  2. jcsd
  3. Sep 27, 2006 #2

    StatusX

    User Avatar
    Homework Helper

    phi(n)=n(1-1/p1)...(1-1/pk), where pi are the distinct prime factors of n. Can you prove and then use this?
     
  4. Sep 27, 2006 #3
    Status X...that was another part of the question. They gave us the fact that

    phi(a)=a*PROD(1-1/p) for the distinct prime factors. Can one say:

    phi(ab)=ab*PROD(1-1/p) for the distinct prime factors of a and b? I don't know if this would help me or not
     
  5. Sep 27, 2006 #4

    StatusX

    User Avatar
    Homework Helper

    The product is over the distinct prime factors of ab. But a and b may share some prime factors (which, remember, will then be in d).
     
  6. Sep 27, 2006 #5
    I dont exactly understand what you mean by "which, remember will be in d"

    d is the gcd of a and b
     
  7. Sep 27, 2006 #6

    StatusX

    User Avatar
    Homework Helper

    Try writing out the identity in the first post using the prime factor expansion of phi(n). Which prime factors does d have?
     
  8. Sep 27, 2006 #7
    ok i wrote out the prime factorization of the equation in the first post.

    The d on the numerator cancels the d in the denominator. I'm not very good thinking about primes and factors (even though im taking Number theory haha).

    Which prime factors does d have?
    Does d have the same prime factors as a and b since it is the gcd of a and b?
     
  9. Sep 27, 2006 #8

    StatusX

    User Avatar
    Homework Helper

    Think about the definition of d. If the abstractness is confusing you, try plugging in some values for a and b.
     
  10. Nov 3, 2009 #9
    I have a question about this same problem. The prime factors of d are 1 and d. So since D is the only distinct prime factor of a and b, this means phi(n)=n*(1-1/d) right? But then, How do I go from here?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook