# Using the chinese remainder theorem to prove a bijection

• Feb 5th 2010, 06:20 AM
chiefbutz
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.
• Feb 5th 2010, 09:28 AM
tonio
Quote:

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
• Feb 5th 2010, 09:36 AM
chiefbutz
Quote:

Originally Posted by tonio
What are these things?

Oops, sorry. I forgot to include that m and n are both Natural numbers.
• Feb 7th 2010, 11:10 AM
chiefbutz
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??