- #1

- 695

- 0

## Main Question or Discussion Point

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?

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