Using the chinese remainder theorem to prove a bijection

Printable View

• 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 $\phi(nm)=\phi(m)\phi(n)$ where n and m are relatively prime and $\phi$ is Euler's totent.

I know that for the proof I must show that there is a bijection between $mn$ and $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 $\phi(nm)=\phi(m)\phi(n)$ where n and m are relatively prime and $\phi$ is Euler's totent.

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

Bijection between $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
Can't anyone help? Please?
• Feb 7th 2010, 11:59 AM
tonio
Quote:

Originally Posted by chiefbutz
Oops, sorry. I forgot to include that m and n are both Natural numbers.

You still haven't answered my question: if $m,n$ are natural numbers then $mn$ is again a natural number and, I suppose, $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 $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??

Mathematics is not just trying to solve problems: one must also strive to understand what one's talking about, the symbols and etc.

Tonio