\[m^{\phi (n)} \equiv 1 \; (mod \; n)\]
\[n^{\phi (m)} = \equiv \; (mod \; n)\]
both of which are statements of Euler's Theorem, where
\[\phi (a)\]
is the number of integers less than \[a\]
which are relatively prime to \[a\]
.We can write these as
\[m^{\phi (n)} -1 \equiv 0 \; (mod \; n)\]
\[n^{\phi (m)} -1 \equiv 0 \; (mod \; n)\]
If
\[gcd(m,n)=1\]
then\[(m^{\phi (n)} -1)(n^{\phi (m)} -1) \equiv 0 \; (mod \; mn)\]
\[m^{\phi (n)} n^{\phi (m)} -m^{\phi (n)}-n^{\phi (m)} +1 \equiv 0 \; (mod \; mn)\]
\[ -m^{\phi (n)}-n^{\phi (m)} +1 \equiv 0 \; (mod \; mn)\]
\[ m^{\phi (n)}+n^{\phi (m)} \equiv 1 \; (mod \; mn)\]