Wilson's Theorem and Fermat's Theorem


Lemma. Let p be a prime and let $0 < k < p$ . $k^2 = 1
   \mod{p}$ if and only if $k = 1$ or $k = p - 1$ .

Proof. If $k = 1$ , then $k^2 = 1 \mod{p}$ . If $k = p - 1$ , then

$$k^2 = p^2 - 2p + 1 = 1 \mod{p}.$$

Conversely, suppose $k^2 = 1
   \mod{p}$ . Then

$$p \mid k^2 - 1 = (k - 1)(k + 1),$$

and since p is prime, $p \mid k -
   1$ or $p \mid k + 1$ . The only number in $\{1, \ldots, p - 1\}$ which satisfies $p \mid k - 1$ is 1, and the only number in $\{1, \ldots, p - 1\}$ which satisfies $p \mid k + 1$ is $p - 1$ .

Theorem. (Wilson's theorem) Let $p > 1$ . p is prime if and only if

$$(p - 1)! = -1 \mod{p}.$$

Proof. Suppose p is prime. If $k \in \{1, \ldots, p - 1\}$ , then k is relatively prime to p. So there are integers a and b such that

$$ak + bp = 1, \quad\hbox{or}\quad ak = 1 \mod{p}.$$

Reducing a mod p, I may assume $a
   \in \{1, \ldots, p - 1\}$ .

Thus, every element of $\{1,
   \ldots, p - 1\}$ has a reciprocal mod p in this set. The preceding lemma shows that only 1 and $p - 1$ are their own reciprocals. Thus, the elements $2, \ldots, p - 2$ must pair up into pairs $\{x, x^{-1}\}$ . It follows that their product is 1. Hence,

$$(p - 1)! = 1\cdot 2\cdots (p - 2)\cdot (p - 1) = 1\cdot 1\cdot (p - 1) = p - 1 = -1 \mod{p}.$$

Now suppose $(p - 1)! = -1
   \mod{p}$ . I want to show p is prime. Begin by rewriting the equation as $(p - 1)! + 1 = kp$ .

Suppose $p = ab$ . I may take $1 \le a, b \le p$ . If $a = p$ , the factorization is trivial, so suppose $a < p$ . Then $a \mid (p
   - 1)!$ (since it's one of $\{1, \ldots, p - 1\}$ ) and $a \mid p$ , so $(p - 1)! + 1 = kp$ shows $a \mid 1$ . Therefore, $a = 1$ .

This proves that the only factorization of p is the trivial one, so p is prime.


Example. Wilson's theorem implies that the product of any ten consecutive numbers, none divisible by 11, equals -1 mod 11 (since any ten consecutive numbers reduce mod 11 to $\{1, 2, \ldots, 10\}$ . For example,

$$12\cdot 13\cdots 20\cdot 21 = -1 \mod{11}.\quad\halmos$$


Example. Find the least nonnegative residue of $70! \mod{5183}$ .

Note that $5183 = 71\cdot 73$ . I'll start by finding the residues of $70!$ mod 71 and 73.

By Wilson's theorem,

$$70! = -1 \mod{71}.$$

Next, let $k = 70! \mod{73}$ . Then

$$71\cdot 72\cdot k = 70!\cdot 71\cdot 72 \mod{73},$$

$$(-2)(-1)k = 72! \mod{73},$$

$$2k = -1 \mod{73}.$$

Note that $2\cdot 37 = 74 = 1
   \mod{73}$ . So

$$37\cdot 2k = 37\cdot (-1) \mod{73},$$

$$k = -37 = 36 \mod{73}.$$

Thus,

$$70! = -1 \mod{71} \quad\hbox{and}\quad 70! = 36 \mod{73}.$$

I'll the the iterative method of the Chinese Remainder Theorem to get a congruence mod 5183. First, $70! = -1 \mod{71}$ means $70! = -1 + 71a$ for some $a \in \integer$ . Plugging this into the second congruence yields

$$-1 + 71a = 36 \mod{73},$$

$$71a = 37 \mod{73},$$

$$-2a = 37 \mod{73},$$

$$(-37)(-2a) = (-37)(37) \mod{73},$$

$$a = -1369 = 18 \mod{73}.$$

The last congruence means that $a
   = 18 + 73b$ for some $b \in \integer$ . Plugging this into $70! = -1 + 71a$ gives

$$70! = -1 + 71(18 + 73b) = 1277 + 5183b, \quad\hbox{or}\quad 70! = 1277 \mod{5183}.\quad\halmos$$


Theorem. (Fermat) Let p be prime, and suppose $p \notdiv a$ . Then $a^{p-1} = 1 \mod{p}$ .

Proof. The idea is to show that the integers

$$a, 2a, \ldots, (p - 1)a$$

reduce mod p to the standard system of residues $\{1, \ldots, p - 1\}$ , then apply Wilson's theorem.

There are $p - 1$ numbers in the set $\{a, 2a, \ldots, (p - 1)a\}$ . So all I need to do is show that they're distinct mod p. Suppose that $1 \le j, k \le p - 1$ , and

$$aj = ak \mod{p}.$$

This means $p \mid aj - ak = a(j
   - k)$ , so $p \mid a$ or $p \mid j -
   k$ . Since the first case is ruled out by assumption, $p \mid
   j - k$ . But since $1 \le j, k \le p - 1$ , this is only possible if $j = k$ .

Thus, $\{a, 2a, \ldots, (p -
   1)a\}$ are $p - 1$ distinct numbers mod p. So if I reduce mod p, I must get the numbers in $\{1, \ldots,
   p - 1\}$ . Hence,

$$a\cdot 2a\cdots (p - 1)a = 1\cdot 2\cdots (p - 1) = (p - 1)! = -1 \mod{p}.$$

On the other hand, another application of Wilson's theorem shows that

$$a\cdot 2a\cdots (p - 1)a = a^{p-1}(p - 1)! = -a^{p-1} \mod{p}.$$

So $-a^{p-1} = -1 \mod{p}$ , or $a^{p-1} = 1 \mod{p}$ .

Corollary. If p is prime, then $a^p = a \mod{p}$ for all a.

Proof. If $p \mid a$ , then $a^p = 0 \mod{p}$ and $a = 0
   \mod{p}$ , so $a^p = a \mod{p}$ .

If $p \notdiv a$ , then $a^{p-1} = 1 \mod{p}$ . Multiplying by a, I get $a^p = a
   \mod{p}$ again.


Example. Compute $50^{250} \mod{83}$ .

If you multiply out $50^{250}$ , here's what you get:

$52714787526044456024726519219225572551424023323922008641517022$

$09078987540239533171017648022222644649987502681255357847020768$

$63325972445883937922417317167855799198150634765625000000000000$

$00000000000000000000000000000000000000000000000000000000000000$

$00000000000000000000000000000000000000000000000000000000000000$

$00000000000000000000000000000000000000000000000000000000000000$

$0000000000000000000000000000000000000000000000000000$

Now just reduce mod 83. Heh.

If you don't have access to software that can do this, you can use Fermat's theorem. First, 83 is prime and $83 \notdiv 50$ , so Fermat says $50^{82} = 1 \mod{83}$ . Now $3\cdot 82 = 246$ , so

$$50^{250} = 50^{246}\cdot 50^4 = (50^{82})^3\cdot 2500^2 = 1^3\cdot 10^2 = 100 = 17 \mod{83}.$$

In other words, if you're trying to reduce $a^k$ mod p, where $p
   \notdiv a$ , factor out as many $a^{p-1}$ 's as possible, then reduce the rest "by hand".


Example. Solve $16x = 25 \mod{41}$ .

I'd like to multiply both sides by the reciprocal of 16 mod 41. What is it? Well, I could use the Euclidean algorithm on $(16,41)$ , or I could do a multiplication table mod 41. A simpler approach is to note that by Fermat, $16^{40} = 1 \mod{41}$ . Hence,

$$16^{39}\cdot 16x = 16^{39}\cdot 25 \mod{41} \quad\hbox{gives}\quad x = 16^{39}\cdot 25 \mod{41}.$$

Now this is an answer, but a rather cheesy one. I ought to reduce the right side mod 41 to something a little smaller! I can't use Fermat any more, so I just "divide and conquer".

$16^2 = 256 = 10 \mod{41}$ , so

$$16^{39}\cdot 25 = (16^2)^{19}\cdot (16\cdot 25) = 10^{19}\cdot 400 = 10^{19}\cdot 31 \mod{41}.$$

Now $10^2 = 100 = 18 \mod{41}$ , so

$$10^{19}\cdot 31 = (10^2)^9\cdot (10\cdot 31) = 18^9\cdot 310 = 18^9\cdot 23 \mod{41}.$$

$18^2 = 324 = 37 \mod{41}$ , so

$$18^9\cdot 23 = (18^2)^4\cdot (18\cdot 23) = 37^4\cdot 414 = 1874161\cdot 414 = 10\cdot 4 = 40 \mod{41}.$$

(I reduce down to the point where the arithmetic can be handled by whatever computational tools I have available.)


Contact information

Bruce Ikenaga's Home Page

Copyright 2008 by Bruce Ikenaga