How can Euler's totient function be proved without using prime factorizations?

[Muzza]

Does anyone know how to prove that

$$\phi(mn) = \phi(m)\phi(n) \frac{d}{\phi(d)}$$

where $$m, n \in \mathbb{N}$$ and $$d = \gcd({m, n})$$, 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

$$\phi(\frac{mn}{d^2}) = \phi(\frac{m}{d}) \cdot \phi(\frac{n}{d})$$

since m/d and n/d are coprime. At this point, one (at least I) feels like multiplying both sides by $$\phi(d^2)$$, 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.