Let $\gcd (m, n) = 1$. Prove that
$$ m^{\phi(n)} + n^{\phi(m)} \equiv 1 \pmod {mn} $$
Hint: Use the Chinese remainder theorem.
Since $\gcd (m, n) = 1$, Euler's Theorem gives us
$$ m^{\phi(n)} \equiv 1 \pmod n $$
$$ n^{\phi(m)} \equiv 1 \pmod m $$
This means, for some integers $j,k$,
$$ m^{\phi(n)} - 1 = j n $$
$$ n^{\phi(m)} - 1 = k m $$
Multiplying gives us
$$ \begin{align} jk(mn) & = (m^{\phi(n)} -1 ) (n^{\phi(m)} - 1) \\ \\ & = m^{\phi(n)}n^{\phi(m)} - n^{\phi(m)} - m^{\phi(n)} + 1 \\ \\ mn(jk - m^{\phi(n)-1}n^{\phi(m)-1}) -1 & = - n^{\phi(m)} - m^{\phi(n)} \end{align} $$
That is
$$ n^{\phi(m)} + m^{\phi(n)} = 1 + mn( m^{\phi(n)-1}n^{\phi(m)-1} - jk)$$
Which is equivalent to
$$ n^{\phi(m)} + m^{\phi(n)} \equiv 1 \pmod {mn} $$
Note: this didn't require use of the Chinese remainder theorem.