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

About Euler's totient function

  1. Aug 13, 2005 #1
    Does anyone know how to prove that

    [tex]\phi(mn) = \phi(m)\phi(n) \frac{d}{\phi(d)}[/tex]

    where [tex]m, n \in \mathbb{N}[/tex] and [tex]d = \gcd({m, n})[/tex], without resorting to considering the prime factorizations of m and n? (It's perfectly doable that way, but not particularly elegant).

    It can, supposedly, be done by noting that it holds for coprime m and n (a rather classical result), but I don't see how the rest follows... If m, n and d are as in the previous paragraph, then

    [tex]\phi(\frac{mn}{d^2}) = \phi(\frac{m}{d}) \cdot \phi(\frac{n}{d})[/tex]

    since m/d and n/d are coprime. At this point, one (at least I) feels like multiplying both sides by [tex]\phi(d^2)[/tex], but it doesn't do us much good since mn/d^2 and d^2 might not be coprime (take m = 4, n = 2). Any ideas?
  2. jcsd
  3. Aug 14, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    i'd suggest just making a study of phi(a/b) where a divides b.
  4. Feb 21, 2010 #3
    Let m = f1^a1 * f2^a2 ... fk^ak where each fk is a prime (basically the prime factorizatin of m)

    Let n = p1^a1 * p2^a2 ... pk^ak where each pk is a prime. The k or each ak has no connection to the prime factorization of n. I'm just making a general prime factorization of numbers.

    Let d equal the GCD of m and n, prime factored into z1^a1 * z2^a2 ... zk^ak.

    phi(mn) = [mn (1-1/f1)(1-1/f2)...(1-1/fk)(1-1/p1)(1-1/p2)...(1-1/pk)] / [(1-1/z1)(1-1/z2)...(1-1/zk)]

    The denominator is there since the GCD contains all prime factors of m and n that are shared and need to be eliminated. The denominator is equal to phi(d)/d.

    Simplifying this we get

    phi(mn) = [phi(m)phi(n)] / [phi(d)/d]
    = phi(m) phi(n) d / phi(d).

    You're welcome.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook