# Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

• Apr 28th 2012, 09:13 AM
math2011
Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Suppose $m$ and $n$ are relatively prime positive integers; show that
$m^{\phi(n)} + n^{\phi(m)} \equiv 1 \pmod{mn}$
where $\phi$ is the Euler Totient function.

I can only see that $\phi(mn) = \phi(m) \phi(n)$ because $gcd(m,n) = 1$.
• Apr 28th 2012, 09:50 AM
ignite
Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Quote:

Originally Posted by math2011
Suppose $m$ and $n$ are relatively prime positive integers; show that
$m^{\phi(n)} + n^{\phi(m)} \equiv 1 \pmod{mn}$
where $\phi$ is the Euler Totient function.

I can only see that $\phi(mn) = \phi(m) \phi(n)$ because $gcd(m,n) = 1$.

Since $(m,n)=1$ ,we can find k and l such that $km+ln=1$ (Using Extended Euclid's Theorem)
Also using Euler's Theorem, $m^{\phi(n)} \equiv 1 \pmod{n}$ and $n^{\phi(m)} \equiv 1 \pmod{m}$
Can you use the above two facts and take it from there?If not,I will further elaborate.
• Apr 28th 2012, 10:51 AM
ILikeSerena
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).
• Apr 29th 2012, 07:38 AM
math2011
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?
• Apr 29th 2012, 07:48 AM
ILikeSerena
Re: 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 $\to$ Z/mZ x Z/nZ
given by
(x mod mn) $\mapsto$ (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 $x=m^{\phi(n)} + n^{\phi(m)}$.
• Apr 30th 2012, 07:11 AM
math2011
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.

$x=m^{\phi(n)} + n^{\phi(m)}$

From $x \equiv 1 \pmod{m}$ we have
$x = 1 + my$.
Substitute into $x \equiv 1 \pmod{n}$ we get
$1 + my \equiv 1 \pmod{n}$.
which simplies to
$my \equiv 0 \pmod{n}$.
Solve $y$ to get
$y \equiv 0 \pmod{n}$,
$y = nz$.
Substitute back into first equation to get
$x = 1 + mnz$.
Hence:
$x \equiv 1 \pmod{mn}$.
• Apr 30th 2012, 07:47 AM
ILikeSerena
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):
$x \mod m \equiv m^{\phi(n)} + n^{\phi(m)} \mod m \equiv 1 \mod m$
$x \mod n \equiv m^{\phi(n)} + n^{\phi(m)} \mod n \equiv 1 \mod n$

Therefore:
$f: (x \mod {mn}) \mapsto (1 \mod m, 1 \mod n)$

Since we also have from the definition of f:
$f: (1 \mod {mn}) \mapsto (1 \mod m, 1 \mod n)$

and since f is bijective (it's an isomorphism), it follows that
$x \mod {mn} \equiv 1 \mod {mn}$

$\square$
• May 1st 2012, 01:46 PM
math2011
Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
Did you mean that the definition of $f$ is $f : (x \pmod{mn}) \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.
• May 1st 2012, 02:10 PM
ILikeSerena
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 $f$ is $f : (x \pmod{mn}) \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.

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.
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 AM
math2011
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.
• May 2nd 2012, 06:46 AM
ILikeSerena
Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)
You're welcome. :)
• May 2nd 2012, 11:48 AM
Moo
Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)