## About Euler's totient function

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?
 PhysOrg.com science news on PhysOrg.com >> Leading 3-D printer firms to merge in $403M deal (Update)>> LA to give every student an iPad;$30M order>> CIA faulted for choosing Amazon over IBM on cloud contract
 Recognitions: Homework Help Science Advisor i'd suggest just making a study of phi(a/b) where a divides b.
 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.

 Tags totient

 Similar discussions for: About Euler's totient function Thread Forum Replies Calculus & Beyond Homework 10 Calculus & Beyond Homework 8 Linear & Abstract Algebra 1 Linear & Abstract Algebra 3