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 and division

  1. Mar 16, 2008 #1


    User Avatar

    Prove that if d divides n then phi(d) divides phi(n).
  2. jcsd
  3. Mar 16, 2008 #2
    Have you already proved the totient function is multiplicative?
  4. Mar 16, 2008 #3


    User Avatar

    yes, rodigee
  5. Mar 16, 2008 #4
    Then you're home free!

    [tex]d\left| n[/tex] means [tex]n = d*a[/tex] for some integer a. So, bearing in mind the totient function is multiplicative, what can you now say about [tex]\varphi (n)[/tex] ?
  6. Mar 17, 2008 #5


    User Avatar

    Yes rodigee, this is the way I've solved it, thanks.
  7. Oct 25, 2009 #6
    There is a crucial problem with your tactic, namely that the Euler phi function is ONLY multiplicative for co-primes.

    Consider that 2|8. 8=2*4, but 2 and 4 are not co-prime. Phi(2)=1 and Phi(4)=2. Phi(2)*Phi(4)=2. But Phi(8)=4!

    Multiplicativity of Phi alone is sufficient to prove the property when n=da, d and a co-prime. But not in general. Anyone have insights on how to do this?
    Last edited: Oct 25, 2009
  8. Oct 25, 2009 #7
    Couldn't you make use of prime decomposition?

    Take the prime decomposition of n, and let it's totient function be the product of the totient's of it's primes. Do the same for d, and since d|n, the prime decomposition of d is imbedded in n, so for n=d*a, a is just what's left to complete d so that it equals a ... or something like that :)
  9. Oct 25, 2009 #8
    Here's how I did it.

    Prove that if m | n, then phi(m) | phi(n)
    Note that from phi(p^a) = (p^(a-1))(p-1) for some prime p, it follows that phi(p^a) | phi(p^b)
    for a | b.
    This generalizes to phi(k^a) | phi(k^b) for composite k, since phi is multiplicative.
    Since m | n, there exists some q in Z such that mq = n.
    Thus, there exists some c, r in Z such that (m^c)r = n where gcd(m, r) = 1 and c ≥ 1.
    Hence phi(m) | phi(m^c) and phi(m^c) | phi(m^c)phi(r).
    We have phi(m^c)phi(r) = phi(mc^r) = phi(n) since gcd(m, r) = 1 and phi multiplicative.
    Thus phi(m) | phi(n).

  10. Nov 5, 2009 #9
    Here is an alternative, perhaps more in the spirit of "consider the prime factorization of...".

    Let P(n) be the set of (distinct) primes in the factorization of n.
    If S is any set of primes {p1, p2, p3, ...}, let F(S) = (1-1/p1) (1-1/p2) (1-1/p3) ...

    In this notation, we know that phi(n) = n F(P(n)).

    Now it is time for a
    If S is a subset of P(n), then n F(S) is an integer.
    Proof: each factor in F(S) is of the form
    (1 - 1/p) = (p-1)/p
    Each distinct prime in S exists (at least once) in the factorization of n, cancelling one denominator in F(S) and leaving
    n F(S) = k (p1-1) (p2-1) (p3-1) ..., where S = {p1, p2, p3, ...} and the integer k = n/(p1 p2 p3 ...). The result follows.

    Now for the main dish: if m|n, let n = qm. We know that P(n) = P(qm) = P(q) U P(m).

    Let D be the set difference P(n) - P(m). We know that D is a subset of P(q).

    Therefore, phi(n) = n F(P(n)) = qm F(P(m)) F(D) = phi(m) q F(D).

    Since, by the Lemma, q F(D) is an integer, the conclusion follows.
  11. Feb 21, 2010 #10
    I'm making a quick comment

    Euler's totient function IS multiplicative. Someone said it's only for coprimes but there's a general form where the 2 numbers dont have to be coprime

    phi(mn) = phi(m)phi(n) * d/phi(d)

    where d is the GCD of m and n.
  12. Apr 19, 2012 #11
    Learn what mulitplicative means.
  13. Apr 19, 2012 #12


    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    This thread is 4 years old...
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Euler, phi and division
  1. Euler phi function (Replies: 5)

  2. Euler's phi function (Replies: 3)

  3. Euler phi function (Replies: 7)