# Understanding Multiplicative of $\phi(mn)$

The function $\phi$ is a multiplicative function.

Proof I read is too big so I didn't add it, just click here for proof.

My problem is with the last paragraph, i.e. from,

....The implication is that the $rth$ column contains as many integers that are relatively prime to $n$ as does the set $\{0,1,2 \cdots , n-1\}$. namely, $\phi(n)$ integers.

Set mention contain $n$ integers, so how all of them is relatively prime to $n$, why can't we have something like $ab=n$ (i.e. factor of $n$) among set mentioned, it is not mention anywhere that $n$ is prime just $m,n$ are relatively prime. What I'm interpreting wrong, please help.

• A short alternative: assuming $\gcd(m,n)=1$ and recalling that $\phi(n)=\left|\mathbb{Z}/(n\mathbb{Z})^*\right|$, the identity $\phi(mn)=\phi(m)\phi(n)$ holds as a consequence of the Chinese remainder theorem, since: $$\mathbb{Z}/(mn\mathbb{Z})^*\simeq \mathbb{Z}/(m\mathbb{Z})^*\times \mathbb{Z}/(n\mathbb{Z})^*.$$ – Jack D'Aurizio Dec 31 '16 at 13:11

## 1 Answer

Not all of them are relatively prime to $n$.

What the author shows is that those $n$ numbers exhaust all the $n$ classes modulo $n$, so that there must be exactly $\phi(n)$ of them that are coprime to $n$.

I offer you a different proof of the identity $\phi(mn)=\phi(m)\phi(n)$ for $(m,n)=1$ which is based on the notion of ring and those pertaining it.

In the ring $\Bbb Z_k$ of classes modulo $k$, the classes of numbers coprime to $k$ are the invertible elements (those $x$ for which there exists a $y$ such that $xy=\bar1$).

Thus $\phi(k)$ is the numbers of elements in the group $\Bbb Z_k^\times$ of invertible elements in $\Bbb Z_k$.

When $k=mn$ with $(m,n)=1$ the Chinese Remainder Theorem applies to give an identification $$\Bbb Z_k=\Bbb Z_m\times\Bbb Z_n,$$ from which $$\Bbb Z_k^\times=\Bbb Z_m^\times\times\Bbb Z_n^\times$$ follows readily. The identity $\phi(mn)=\phi(m)\phi(n)$ follows from the last displayed formula simply counting elements in the left hand side and in the right hand side.