About Euler's totient function

Muzza

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?

matt grime

i'd suggest just making a study of phi(a/b) where a divides b.

squelchy451

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.