This looks a lot like Euler's Theorem (the extension of Fermat's Little Theorem), right?

Euler's Theorem guarantees that both $m^{\phi(n)} \equiv 1 \pmod{n}$ and $n^{\phi(n)} \equiv 1 \pmod{m}$. How can you turn these into something that looks like $m^{\phi(n)} + n^{\phi(m)}$?

(Try to remember what we usually do in a problem like "what is the largest three-digit number that leaves a remainder of $1$ when divided by $5$ and $7$?")