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

Suppose $\displaystyle m$ and $\displaystyle n$ are relatively prime positive integers; show that

$\displaystyle m^{\phi(n)} + n^{\phi(m)} \equiv 1 \pmod{mn}$

where $\displaystyle \phi$ is the Euler Totient function.

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

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

Quote:

Originally Posted by

**math2011** Suppose $\displaystyle m$ and $\displaystyle n$ are relatively prime positive integers; show that

$\displaystyle m^{\phi(n)} + n^{\phi(m)} \equiv 1 \pmod{mn}$

where $\displaystyle \phi$ is the Euler Totient function.

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

Since $\displaystyle (m,n)=1$ ,we can find k and l such that $\displaystyle km+ln=1 $ (Using Extended Euclid's Theorem)

Also using Euler's Theorem,$\displaystyle m^{\phi(n)} \equiv 1 \pmod{n} $ and $\displaystyle 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.

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 $\displaystyle \to$ Z/mZ x Z/nZ

given by(x mod mn) $\displaystyle \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 $\displaystyle x=m^{\phi(n)} + 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.

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

From $\displaystyle x \equiv 1 \pmod{m}$ we have

$\displaystyle x = 1 + my$.

Substitute into $\displaystyle x \equiv 1 \pmod{n}$ we get

$\displaystyle 1 + my \equiv 1 \pmod{n}$.

which simplies to

$\displaystyle my \equiv 0 \pmod{n}$.

Solve $\displaystyle y$ to get

$\displaystyle y \equiv 0 \pmod{n}$,

$\displaystyle y = nz$.

Substitute back into first equation to get

$\displaystyle x = 1 + mnz$.

Hence:

$\displaystyle x \equiv 1 \pmod{mn}$.

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):$\displaystyle x \mod m \equiv m^{\phi(n)} + n^{\phi(m)} \mod m \equiv 1 \mod m$

$\displaystyle x \mod n \equiv m^{\phi(n)} + n^{\phi(m)} \mod n \equiv 1 \mod n$

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

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

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

$\displaystyle \square$

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

Did you mean that the definition of $\displaystyle f$ is $\displaystyle 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.

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 $\displaystyle f$ is $\displaystyle 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.

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)