The Fermat-Euler Theorem

If \gcd(a,m)=1, then

(1)   \begin{equation*} \boxed{a^{\phi(m)}\equiv 1 \pmod m} \end{equation*}

For example, when m=10, \phi(10)=4, (i.e. 4 numbers < 10 - 1, 3, 7 and 9 - have no common divisor with 10) and a^4 \equiv 1 \bmod 10. So, the 4th power of every positive integer not divisible by 2 or 5 ends with a 1.
3^4 = 81, 7^4=2401, 9^4=6561, 11^4=14641, 13^4=28561, 17^4=83521, etc.

Leave a Reply

Your email address will not be published.