# Wilson's Theorem and Fermat's Theorem

• Wilson's theorem says that p is prime if and only if .
• Fermat's theorem says that if p is prime and , then .
• Wilson's theorem and Fermat's theorem can be used to reduce large numbers with respect to a give modulus and to solve congruences. They are also used to prove other results in number theory --- for example, those used in cryptographic applications.

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

Proof. If , then . If , then

Conversely, suppose . Then

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

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.

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 . For example,

Example. Find the least nonnegative residue of .

Note that . 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

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

Proof. The idea is to show that the integers

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. Compute .

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 , so

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. Solve .

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 , or I could do a multiplication table mod 41. A simpler approach is to note that by Fermat, . Hence,

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".

, so

Now , so

, so

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

Contact information