In this section we study two important theorems of congruence.
Theorem.(Fermat's Little Theorem, 1640)
If \(p\) is a prime and \(a\) is an integer not divisible by \(p\), then \[ a^{p-1}\equiv 1\:\left(\mathrm{mod}\: p \right).\]
We claim that \(\{\overline{a},\overline{2a},\ldots,\overline{(p-1)a}\}=\{\overline{1},\overline{2},\ldots,\overline{p-1}\}(=\mathbb Z_p^*)\). First of all
\(\overline{ra}\neq \overline{0}\) for \(r=1,2,\ldots,p-1\). Otherwise \(p\vert ra\) for some \(r=1,2,\ldots,p-1\).
Since \(p\nmid a\), \(p\vert r\), a contradiction. To show distinctness, suppose \(\overline{ra}=\overline{sa}\)
for some integers \(1\leq r < s\leq p-1\) which implies \(\overline{(s-r)a}=\overline{0}\). Then \(p\vert (s-r)a\).
Since \(p\nmid a\), \(p\vert (s-r)\), a contradiction. Thus \(\{\overline{a},\overline{2a},\ldots,\overline{(p-1)a}\}=\{\overline{1},\overline{2},\ldots,\overline{p-1}\}\)
and consequently
\[ \begin{align*}
&\overline{a}\;\overline{2a}\cdots\overline{(p-1)a}=\overline{1}\;\overline{2}\cdots\overline{p-1}\\
\implies & \overline{a^{p-1}(p-1)!}=\overline{(p-1)!}\\
\implies & a^{p-1}(p-1)!\equiv (p-1)!\:\left(\mathrm{mod}\: p \right)\\
\implies & a^{p-1}\equiv 1\:\left(\mathrm{mod}\: p \right) \text{ as }\gcd((p-1)!,p)=1. \hfill & \text{◼}
\end{align*} \]
Example.
To determine \(2^{64}\equiv 5 \:\left(\mathrm{mod}\: 11 \right)\), using \(p=11\) in FLT we get \(2^{10}\equiv 1\:\left(\mathrm{mod}\: 11\right)\).
Note that \(64=10\cdot 6+4\). Then \(2^{64}=(2^{10})^6 2^4\equiv (1)^6 16\equiv 5 \:\left(\mathrm{mod}\: 11 \right)\).
The converse of FLT is not true as \(2^{340}\equiv 1\:\left(\mathrm{mod}\: 341 \right)\) but \(341=11\cdot 31\) is not a prime.
The first proof of FLT was published by Euler in 1736. But more than 50 years ago a similar proof was found in
an unpublished manuscript by Leibniz. Sometimes FLT is written in a more general form:
Corollary.
If \(p\) is a prime, then \(a^p\equiv a\:\left(\mathrm{mod}\: p \right)\) for all integers \(a\).
To see this, note that if \(a\) is divisible by \(p\), then \(a^p\equiv 0\equiv a\:\left(\mathrm{mod}\: p \right)\).
Otherwise it is FLT.
Using FLT, we have a probabilistic primality test called the Fermat Primality Test :
To test primality of a given integer \(n>1\), chose a random positive integer \(a < n\) not divisible by \(n\).
If \(a^{n-1}-1\) is not divisible by \(n\), then \(n\) is not a prime. Otherwise \(n\) is a probable prime.
Theorem.(Euler's Theorem, 1736)
If \(n\) is a positive integer and \(a\) is an integer such that \(\gcd(a,n)=1\), then
\[ a^{\phi(n)}\equiv 1\:\left(\mathrm{mod}\:n \right).\]
Euler's theorem is a generalization of FLT because for a prime \(n\), \(\phi(n)=n-1\) and also note that \(\gcd(a,n)=1\iff n\nmid a\).
Proof. Suppose \(S=\{k_1,k_2,\ldots,k_{\phi(n)}\}\) is the set of integers from \(\{1,2,\ldots,n\}\)
that are relatively prime to \(n\). We claim that
\[\{\overline{k_1a},\overline{k_2a},\ldots,\overline{k_{\phi(n)}a}\}=\{\overline{k_1},\overline{k_2},\ldots,\overline{k_{\phi(n)}}\}(=\mathbb Z_n^*).\]
For each \(k_i\in S\), \(\gcd(k_i,n)=1\) and \(\gcd(a,n)=1\). Then \(\gcd(k_ia,n)=1\) (gcd prop), i.e.,
\(\overline{k_ia}\in \mathbb Z_n^*\) for all \(k_i\in S\). To show distinctness, suppose \(\overline{k_ia}=\overline{k_ja}\)
for some integers \(k_i < k_j\in S\) which implies \(\overline{(k_j-k_i)a}=\overline{0}\).
Then \(n\vert (k_j-k_i)a\). Since \(\gcd(a,n)=1\), \(n\vert (k_j-k_i)\), a contradiction. Thus \(\{\overline{k_1a},\overline{k_2a},\ldots,\overline{k_{\phi(n)}a}\}=\{\overline{k_1},\overline{k_2},\ldots,\overline{k_{\phi(n)}}\}\)
and consequently
\[ \begin{align*}
&\overline{k_1a}\;\overline{k_2a}\cdots\overline{k_{\phi(n)}a}=\overline{k_1}\;\overline{k_2}\cdots\overline{k_{\phi(n)}}\\
\implies &\overline{a^{\phi(n)}k_1k_2\cdots k_{\phi(n)}}=\overline{k_1k_2\cdots k_{\phi(n)}}\\
\implies &a^{\phi(n)}k_1k_2\cdots k_{\phi(n)}\equiv k_1k_2\cdots k_{\phi(n)}\:\left(\mathrm{mod}\: n \right)\\
\implies &a^{\phi(n)}\equiv 1\:\left(\mathrm{mod}\: n \right) \text{ as }\gcd(k_1k_2\cdots k_{\phi(n)},n)=1. \hfill & \text{◼}
\end{align*} \]
Euler's Theorem plays a crucial role in the RSA cryptography (1978). Note that the converse of Euler's Theorem is also true:
Corollary.
For positive integers \(n\) and \(a\), if \(a^{\phi(n)}\equiv 1\:\left(\mathrm{mod}\: n \right)\), then \(\gcd(a,n)=1\).
Example.
To determine \(7^{65}\equiv 9 \:\left(\mathrm{mod}\: 10 \right)\), using \(n=10\) in Euler's Theorem we get
\(7^{\phi(10)}=7^{4}\equiv 1\:\left(\mathrm{mod}\: 10 \right)\). Note that \(66=16\cdot 4+2\).
Then \(21^{66}=(7^{4})^{16} 7^2\equiv (1)^{16} 49\equiv 9 \:\left(\mathrm{mod}\: 10 \right)\).