Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Suppose 
and 
are relatively prime positive integers; show that
} + n^{\phi(m)} \equiv 1 \pmod{mn})
where 
is the Euler Totient function.
I can only see that  = \phi(m) \phi(n))
because  = 1)
.
Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Quote:
Originally Posted by
math2011 
Suppose
and
are relatively prime positive integers; show that
where
is the Euler Totient function.
I can only see that
because
.
Since =1)
,we can find k and l such that 
(Using Extended Euclid's Theorem)
Also using Euler's Theorem, } \equiv 1 \pmod{n} )
and } \equiv 1 \pmod{m} )
Can you use the above two facts and take it from there?If not,I will further elaborate.
Re: 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).
Re: 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?
Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
The Chinese remainder theorem says that the functionf: Z/mnZ
Z/mZ x Z/nZ
(x mod mn)
(x mod m, x mod n)
Please give some feedback on what you know or do not know, or perhaps what you've tried.
Pick } + n^{\phi(m)})
.
Re: 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:
.
Re: 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
Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Did you mean that the definition of 
is  \to (x \pmod{m}, x \pmod{n}))
? 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.
Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Quote:
Originally Posted by
math2011 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.
Re: 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.
Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
