19
$\begingroup$

The third formula on the wikipedia page for the Totient function states that $\varphi (mn) = \varphi (m) \varphi (n) \cdot \dfrac{d}{\varphi (d)} $ where $d = \gcd(m,n)$.

How is this claim justified?

Would we have to use the Chinese Remainder Theorem, as they suggest for proving that $\varphi$ is multiplicative?

  • 0
    See also http://math.stackexchange.com/questions/119911/proving-formula-involving-eulers-totient-function. (Thanks @Dane!)2012-03-14

3 Answers 3

28

You can write $\varphi(n) = n \prod\limits_{p \mid n} \left( 1 - \frac 1p \right)$. Using this identity, we have

$$ \varphi(mn) = mn \prod_{p \mid mn} \left( 1 - \frac 1p \right) = mn \frac{\prod_{p \mid m} \left( 1 - \frac 1p \right) \prod_{p \mid n} \left( 1 - \frac 1p \right)}{\prod_{p \mid d} \left( 1 - \frac 1p \right)} = \varphi(m)\varphi(n) \frac{d}{\varphi(d)} $$

  • 0
    This should probably be restricted to prime $p$.2014-04-25
5

Hint $\ $ A multiplicative function $\rm\:f(n)\:$ satisfies said identity if for all primes $\rm\:p\:$

$\rm\ j\le k\ \Rightarrow\ \ f(p^{j+k}) = \frac{f(p^j)\: f(p^k)\: p^j}{f(p^j)}\ =\ p^j f(p^k)$

Indeed we have $\rm\ \ \phi(p^{j+k})\ =\ p^{j+k}-p^{j+k-1}\ =\ p^j (p^k-p^{k-1})\ =\ p^j \phi(p^k)$

  • 0
    Thanks, $B$ill. I'll try to wrap my head around that. It seems useful.2012-02-29