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.

  • 4
    $\begingroup$ 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})^*.$$ $\endgroup$ – Jack D'Aurizio Dec 31 '16 at 13:11

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.