Number Theory Home

Theorems of Fermat and Euler

    


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)\).


Last edited