Need Euler phi function proof help

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

 

[Petek]

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

Petek

 

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

 

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

 

[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?

 

[Petek]

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?

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

 

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

 

[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