26
$\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?

$\endgroup$
3
  • 2
    $\begingroup$ There might be a direct proof, but of course if you show that $\varphi$ is multiplicative (using the Chinese Remainder Theorem) and that $\varphi(p^a) = p^a - p^{a-1}$, then you get your result. $\endgroup$
    – Joel Cohen
    Commented Feb 29, 2012 at 15:18
  • 3
    $\begingroup$ It'd be nice to relate this formula with the natural mapping $U_{mn}\to U_m \times U_n$ by proving that the kernel has size $d$ and the image has index $\phi(d)$. $\endgroup$
    – lhf
    Commented Mar 13, 2012 at 2:22
  • 1
    $\begingroup$ See also math.stackexchange.com/questions/119911/…. (Thanks @Dane!) $\endgroup$
    – lhf
    Commented Mar 14, 2012 at 12:07

3 Answers 3

38
$\begingroup$

You can write $\varphi(n)$ as a product $\varphi(n) = n \prod\limits_{p \mid n} \left( 1 - \frac 1p \right)$ over primes. 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)} $$

$\endgroup$
1
  • $\begingroup$ This should probably be restricted to prime $p$. $\endgroup$
    – G. Bach
    Commented Apr 25, 2014 at 19:55
9
$\begingroup$

Just as an additional note to the identity provided by @Cardboard Box.

$$ \prod_{p|mn} \left(1 - \dfrac{1}{p}\right) = \frac{\prod\limits_{p|m} \left(1 - \dfrac{1}{p}\right) \prod\limits_{p|n} \left(1 - \dfrac{1}{p}\right)}{\prod\limits_{p|d} \left(1 - \dfrac{1}{p}\right)} $$

Why does this work? Consider the prime factorization of $m,n$, and that we are multiplying all $p$ such that $p|mn$. But, on first sight, this is the same as multiplying all $p$ such that $p|n$ together with all $p$ such that $p|m$. But what if $m$ and $n$ share a prime factor?

This means that we will multiply that prime factor (call it $p_c$) twice, although of course it can only appear once in the prime factorization of $mn$, albeit with a greater power associated.

Thus, we need to account for this shared factor, or even shared factors in case there is more than 1 shared prime factor.

To do this, divide the whole thing by prime factors of the $gcd(m,n)$. Thus, we will be "removing" the factors which we multiplied twice.

Furthermore, to go from $$ mn \frac{\prod\limits_{p|m} \left(1 - \dfrac{1}{p}\right) \prod\limits_{p|n} \left(1 - \dfrac{1}{p}\right)}{\prod\limits_{p|d} \left(1 - \dfrac{1}{p}\right)} = \phi(m) \phi(n) \dfrac{d}{\phi(d)} $$

consider multiplying the left side by $\dfrac{d}{d}$. Thus you can group together the $d$ with $\prod\limits_{p|d} \left(1 - \dfrac{1}{p}\right)$ in the denominator to get $\phi(d)$.

Hope this makes it easier to follow the top answer.

$\endgroup$
8
$\begingroup$

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)$

$\endgroup$
1
  • $\begingroup$ Thanks, Bill. I'll try to wrap my head around that. It seems useful. $\endgroup$ Commented Feb 29, 2012 at 16:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .