# Thread: euler's theorem 2nd question

1. ## euler's theorem 2nd question

Hi,

i need to verify if my proof for this particular problem is correct.

The theorem:

Let m, n be relatively prime positive integers. Prove that m^Φ(n) + n^Φ(m) Ξ 0mod mn
Proof:
nx = m^Φ(n) – 1
my = n^Φ(m) – 1
Let xy = z
nm(z) = (m^Φ(n) – 1)( n^Φ(m) – 1)
nm(z) = m^Φ(n) n^Φ(m) - m^Φ(n) - n^Φ(m) + 1
m^Φ(n) + n^Φ(m) - m^Φ(n) n^Φ(m) – 1 = (nm)(-z)
m^Φ(n) n^Φ(m) Ξ 0mod (mn)
Therefore,
m^Φ(n) + n^Φ(m) Ξ 1mod (mn)

2. Originally Posted by htata123
Hi,

i need to verify if my proof for this particular problem is correct.

The theorem:

Let m, n be relatively prime positive integers. Prove that m^Φ(n) + n^Φ(m) Ξ 1mod mn
Proof:
nx = m^Φ(n) – 1
my = n^Φ(m) – 1
Let xy = z
nm(z) = (m^Φ(n) – 1)( n^Φ(m) – 1)
nm(z) = m^Φ(n) n^Φ(m) - m^Φ(n) - n^Φ(m) + 1
m^Φ(n) + n^Φ(m) - m^Φ(n) n^Φ(m) – 1 = (nm)(-z)
m^Φ(n) n^Φ(m) -1 Ξ 0mod (mn)
Therefore,
m^Φ(n) + n^Φ(m) Ξ 1mod (mn)
Be careful, the correct statement is, if $\text{gcd}(m,n)=1$ then $m^{\phi(n)}+n^{\phi(m)}\equiv{1}(\bmod.n\cdot m)$

But, besides that, your proof is correct . See in the quote above.