# Homework Help: 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?