how to prove $m^{\phi(n)}+n^{\phi(m)}\equiv 1 \pmod{mn}$ where m and n are relatively prime? 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?
 A: 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}?$$
A: 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$).
A: Since $\gcd(m, n) = 1$, so by Euler's theorem
$$m^{\phi(n)} \equiv 1 \mod n$$
and
$$n^{\phi(m)} \equiv 1 \mod m$$
But
$$m^{\phi(n)} \equiv 0 \mod m$$
and
$$n^{\phi(m)} \equiv 0 \mod n$$
Thus,
$$m^{\phi(n)} + n^{\phi(m)} \equiv (1 + 0) \mod n  \equiv 1 \mod n$$
and
$$m^{\phi(n)} + n^{\phi(m)} \equiv (1 + 0) \mod m  \equiv 1 \mod m$$
Hence,
$$m^{\phi(n)} + n^{\phi(m)} \equiv 1 \mod mn$$
A: 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.
