# How to prove that $\varphi\left(mn\right)=\varphi\left(m\right)\varphi\left(n\right)$ [duplicate]

Of course we are familiar with the notion that if $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$ ($p_{i}$ distinct primes; $k_{i}>0$), then $$\varphi\left(n\right)=n\left(1-1/p_{1}\right)\left(1-1/p_{2}\right)\cdots\left(1-1/p_{r}\right),$$ where $\varphi$ is the Euler totient function.

The goal is to prove this using the fact that $\varphi$ is multiplicative, that is, $$\varphi\left(mn\right)=\varphi\left(m\right)\varphi\left(n\right),$$ given that $m$ and $n$ are coprime.

Proving the former notion from the multiplicative property. But how do we prove the multiplicative property of $\varphi$ without using that notion?

-

## marked as duplicate by Martin Brandenburg, Davide Giraudo, Shuhao Cao, Andrey Rekalo, Vedran ŠegoSep 6 '13 at 19:17

What is the definition of $\varphi$ you are using? – Zev Chonoles Sep 6 '13 at 4:50
Note that $\phi(mn)=\phi(m)\phi(n)$ if and only if $m$ and $n$ are coprime. For example, $\phi(2)=1$, but $\phi(2\cdot2)=\phi(4)=2\ne1\cdot1=1$. That might make things easier. – William Ballinger Sep 6 '13 at 4:51
– Salech Alhasov Sep 6 '13 at 4:54
@AnthonyCarapetis, the goal this time is to prove it the other way around. So I need to prove the multiplicative property first. – vantonio1992 Sep 6 '13 at 5:05
@vantonio1992: oh sorry, I clearly skimmed too fast. – Anthony Carapetis Sep 6 '13 at 5:08

Let us start from the definition of Euler's Phi: $$\varphi(n)=|\{x\in [1,n-1] | \gcd(x,n)=1\}|,$$ i.e., $\varphi(n)$ is the number of positive integers at most equal to $n$ and prime to $n$.
Now, if $n$ and $m$ are coprime, we want to show that $\varphi(mn)=\varphi(n)\varphi(m)$. For this, let us denote: $$\Phi(n)=\{x\in [1,n-1] | \gcd(x,n)=1\}.$$ We just want to show that $\Phi(mn)$ has the same cardinality as $\Phi(m)\times\Phi(n)$. To do this, we can use the Chinese Remainder Theorem (since $m$ and $n$ are coprime) to construct a bijection between the two sets. This bijection is given by $x \rightarrow (x\bmod{m},x\bmod{n})$.
The only thing you need to check is that $x$ is prime to $mn$, if and only if, $x \mod {m}$ is prime to $m$ and $x \mod {n}$ is prime to $n$.
The group $(\mathbb{Z}/n\mathbb{Z})^*$ has order $\phi(n)$. Because $(\mathbb{Z}/nm\mathbb{Z})^*\simeq (\mathbb{Z}/n\mathbb{Z})^*\times (\mathbb{Z}/m\mathbb{Z})^*$ for coprime $n$ and $m$ it follows $\phi(nm)=\phi(n)\phi(m)$.