Theorem 5.4.3.1. Fermat’s little theorem.
Let \(p\) be a prime number and \(a\) an integer. If \(p \nmid a\text{,}\) then \(a^{p - 1} \equiv 1 \pmod p\text{.}\)
Subsection 5.4.3 Fermat’s little theorem and Euler’s generalization
Proof.
First we proof that if \(1\le x \le p-1\) and \(1\le y \le p-1\) with \(x\ne y\) then \((a\cdot x) \bmod p\ne (a \cdot y) \bmod p\) by contradiction.
Suppose \((a \cdot x) \bmod p = (a \cdot y) \bmod p\text{.}\) Then \(a \cdot (x-y)\bmod p = 0\text{.}\) Because \(p\) is prime and \(p\nmid a\) we have that \(p\mid a(x−y)\) implies \(p\mid (x−y)\text{.}\) Because \(1\le x \le p-1\) and \(1\le y \le p-1\) and \(x\ne y\) we have \(-(p-1) \lt x-y \lt p-1\text{.}\) Thus \(x-y=0\text{,}\) which contradicts \(x\ne y\text{.}\)
Because of the above we have
\begin{equation*}
\{1,\dots,p-1\}=\bigl\{(a\!\cdot\!1) \bmod p,\dots,\bigl(a\!\cdot\!(p-1)\bigr) \mod p\bigr\}.
\end{equation*}
Thus
\begin{equation*}
\left(\prod_{b=1}^{p-1}b\right)\bmod p=\left(\prod_{b=1}^{p-1}a\!\cdot\!b\right)\mod p=\left(a^{p-1}\!\cdot\!\prod_{b=1}^{p-1}b\right)\mod p.
\end{equation*}
Therefore \(a^{p-1} \bmod p = 1\text{.}\)
Fermat’s Little Theorem 5.4.3.1 is easily generalized to all integers. For a prime number \(p\) and an integer \(a\) we obtain \(a^p\bmod p = a\)
Example 5.4.3.2. Small example for Little Fermat.
With Euler’s \(\phi\) function and the Chinese Remainder Theorem 5.4.2.1 we can generalize Fermat’s Little Theorem 5.4.3.1 to composite moduli
Theorem 5.4.3.3. Euler’s generalization.
Let \(m\) be an integer greater than one and let \(a\) be an integer. If \(\gcd(a,m)=1 \text{,}\) then \(a^{\phi(m)} \equiv 1 \pmod m\text{.}\)
Example 5.4.3.4. Little Fermat’s power.
Compute \(8^{222} \bmod{11}\text{.}\)
Solution.
Note that \(11\) is prime and \(\gcd(11, 8) = 1\text{.}\) Since \(11-1 = 10\text{,}\) Fermat’s little theorem implies \(8^{10} \equiv 1 \pmod{11}\text{.}\) We rewrite the exponent \(222\) as
\begin{equation*}
222 = 22 \cdot 10 + 2
\end{equation*}
and use properties of exponents to get
\begin{equation*}
8^{222} \equiv 8^{22 \cdot 10 + 2} \equiv 1^{22} \cdot 8^2 \pmod{11}
\equiv 9 \pmod{11}.
\end{equation*}
Thus \(8^{222} \bmod{11} = 9\text{.}\)
