Identity for n^phi(m)+m^phi(n)

Consider the congruences
\[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)\]

You have no rights to post comments