1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Euler's Phi function Number Theory
Loading...