Suppose p is prime. Wilson's theorem says . Fermat's theorem says if , then . They are often used to reduce factorials and powers mod a prime.

I'll prove Wilson's theorem first, then use it to prove Fermat's theorem.

* Lemma.* Let p be a prime and let . Then if and only if or .

* Proof.* If , then . If , then

Conversely, suppose . Then

Since p is prime, or . The only number in which satisfies is 1, and the only number in which satisfies is .

means --- that is, k is its own multiplicative inverse. So the result says that 1 and are the only numbers which are their own multiplicative inverses mod p.

* Theorem.* (Wilson's theorem) Let . p is prime if and only if

* Proof.* Suppose p is prime. If , then k is relatively prime to
p. So there are integers a and b such that

Reducing a mod p, I may assume .

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

Now suppose . I want to show p is prime. Begin by rewriting the equation as .

Suppose . I may take . If , the factorization is trivial, so suppose . Then (since it's one of ) and , so shows . Therefore, .

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

Let's see how this works in a particular case. Take . Then mod 11 I have

Notice how the numbers other than 1 and 10 paired up as a number and its multiplicative inverse, and how 1 and 10 are the only numbers which are their own multiplicative inverses.

Note that implies that p is prime --- but this is not a very good way to test that a number is prime. The factorials grow too rapidly.

* Theorem.* (Fermat) Let p be prime, and suppose
. Then .

* Proof.* Consider the set of integers

I'll show that they reduce mod p to the standard system of residues , then apply Wilson's theorem.

There are numbers in the set . So all I need to do is show that they're distinct mod p. Suppose that , and

This means , so or . Since the first case is ruled out by assumption, . But since , this is only possible if .

Thus, are distinct numbers mod p. So if I reduce mod p, I must get the numbers in . Hence,

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

So , or .

* Corollary.* If p is prime, then for all a.

* Proof.* If , then and , so .

If , then . Multiplying by a, I get again.

* Example.* Reduce to a
number in the range . (Note: 83 is
prime.)

If you multiply out , here's what you get:

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 , so Fermat says .

Now

Hence,

In other words, if you're trying to reduce mod p, where , factor out as many 's as possible, then reduce the rest "by hand".

* Example.* Reduce to a
number in the range . (Note that 113 is
prime.)

Since 113 is prime and , Fermat's theorem gives . So

Next,

I need to compute .

Hence, . So

* Example.* Compute

The any ten consecutive numbers, none divisible by 11, reduce mod 11 to . Hence,

* Example.* Simplify to a number in the range .

By Wilson's theorem, . So

It follows that , so

* Example.* Simplify to a number in the range .

Note: 149 is prime.

By Wilson's theorem, .

Now , so

The next problem shows how you can often deal with composite moduli: Factor the modulus into a product of (powers of) primes, solve the problem relative to the prime (power) moduli, then combine the results using the Chinese Remainder Theorem to answer the original question.

* Example.* Find the least nonnegative residue of
.

Note: .

I'll start by finding the residues of mod 71 and 73.

By Wilson's theorem,

Next, let . Then

Note that . So

Thus,

I'll the the iterative method of the Chinese Remainder Theorem to get a congruence mod 5183. First, means for some . Plugging this into the second congruence yields

The last congruence means that for some . Plugging this into gives

Copyright 2019 by Bruce Ikenaga