Fermat’s Theorem (and Wilson’s Theorem)

Maybe you have heard of Wilson’s Theorem? But did you know that’s is converse also holds. In this article, I prove both Wilson’s Theorem, its converse, and Fermat’s Theorem. Then you will also see many examples using Fermat’s theorem.

Wilson’s theorem, its converse, and Fermat’s theorem are discussed. We motivate each proof through example and careful write out the proof of each theorem. Several examples of their use are given.

Wilson’s Theorem

This theorem is named after one of Edward Waring‘s students, John Wilson. But actually, Wilson only observed the result to be true and did not provide its proof. Later Euler proved Wilson’s theorem and then Gauss gave a generalization. Basically, the theorem states that the factorial of a prime number minus one is congruent to minus one modulo the prime. Interestingly, its converse is also well-known and gives a sufficient condition for an integer to be a prime.

Before we state and prove Wilson’s theorem let’s Illustrate with $p=13.$ For $p=13$ we have $(13-1)!\equiv -1 \pmod{13}$ which we can prove by using the $(13-3)/2$ congruences

$2\cdot 7 \equiv 1 \pmod{13}$,

$3\cdot 9 \equiv 1 \pmod{13}$,

$4\cdot 10 \equiv 1 \pmod{13}$,

$5\cdot 8 \equiv 1 \pmod{13}$, and

$ 6\cdot 11 \equiv 1 \pmod{13}$.

When these $(13-3)/2$ congruences are multiplied together and the factors are rearranged, we get $2\cdot 3\cdot 4\cdot \cdot \cdot (13-2)\equiv 1 \pmod{13}$ and thus $(13-2)!\equiv 1 \pmod{13}$, whence $(13-1)!\equiv -1 \pmod{13}.$

Theorem. (Wilson) If $p$ is prime, then $(p-1)!\equiv -1 \pmod{p}.$

Proof. The cases $p=2$ and $p=3$ are evident. Choose any integer $a$ from the list $1,2,3,\ldots ,p-1.$ Recall that the linear congruence $a x\equiv 1 \pmod{p}$ has a unique solution $x,$ since $(a,p)=1.$ Notice that if $a x\equiv 1 \pmod{p}$ and $a=x$ then $a\equiv \pm 1 \pmod{p}$ and so there are exactly $(p-3)/2$ pairs left. If we omit the numbers $1$ and $p-1,$ the effect is to group the remaining integers $2, 3, \ldots , p-2$ into pairs $a$ and $b$ where $a\neq b,$ such that their product $ a b\equiv 1 \pmod{p}.$ When these $(p-3)/2$ congruences are multiplied together and the factors are rearranged, we get $$ 2\cdot 3\cdot 4\cdots (p-2)\equiv 1 \pmod{p} $$ and thus $(p-2)!\equiv 1 \pmod{p}$, whence $(p-1)!\equiv -1 \pmod{p}$ as desired.

Converse of Wilson’s Theorem

Theorem. (Converse of Wilson’s Theorem) If $n>2$ is a positive integer such that $(n-1)!\equiv -1 \pmod{n},$ then $n$ is prime.

Proof. Assume that $n$ is not prime and $(n-1)!\equiv -1 \pmod{n}$, and so there is some nontrivial factor $a$ of $n$ for which $a|(n-1)!$, whence $a|1$ since $n k-(n-1)!=1$ for some integer $k.$ Therefore, $a$ can not exist and so $n$ is prime.

About Fermat’s Theorem

Given a prime number $p$ and a positive integer $a$, Fermat’s Theorem says that $a$ to the $p-1$ power is congruent to 1 modulo $p$. Fermat’s Theorem takes care of solving linear congruences with prime modulus and provides a formula for finding the solution.

Example. Before stating and proving Fermat’s Theorem let’s consider the congruence $5^{22}\equiv 1 \pmod{23}.$ To illustrate why this is true, let $p=23$ and $a=5$. Notice that $1\cdot 5 \equiv 5 \pmod{23}$ and see the same for the other congruences. Consequently, we have, $$\prod _{k=1}^{22} (k\cdot 5)=5^{22}22! \equiv 22! \pmod{23}$$ Whence, $5^{22}\equiv 1 \pmod{23}$.

Here is Fermat’s Theorem in the case $p=23$ and $a=5$.

\begin{equation*}\begin{array}{lll} 2\cdot 5 \equiv 10 \pmod{23} & 3\cdot 5 \equiv 15 \pmod{23} & 4\cdot 5 \equiv 20 \pmod{23} \\ 5\cdot 5 \equiv 2 \pmod{23} & 6\cdot 5 \equiv 7 \pmod{23} & 7\cdot 5 \equiv 12 \pmod{23} \\ 8\cdot 5 \equiv 17 \pmod{23} & 9\cdot 5 \equiv 22 \pmod{23} & 10\cdot 5 \equiv 4 \pmod{23} \\ 11\cdot 5 \equiv 9 \pmod{23} & 12\cdot 5 \equiv 14 \pmod{23} & 13\cdot 5 \equiv 19 \pmod{23} \\ 14\cdot 5 \equiv 1 \pmod{23} & 15\cdot 5 \equiv 6 \pmod{23} & 16\cdot 5 \equiv 11 \pmod{23} \\ 17\cdot 5 \equiv 16 \pmod{23} & 18\cdot 5 \equiv 21 \pmod{23} & 19\cdot 5 \equiv 3 \pmod{23} \\ 20\cdot 5 \equiv 8 \pmod{23} & 21\cdot 5 \equiv 13 \pmod{23} & 22\cdot 5 \equiv 18 \pmod{23} \end{array} \end{equation*}

Fermat’s Theorem

Theorem. (Fermat) If $p$ is prime and $a$ is a positive integer with $(a,p)=1,$ then $$ a^{p-1}\equiv 1 \pmod{p}.$$

Proof. Consider the $p-1$ integers: $a, 2a, 3a, \ldots, (p-1)a.$ These integers have the following property: if $ r a\equiv s a \pmod{p}$ with $1\leq r<s\leq p-1,$ then $r\equiv s \pmod{p}$ because $(a,p)=1.$ Therefore, these integers must be congruent modulo $p$ to $1,2,3,\ldots , p-1$ taken in some order. Multiplying all of these congruence together yields $$a^{p-1}(p-1)!\equiv (p-1)! \pmod{p}$$ and since $((p-1)!,p)=1,$ we have $a^{p-1}\equiv 1 \pmod{p}$ as desired.

If $p$ is prime and $a$ is a positive integer with $(a,p)=1,$ then $a^p\equiv a \pmod{p} $ follows as well because $a^{p-1} \equiv 1 \pmod{p}$ and so $a^p\equiv a \pmod{p}$. If $(a,p)=p$ then $a^p\equiv a\equiv 0 \pmod{p} $ and so in either case we have $a^p\equiv a \pmod{p}$.

Example. Use Fermat’s theorem to solve $23x\equiv 1 \pmod{53}$.

Solution. Since $53$ is prime and $(23,53)=1$ we can apply Fermat’s theorem, to find $23^{52}\equiv 1 \pmod{53}$. Therefore a solution is $x\equiv 23^{51} \pmod{53}$. Using $23^{25}\equiv 23 \pmod{53}$, we find the solution to be $x\equiv 23\cdot 23 \cdot 23 \equiv 30 \pmod{53}$.

Example. Compute $2^{340}$ modulo $341$. Use this to show that the converse of Fermat’s Theorem is not true.

Solution. Since $2^{340}\equiv 1 \pmod{341}$, if the converse of Fermat’s Theorem were true then $341$ would be prime. However, $341=11\cdot 13$ and so the converse of Fermat Little Theorem is not true.

Using Fermat’s Theorem

Example. Show that if $p$ is a prime and $a$ is an integer such that
$(a,p)=1,$ then $a^{p-2}$ is an inverse of $a$ modulo $p.$ Find the inverse of $5$ modulo $23.$

Solution. By Fermat’s Theorem we know that $a^{p-1}\equiv 1 \pmod{p}$ and so $a\cdot a^{p-2}\equiv 1 \pmod{p}.$ Therefore, $a^{p-2}$ is an inverse of $a$ modulo $p.$ Since $5^{22}=5\cdot 5^{21}\equiv \pmod{23}$ and $5^{21}\equiv 14 \pmod{23}.$ We see that $5\cdot 14\equiv 1 \pmod{23}$ and so $14$ is the inverse of $5$ modulo $23.$

Example. Show that if $a$ and $b$ are positive integers and $p$ is a prime with $(a,p)=1,$ then the solutions of the linear congruence $a x\equiv b \pmod{p}$ are the integers $x$ such that $x\equiv a^{p-2}b \pmod{p}.$

Example. Solve the two linear congruences $4x\equiv 11 \pmod{19}$ and $5x\equiv 19 \pmod{23}.$

Solution. Since $a^{p-2}$ is the inverse of $a$ modulo $p$ we have $$a x\equiv a\left(a^{-1}b\right)=\left(a a^{p-2}\right)b=a^{p-1}b\equiv b \pmod{p}$$ by Fermat’s Theorem.

Example. By Fermat’s Theorem we have $4^{18}\equiv 1 \pmod{19}$ and $5^{22}\equiv 1 \pmod{23}$, so $x\equiv 4^{17}\cdot 11\equiv 17 \pmod{19}$ is the solution to $4x\equiv 11 \pmod{19}$ and $x\equiv 5^{21}\cdot 19\equiv 13 \pmod{23}$ is the solution to $5x\equiv 19 \pmod{23}.$

Example. Show $p^{q-1}+q^{p-1}\equiv 1 \pmod{p q}$ when $p$ and $q$ are distinct primes.

Solution. By Fermat’s Theorem we have $p^{q-1}\equiv 1 \pmod{q}$ and $q^{p-1}\equiv 1 \pmod{p}$, thus we consider the system $x\equiv 1 \pmod{p}$ and $x\equiv 1 \pmod{q}.$ Using the Chinese Remainder Theorem we have, $$x\equiv 1\left(\frac{p q}{q}\right)p^{q-2}+1\left(\frac{p q}{p}\right)q^{q-2} \pmod{p q}.$$ Finally since $(p,q)=1$, we have $x\equiv p^{q-1}+q^{p-1}\equiv 1 \pmod{p q}$ as desired.

Exercises on Fermat’s Theorem

Exercise. What is the remainder when $16!$ is divided by 19?

Exercise. What is the remainder when $5!$ 25! is divided by 31?

Exercise. What is the remainder when $18!$ is divided by 437?

Exercise. What is the remainder when $40!$ is divided by 1763?

Exercise. Find the least positive residue of $8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13$ modulo 7.

Exercise. Show that $10!+1$ is divisible by 11 by grouping together pairs of inverses modulo 11 that occur in $10!.$

Exercise. Show that $12!+1$ is divisible by 13 by grouping together pairs of inverses modulo 13 that occur in $12!.$

Exercise. Show that if $m$ and $k$ are positive integers, then $\phi(m^k)=m^{k-1}\phi(m)$.

Exercise. Show that if $p$ is prime then $$1^{p-1}+2^{p-1}+3^{p-1}+\cdot \cdot \cdot +(p-1)^{p-1}\equiv -1 \pmod{p}.$$

Exercise. Show that if $p>2$ is prime then $$1^p+2^p+3^p+\cdot \cdot \cdot +(p-1)^p\equiv 0 \pmod{p}.$$

Exercise. Show that if $p$ is prime and $p\equiv 3 \pmod{4},$ then $$\left(\frac{p-1}{2}\right)!\equiv \pm 1 \pmod{p}.$$

Exercise. What is the remainder when $18!$ is divided by $437?$

Exercise. Use Fermat’s theorem to solve $23x\equiv 1 \pmod{91}$.

Exercise. Find the least positive residue of $9!+10!+11! +12!+13!$ modulo $11$.

About David A. Smith aka Dave
About Dave

David Smith (Dave) has a B.S. and M.S. in Mathematics and has enjoyed teaching precalculus, calculus, linear algebra, and number theory at both the junior college and university levels for over 20 years. David is the founder and CEO of Dave4Math.

Leave a Comment

Subscribe to Dave4Math

Receive free updates from Dave with the latest news!
  • This field is for validation purposes and should be left unchanged.