Suppose and are relatively prime positive integers; show that
where is the Euler Totient function.
I can only see that because .
The Chinese remainder theorem says that the functionf: Z/mnZ Z/mZ x Z/nZgiven by(x mod mn) (x mod m, x mod n)is an isomorphism if m and n are relatively prime.
Please give some feedback on what you know or do not know, or perhaps what you've tried.
Pick .
Hmm, I can't follow what you did there (without making a great effort).
I'll just show my proof (using the definition of f from my previous post):
Therefore:
Since we also have from the definition of f:
and since f is bijective (it's an isomorphism), it follows that
Did you mean that the definition of is ? Why is this a bijective function? Do we need to prove that it is a bijective function?
P.S. The method I used is one of the methods for solving simultaneous congruences.
Yes it is.
The function f is bijective because the Chinese remainder theorem says so.
Do we need to prove it?
I don't know.
That depends on your context.
You have not set any boundaries on what you can or cannot use.
The Chinese remainder theorem also says exactly how you can solve a simultaneous set of congruences.
See for instance this link for a simple formula.
Hello,
Another way : modular arithmetic