Euler's Phi function Number Theory

1. Sep 27, 2006

Ch1ronTL34

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. Sep 27, 2006

StatusX

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?

3. Sep 27, 2006

Ch1ronTL34

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

4. Sep 27, 2006

StatusX

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).

5. Sep 27, 2006

Ch1ronTL34

I dont exactly understand what you mean by "which, remember will be in d"

d is the gcd of a and b

6. Sep 27, 2006

StatusX

Try writing out the identity in the first post using the prime factor expansion of phi(n). Which prime factors does d have?

7. Sep 27, 2006

Ch1ronTL34

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?

8. Sep 27, 2006

StatusX

Think about the definition of d. If the abstractness is confusing you, try plugging in some values for a and b.

9. Nov 3, 2009

viviane363

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?