# Thread: Using the chinese remainder theorem to prove a bijection

1. ## Using the chinese remainder theorem to prove a bijection

I have a problem where I have to prove that $\displaystyle \phi(nm)=\phi(m)\phi(n)$ where n and m are relatively prime and $\displaystyle \phi$ is Euler's totent.

I know that for the proof I must show that there is a bijection between $\displaystyle mn$ and $\displaystyle m \times n$ and I am having troubles doing that. Any help would be appreciated.

2. Originally Posted by chiefbutz
I have a problem where I have to prove that $\displaystyle \phi(nm)=\phi(m)\phi(n)$ where n and m are relatively prime and $\displaystyle \phi$ is Euler's totent.

I know that for the proof I must show that there is a bijection between $\displaystyle mn$ and $\displaystyle m \times n$ and I am having troubles doing that. Any help would be appreciated.

Bijection between $\displaystyle mn\,\,\,and\,\,\,m\times n$?? How? What are these things? You may, or may not, have a bijection between sets: what are the sets here?

Tonio

3. Originally Posted by tonio
What are these things?
Oops, sorry. I forgot to include that m and n are both Natural numbers.

You still haven't answered my question: if $\displaystyle m,n$ are natural numbers then $\displaystyle mn$ is again a natural number and, I suppose, $\displaystyle m\times n$ may be, again, a natural numer. You can, of course, define a very boring correspondence between the two sets containing each one of these numbers ( that'd be exactly the same set if both $\displaystyle mn\,,\,\,m\times n$ happen to be the very same natural number) so again I ask: what correspondence, between WHICH SETS, are you talking about??