Skip to main content

Section 9.4 Fermat's Little Theorem

The great thing about congruence is that arithmetic becomes easier since you can replace big numbers with smaller numbers that are congruent. The following is a little but powerful theorem due to Fermat that allows you to eliminate large powers if you are working modulo some prime.

Without loss of generality, we may assume that \(a \in \{1,\dots,p-1\}\text{.}\) We consider the numbers \(a,2a,3a,\dots,(p-1)a\text{.}\) We first observe that each of these numbers is distinct modulo \(p\text{;}\) that is, for each \(c,d\in \mathbb{Z}/p\text{,}\) one has \(ca = da\mod p\) if and only if \(c=d\text{.}\) This follows from Proposition 9.1.6.

If \(\overline{a},\overline{2a}, \dots, \overline{(p-1)a}\) are the remainders of \(a,2a,\dots,(p-1)a\) after dividing by \(p\text{,}\) then we deduce that the sets \(\{\overline{a},\overline{2a}, \dots, \overline{(p-1)a}\}\) and \(\{1,2,\dots,p-1\}\) are equal Consequently,

\begin{equation*} a\cdot 2a \cdots (p-1)a = \overline{a}\cdot\overline{2a}\cdot \cdots\cdot \overline{(p-1)a} = 1\cdot 2 \cdots \cdot (p-1) \mod p\text{.} \end{equation*}

Thus

\begin{equation*} (p-1)!a^{p-1} = (p-1)!\mod p\text{.} \end{equation*}

Now since \(p\) does not divide \((p-1)!\text{,}\) Proposition 9.1.6 implies that \(a^{p-1} = 1 \mod p\text{,}\) as desired.

Find \(5^{100}\mod 7\text{.}\)

Since \(7\) does not divide \(5\text{,}\) the FLT says \(5^{6} = 1\mod 7\text{.}\) Thus, we can shave off any power of \(5\) from \(5^{100}\) that is a multiple of \(6\text{.}\) Thus,

\begin{equation*} 5^{100} = 5^{96}5^{4}=(5^{6})^{16}5^{4} = 1^{16}5^{4}= 5^{4}\text{.} \end{equation*}

Then the rest is as before:

\begin{align*} 5^{2} \amp =25 = 4\mod 7\\ 5^{4} \amp =(5^{2})^{2} = 4^{2}=16 = 2\mod 7\text{.} \end{align*}

Fermat's Little Theorem gives us a way of solving a large class of polynomial equations mod \(m\text{:}\)

Since \(n\) and \(p-1\) are coprime, there are integers \(s,t\) so that \(sn+t(p-1)=1\text{.}\)

Let us prove the uniqueness. If \(x_1,x_2 \in \{1,\dots,p-1\}\) are two such solutions, then \(x_1^n=x_2^n \mod p\text{,}\) and so for \(i \in \{1,2\}\text{,}\)

\begin{equation*} x_i = x_i^{sn+t(p-1)} = x_i^{sn}x_i^{t(p-1)} = b^s(x_i^t)^{p-1} \mod p\text{.} \end{equation*}

Since \(p\) does not divide \(x_i^t\text{,}\) Fermat's Little Theorem that each \(x_i = b^s \mod p\text{,}\) whence \(x_1=x_2\text{.}\)

Now let us prove the existence. Let \(x\) be the remainder after dividing \(b^s\) by \(p\text{.}\) Now in \(\mathbb{Z}/p\text{,}\)

\begin{equation*} x^{n} = (b^{s})^{n}=b^{ns} = b^{1-t(p-1)}=b\cdot (b^{p-1})^{-t}\text{.} \end{equation*}

(Note that this makes sense, since \(p\) does not divide \(b\text{,}\) so \(b\) is invertible.) Since \(p\) does not divide \(b\text{,}\) Fermat's Little Theorem implies that \(x^n = b \mod p\text{.}\)

Notice that even though the choice of \(s, t\) is not unique, the remainder after dividing \(b^s\) by \(p\) is unique. In other words, if \(s_1,t_1,s_2,t_2\) are integers such that for \(i \in \{1,2\}\text{,}\) we have

\begin{equation*} s_in+t_i(p-1)=1\text{,} \end{equation*}

then \(b^{s_1} = b^{s_2} \mod p\text{.}\) To see this directly, note that in \(\mathbb{Z}/p\text{,}\) we have by FLT:

\begin{equation*} b^{s_1} = (b^{s_1})^{s_2n+t_2(p-1)} = b^{s_1s_2}(b^{s_1t_2})^{p-1}=b^{s_1s_2}\text{,} \end{equation*}

and by the same reasoning:

\begin{equation*} b^{s_2} = (b^{s_2})^{s_1n+t_1(p-1)} = b^{s_1s_2}(b^{s_2t_1})^{p-1}=b^{s_1s_2}\text{.} \end{equation*}

We now have a blueprint to how to solve equations of the form (9.4.1) when \(n\) and \(p-1\) are coprime and \(p\) does not divide \(b\text{.}\)

Find \(x\in\{0,1,...16\}\) so that \(x^{7} = 4\mod 17\text{.}\)

Since \(\gcd(7,17-1)=\gcd(7,16)=1\text{,}\) we can use the Euclidean Algorithm to show that \(7\cdot 7=1+3\cdot 16\text{.}\) Thus, if \(x\) solves the above equation, then \(4 = x^{7}\text{,}\) and so

\begin{equation*} 4^{7} = (x^{7})^{7} = x^{7\cdot 7} = x^{1+3\cdot 16} = x\cdot (x^{16})^{3} = x\cdot (1)^{3} = x\text{.} \end{equation*}

Thus, \(x = 4^{7}\text{,}\) so we need to find a representative in \(\{0,1,...,16\}\text{.}\) Note that \(4^{2}=16 = -1\mod 17\text{,}\) so

\begin{equation*} 4^{7}=(4^{2})^{3} \cdot 4 = (-1)^{3} \cdot 4 =-4 = 13\mod 17\text{.} \end{equation*}

Thus, \(x=13\) is the unique solution in \(\{0,1,...,16\}\text{.}\)

Not all polynomial equations can be solved using the above method:

Find a solution to \(x^{22} = 3 \mod 11\text{.}\)

Note that \(\gcd(22,11-1)=\gcd(22,10)=2\text{,}\) so we can't use the method in Theorem 9.4.3. However, let's suppose \(x\) is a solution to the above equation and try to narrow down what it must be. Note that \(11\) does not divide \(x\) (otherwise \(x^{22} = 0\)). Thus, FLT implies \(x^{10} = 1 \mod 11\text{.}\) Hence,

\begin{equation*} x^{22}=x^{2}(x^{10})^{2} = x^{2}\text{.} \end{equation*}

Now we just need to solve \(x^{2} = 3 \mod 11\text{.}\) Again, \(\gcd(2,11-1)=\gcd(2,10)=2\text{,}\) so we still can't use the method of Theorem 9.4.3. But now the power \(2\) is small enough we can just try values \(x\in \{0,1,...,10\}\) and see what works:

  • \(\displaystyle 1^{2}=1\)

  • \(\displaystyle 2^{2}=4\)

  • \(\displaystyle 3^{2}=9\)

  • \(4^{2}=16 = 5 \mod 11\text{.}\)

  • \(5^{2}=25 = 3\mod 11\text{.}\)

Thus, \(x=5\) is a solution to \(x^{22} = 3 \mod 11\text{:}\)

\begin{equation*} 5^{22}=5^{2}(5^{10})^{2} = 3\cdot (1)^{2}=3\text{.} \end{equation*}

Note that if we can't use Theorem 9.4.3, then the solution may not be unique. In this example, note that \(x=6\) is also a solution

Find \(x\in\{0,1,...,10\}\) that solves \(x^{3} = 9 \mod 11\text{.}\)

Note \(\gcd(3,11-1)=\gcd(3,10)=1\text{,}\) so this tells us that the method of Theorem 9.4.3 should work in finding the unique solution. Note also that \(7\cdot 3 = 21=1+2\cdot 10\text{.}\) Thus, if \(x\) is the solution, then \(9 = x^{3}\mod 11\) implies

\begin{equation*} 9^{7} = (x^{3})^{7} =x^{3\cdot 7} =x^{1+2\cdot 10} =x\cdot (x^{10})^{2} = x\cdot(1)^{2} =x \mod 11\text{.} \end{equation*}

Thus, \(x = 9^{7}\text{.}\) Now we must find \(x\in \{0,1,...,10\}\) so that \(x = 9^{7}\text{.}\)

  • \(\displaystyle 9^{2}=81 = 4 \mod 11\)

  • \(9^{4}=(9^{2})^{2} = 4^{2} =16 = 5\mod 11\text{.}\)

  • \(9^{7}=9^{4}\cdot 9^{2}\cdot 9 = 5\cdot 4\cdot 9 =180 =176+4 = 4\mod 11\text{.}\)

Thus, \(x=4\) is the solution. We can also check \(4^{3}=64=55+9 = 9\mod 11\text{.}\)

Subsection 9.4.1 Diophantine equations

As congruences relate to divisibility, we can also use them to solve diophantine equations.

What are the integer solutions to \(9x^{2}+9x+2=y^{4}\text{?}\)

We will present two methods for comparison, first using the usual divisbility methods from last week, and then a second method using modular arithmetic.

Method 1: If \(x,y\) are integer solutions, then

\begin{equation*} y^{4}=9x^{2}+9x+2 =(3x+2)(3x+1)\text{.} \end{equation*}

Since \(y^{4}\geq 0\text{,}\) we know \(3x+1,3x+2> 0\) or \(\lt 0\text{.}\) First assume \(>0\text{.}\) They are coprime since \(\gcd(3x+1,3x+2)\) divides \((3x+2)-(3x+1)=1\text{.}\) Thus, \(3x+1=a^{4}\) and \(3x+2=b^{4}\) for some integers \(a\) and \(b\text{.}\) (We can assume they are non-negative). But then \(b^{4}-a^{4} =3x+2-(3x+1) =1\text{.}\) This is only possible if \((a,b)=(0,1)\) (exercise :). We can't have \(a=0\) since then \(3x+1=0\text{,}\) which is impossible if \(x\) is an integer. The same happens if \(3x+1,3x+2\lt 0\text{.}\) Thus, there are no solutions.

As you can see, the above solution is quite long (and we didn't do some of the details). Now let's instead use modular arithmetic for a shorter proof:

Method 2: If \(x,y\) are integer solutions to \(9x^{2}+9x+2=y^{4}\text{,}\) then

\begin{equation*} y^{4}=9x^{2}+9x+2 = 2\mod 3\text{.} \end{equation*}

Let \(z\in \{0,1,2\}\) be such that \(z = y\mod 3\text{,}\) then \(z^{4} = y^{4} = 2\mod 3\text{.}\) So let's test some \(z\)'s!

  • \(\displaystyle 0^{4}=0\)

  • \(\displaystyle 1^{4}=1\)

  • \(2^{4}=16 = 1 \mod 3\text{.}\)

So there are no \(z\in \{0,1,2\}\) so that \(z^{4} = 2 \mod 3\text{.}\) Thus, there are no integer solutions to \(9x^{2}+9x+2=y^{4}\text{.}\)