Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euler phi function proof help

  1. Mar 8, 2010 #1
    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. jcsd
  3. Mar 8, 2010 #2
    Hint: Can you prove the result if d and n are both powers of the same prime p?

  4. Mar 9, 2010 #3
    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).
  5. Mar 9, 2010 #4
    Try factoring a [tex]p^{k-1}[/tex] 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 [tex]d\mid n[/tex]. That's part of the problem statement, not something to prove.
  6. Mar 9, 2010 #5
    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?
  7. Mar 9, 2010 #6
    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.

  8. Mar 10, 2010 #7
    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.
  9. Mar 10, 2010 #8
    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 [itex]\leq[/itex] 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.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook