Euler phi function

1. Mar 8, 2010

tarheelborn

I am having trouble with this proof: show that if d|n then phi(d)|phi(n). I know that if d|n, then ad=n and that phi(ad)=(a,d)*phi(a)&phi(d)/phi((a,d)), but I can't seem to get anywhere with this info. Thanks for your help.

2. Mar 8, 2010

Petek

Hint: Can you prove the result if d and n are both powers of the same prime p?

Petek

3. Mar 9, 2010

tarheelborn

I know that if p is prime, then phi(p^k)=p^k-p^(k-1). So if I let d=p^k and n=p^l, I am still not sure how to work this around so that d|n and phi(d)|phi(n).

4. Mar 9, 2010

Tinyboss

Try factoring a $$p^{k-1}$$ out of that expression, then see if it's easier to see Petek's result.

Edit: I may just be reading you wrong, but it seems like you're trying to show $$d\mid n$$. That's part of the problem statement, not something to prove.

5. Mar 9, 2010

tarheelborn

Right. Good point... So if d|n and d=p1^a1p2^a2...pk^ak, n=p1^b1p2^b2...pk^bk, then phi(d)=p1p2...pk*(p^k-1) and phi(n)=p1p2...pk*(p^k-1), so p1p2...pk|phi(n). Would that work?

6. Mar 9, 2010

Petek

Your work isn't correct, but you're getting closer. Look at your expressions for phi(d) and phi(n). They're the same, which can't be right. Also, both expressions contain a "p", which wasn't used before.

Let's go back to my hint and just consider the case in which d and n are both powers of the same prime p. So we have that d = p^k and n = p^l. The assumption is that d|n. What can you then say about the relation between k and l?

Assuming that you got that part, now write phi(p^k) = p^k - p^(k-1) = p^(k-1)(p - 1) and a similar expression for phi(p^l). Can you now see that phi(d)|phi(n)?

Finally, use the fact that phi is a multiplicative function (do you know what this means?) to derive the result when d|n and d and n could be any positive integers.

Petek

7. Mar 10, 2010

tarheelborn

OK... Thank you for your kindly-worded candor.

Now, if d|n and we let d and n be powers of the same prime p, then d=p^k and n+p^l implies k|l if k< l. Then phi(d)=phi(p^k)=p^k-p^(k-1)=p^(k-1)(p-1) and phi(n)=phi(p^l)=p^l-p^(l-1)=p^(l-1)(p-1).

I am not sure where to go with the multiplicative part. I know that phi is multiplicative, meaning that phi(dn)=phi(d)*phi(n) if (d,n)=1 which it clearly does in this case, but I'm not making a connection here. It seems to me if I got the k|l part right, then phi(d) | phi(n) follows from that, but that doesn't seem to be enough. Thanks so much for your help.

8. Mar 10, 2010

Petek

If d = p^k divides n = p^l, then we can't conclude that k|l. For example, consider d = p^2 and n = p^3. However, you can conclude that k $\leq$ l. Now argue that phi(d) divides phi(n).

To use the fact that phi is multiplicative, write both d and n as the product of prime powers (using unique factorization). Now argue that phi(d) divides phi(n) by using what was proved in the preceding. For example, suppose that d = p^a q^b and n = p^c q^d, where p and q are distinct primes and d|n. Can you prove that phi(d) divides phi(n) here? Can you extend this argument to the general case?

Hope this helps.

Petek