Suppose and are relatively prime positive integers; show that

where is the Euler Totient function.

I can only see that because .

- Apr 28th 2012, 09:13 AMmath2011Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Suppose and are relatively prime positive integers; show that

where is the Euler Totient function.

I can only see that because . - Apr 28th 2012, 09:50 AMigniteRe: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
- Apr 28th 2012, 10:51 AMILikeSerenaRe: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Are you aware of the Chinese remainder theorem?

It fits kind of neatly, since it says there's a natural isomorphism between (mod mn) and the combination of (mod m) and (mod n). - Apr 29th 2012, 07:38 AMmath2011Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Thank you for your replies. However, I cannot figure out the rest of the solution from either of your hints. Could you please elaborate?

- Apr 29th 2012, 07:48 AMILikeSerenaRe: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
The Chinese remainder theorem says that the function

f: 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 . - Apr 30th 2012, 07:11 AMmath2011Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
I can solve it now. Thank you for your help.

From we have

.

Substitute into we get

.

which simplies to

.

Solve to get

,

.

Substitute back into first equation to get

.

Hence:

. - Apr 30th 2012, 07:47 AMILikeSerenaRe: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
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

- May 1st 2012, 01:46 PMmath2011Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
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. - May 1st 2012, 02:10 PMILikeSerenaRe: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
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. - May 2nd 2012, 06:30 AMmath2011Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Thank you for helping me with this problem. I really appreciate it.

- May 2nd 2012, 06:46 AMILikeSerenaRe: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
You're welcome. :)

- May 2nd 2012, 11:48 AMMooRe: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Hello,

Another way : http://mathhelpforum.com/number-theo...rithmetic.html