1.23: Two Theorems of Euler and Fermat

Fermat’s Big Theorem or, as it is also called, Fermat’s Last Theorem states that \(x^n + y^n = z^n\) has no solutions in positive integers \(x, y, z\) when \(n > 2\). This was proved by Andrew Wiles in 1995 over 350 years after it was first mentioned by Fermat. The theorem that concerns us in this chapter is Fermat’s Little Theorem. This theorem is much easier to prove, but has more far reaching consequences for applications to cryptography and secure transmission of data on the Internet. The first theorem below is a generalization of Fermat’s Little Theorem due to Euler.

Theorem \(\PageIndex{1}\): Euler's Theorem

If \(m>0\) and \(a\) is relatively prime to \(m\) then \[a^{\phi(m)}\equiv 1\pmod m.\nonumber \]

Theorem \(\PageIndex{2}\): Fermat's Little Theorem

If \(p\) is prime and \(a\) is relatively prime to \(p\) then \[a^{p-1}\equiv 1 \pmod p.\nonumber \]

Let’s look at some examples. Take \(m=12\) then \[\phi(m)=\phi\left(2^2\cdot3\right)=\left(2^2-2\right)(3-1)=4.\nonumber \] The positive integers \(a<m\) with \(\gcd(a,m)=1\) are \(1\), \(5\), \(7\) and \(11\). \[\begin{aligned} 1^4 &\equiv 1\pmod{12}\quad\text{is clear} \\ 5^2 &\equiv 1\pmod{12}\quad\text{since }12\mid 25-1 \\ \therefore\left(5^2\right)^2 &\equiv 1^2\pmod{12} \\ \therefore 5^4 &\equiv 1\pmod{12}.\end{aligned}\]

Now \(7\equiv -5\pmod{12}\) and since \(4\) is even \[\begin{aligned} 7^4 &\equiv 5^4\pmod{12} \\ \therefore 7^4 &\equiv 1\pmod{12}.\end{aligned}\]

\(11\equiv -1\pmod{12}\) and again since \(4\) is even we have \[11^4\equiv (-1)^4\pmod{12}\nonumber \] and \[11^4\equiv 1\pmod{12}.\nonumber \]

So we have verified Theorem \(\PageIndex{1}\) for the single case \(m=12\).

Exercise \(\PageIndex{1}\)

Verify that Theorem \(\PageIndex{2}\) holds if \(p=5\) by direct calculation as in the above example.

Definition \(\PageIndex{1}\): Powers of Residue Classes

If \([a]\in U_m\) define \([a]^1=[a]\) and for \(n>1\), \([a]^n=[a][a]\dotsm[a]\) where there are \(n\) copies of \([a]\) on the right.

Theorem \(\PageIndex{3}\)

If \([a]\in U_m\), then \([a]^n\in U_m\) for \(n\ge 1\) and \([a]^n=[a^n]\).

Proof

We prove that \([a]^n=[a^n]\in U_m\) for \(n\ge 1\) by induction on \(n\).

If \(n=1\), \([a]^1=[a]=\left[a^1\right] \) and by assumption \([a]\in U_m\). Suppose \[[a]^k=\left[a^k\right]\in U_m\nonumber \] for some \(k\ge 1\). Then \[\begin{split} [a]^{k+1} &=[a]^k[a] \\ &=\left[a^k\right][a]\quad\text{by the induction hypothesis} \\ &=\left[a^ka\right]\quad\text{by Definition 21.1} \\ &=\left[a^{k+1}\right]\quad\text{since }a^ka=a^{k+1}. \end{split}\] So by the PMI, the theorem holds for \(n\ge 1\).

Note that for fixed \(m>0\) if \(\gcd(a,m)=1\) then \([a]\in U_m\). And using Theorem \(\PageIndex{3}\) we have

\[a^n\equiv 1\pmod m \Longleftrightarrow\left[a^n\right]=[1] \Longleftrightarrow [a]^n=[1].\nonumber \]

It follows that Euler’s Theorem (Theorem \(\PageIndex{1}\)) is equivalent to the following theorem.

Theorem \(\PageIndex{4}\)

If \(m>0\) and \([a]\in U_m\) then \[[a]^{\phi(m)}=[1].\nonumber \]

A proof of Theorem \(\PageIndex{4}\) is outlined in the following exercise.

Exercise \(\PageIndex{2}\): Optional

Let \(U_m = \{X_1, X_2, \dots, X_{\phi(m)} \}\). Here we write \(X_i\) for a residue class in \(U_m\) to simplify notation.

1. Show that if \(X \in U_m\) then \[\{XX_1, XX_2, \cdots, XX_{\phi(m)} \} = U_m.\nonumber\]
2. Show that if \(X \in U_m\) then \[XX_1 XX_2 \cdots XX_{\phi(m)} = X_1X_2 \cdots X_{\phi(m)}.\nonumber\]
3. Let \(A = X_1X_2 \cdots X_{\phi(m)}\). Show that if \(X \in U_m\) then \(X^{\phi(m)}A = A.\)
4. Conclude from (3) that \(X^{\phi(m)} = [1]\) and hence Theorem \(\PageIndex{4}\) is true.

Also Theorem \(\PageIndex{4}\) is an easy consequence of Lagrange’s Theorem, which students who take (or have taken) a course in abstract algebra will learn about (or will already know).

Exercise \(\PageIndex{3}\)

Show that Fermat’s Little Theorem follows from Euler’s Theorem.

Exercise \(\PageIndex{4}\)

Show that if \(p\) is prime then \(a^p \equiv a \pmod p\) for all integers \(a\).

Hint

Consider two cases: I. \(\gcd(a,p) = 1\) and II. \(\gcd(a,p) > 1\). Note that in the second case \(p \mid a\).

Exercise \(\PageIndex{5}\)

Let \(m>0\). Let \(\gcd(a,m)=1\). Show that \(a^{\phi(m)-1}\) is an inverse for \(a\) modulo \(m\). (See Theorem 18.1)

Exercise \(\PageIndex{6}\)

For all \(a\in\{1,2,3,4,5,6\}\) find the inverse \(a^\ast\) of \(a\) modulo \(7\) by use of Exercise \(\PageIndex{5}\). Choose \(a^\ast\) in each case so that \(1\le a^\ast \le 6\).

Example \(\PageIndex{1}\)

Note that Fermat’s Little Theorem can be used to simplify the computation of \(a^n\bmod p\) where \(p\) is prime. Recall that if \(a^n\equiv r\pmod p\) where \(0\le r<p\), then \(a^n\bmod p=r\). We can do two things to simplify the computation:

1. Replace \(a\) by \(a\bmod p\).
2. Replace \(n\) by \(n\bmod(p-1)\).

Suppose we want to calculate \[ 1234^{7865435}\bmod 11.\nonumber \] Note that \(1234\equiv-1+2-3+4\pmod{11}\), that is, \(1234\equiv 2\pmod{11}\). Since \(\gcd(2,11)=1\) we have \(2^{10}\equiv1\pmod{11}\). Now \(7865435=(786543)\cdot 10+5\) so \[\begin{split} 2^{7865435} &\equiv 2^{(786543)\cdot10+5}\pmod{11} \\ &\equiv\left(2^{10}\right)^{786543}\cdot 2^5\pmod{11} \\ &\equiv 1^{786543}\cdot 2^5\pmod{11} \\ &\equiv 2^5\pmod{11}, \end{split}\] and \(2^5=32\equiv10\pmod{11}\). Hence, \[1234^{7865435}\equiv10\pmod{11}.\nonumber \] It follows that \[1234^{7865435}\bmod 11=10.\nonumber \]

Exercise \(\PageIndex{7}\)

Use the technique in the above example to calculate \[28^{1202}\bmod 13.\nonumber\] [Here you cannot use the mod 11 trick, of course.]