# euler's theorem 2nd question

• Mar 2nd 2009, 08:56 PM
htata123
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)
• Mar 3rd 2009, 04:18 AM
PaulRS
Quote:

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.