Does anyone know how to prove that(adsbygoogle = window.adsbygoogle || []).push({});

[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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# About Euler's totient function

**Physics Forums | Science Articles, Homework Help, Discussion**