# Wilson's Theorem and Fermat's Theorem

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

Contact information

Copyright 2019 by Bruce Ikenaga