how to prove $m^{\phi(n)}+n^{\phi(m)}\equiv 1 \pmod{mn}$ where m and n are relatively prime?

Question

I do not know how to prove this question: $m^{\phi(n)}+n^{\phi(m)}\equiv 1 \pmod {mn}$ where $m$ and $n$ are relatively prime.

Can anyone help?

Answer 1

Hint: Can you prove:

$$m^{\phi(n)}+n^{\phi(m)}\equiv 1 \pmod {m}$$ and $$m^{\phi(n)}+n^{\phi(m)}\equiv 1 \pmod {n}?$$

Answer 2

By the Chinese Remainder Theorem, it suffices to prove that $$ m^{\phi(n)}+n^{\phi(m)}\equiv 1\mod{m},\qquad m^{\phi(n)}+n^{\phi(m)}\equiv 1\mod{n}. $$ But now this follows trivially, since $m^{\phi(n)}\equiv 1\mod{n}$ by Euler's Theorem (and likewise for $n$).

Answer 3

Hint $\ $ It is simply $\,\overbrace{(0,1)}^{\large m^{\large \phi(n)}}+ \overbrace{(1,0)}^{\large n^{\large \phi(m)}}\, =\, \overbrace{(1,1)}^{\large1}\ $ in $\ \Bbb Z/m \times \Bbb Z/n\overset{\rm CRT}\cong \Bbb Z/mn\ $ using Euler's Theorem.