Wilsons Theorem

What Is Wilson's Theorem?

Wilson's Theorem is a statement in number theory that gives a necessary and sufficient condition for a number to be prime. It states that an integer $p>1$ is a prime number if and only if the factorial of $p-1$ is one less than a multiple of $p$. In the language of modular arithmetic, this is written as a clean, powerful formula.

Let's break that down. A prime number is a whole number greater than $1$ whose only factors are $1$ and itself. Examples include $2,3,5,7,11$, and so on. The term 'if and only if' is crucial here. It means the rule works in both directions:

• If $p$ is a prime number, then $(p-1)!\equiv -1(\mathrm{mod}p)$ is guaranteed to be true.
• If $(p-1)!\equiv -1(\mathrm{mod}p)$ is true for some integer $p$, then $p$ is guaranteed to be a prime number.

This two-way relationship makes Wilson's Theorem a complete test for primality. To understand how it works, we first need to get comfortable with its two main ingredients: factorials and modular arithmetic.

What Are Factorials and Modular Arithmetic?

Before we can test numbers with Wilson's Theorem, let's master the two key concepts it relies on. These might sound complicated, but they are built on simple ideas.

Factorials (n!)

A factorial, denoted by an exclamation mark (!), is the product of all positive integers up to that number. For example, the factorial of $5$, written as $5!$, is:

Here are a few more examples:

• $1!=1$
• $2!=2\times 1=2$
• $3!=3\times 2\times 1=6$
• $4!=4\times 3\times 2\times 1=24$

As you can see, factorials grow very quickly! This is an important detail that we'll come back to later.

Modular Arithmetic (Clock Math)

Modular arithmetic is a system of arithmetic for integers, where numbers 'wrap around' upon reaching a certain value—the modulus. Think of a 12-hour clock. If it's 10 o'clock now, what time will it be in 5 hours? It won't be 15 o'clock. It will be 3 o'clock. In modular arithmetic, we would write this as:

The symbol $\equiv$ means 'is congruent to', and $(\mathrm{mod}12)$ tells us the modulus is $12$. Two numbers are congruent modulo $m$ if they have the same remainder when divided by $m$. For example, $15÷12$ gives a remainder of $3$, so $15\equiv 3(\mathrm{mod}12)$.

Now, what does $\equiv -1$ mean in Wilson's Theorem? Let's look at the expression $(p-1)!\equiv -1(\mathrm{mod}p)$. This means that when you divide $(p-1)!$ by $p$, the remainder is the same as when you divide $-1$ by $p$. A remainder of $-1$ is simply a mathematical shortcut for a remainder of $p-1$. In other words, $(p-1)!$ is exactly one less than a multiple of $p$. For instance, $24\equiv -1(\mathrm{mod}5)$ is true because $24$ is one less than $25$, which is a multiple of $5$.

How Does Wilson's Theorem Work with Prime Numbers?

Now that we have the tools, let's see the theorem in action. We'll test a few known prime numbers to confirm that the formula holds true.

The theorem works for all primes, but as you can see, the factorial calculation becomes very large, very fast. Calculating $16!$ to test if $17$ is prime would be quite a task by hand!

Why Does the Theorem Fail for Composite Numbers?

A powerful feature of Wilson's Theorem is that it not only works for primes but also reliably fails for composite numbers (numbers greater than 1 that are not prime). Let's explore why.

A composite number $n$ can be factored into smaller integers. These factors will appear in the product of $(n-1)!$, causing the result to be a multiple of $n$, which means the remainder will be $0$.

There are two main cases for a composite number $n>4$:

1. $n$ has two distinct factors, $a$ and $b$, where $1<a<b<n$. For example, $n=10$. Its factors are $2$ and $5$. Both $2$ and $5$ are less than $9$, so they will both be part of the product in $(10-1)!=9!$.
   $$9!=9\times 8\times 7\times 6\times \mathbf{5}\times 4\times 3\times \mathbf{2}\times 1$$
   Since both $2$ and $5$ are in the product, their product, $10$, must be a factor of $9!$. If $10$ is a factor of $9!$, then $9!$ is a multiple of $10$, and the remainder when dividing $9!$ by $10$ is $0$. So, $9!\equiv 0(\mathrm{mod}10)$. This is not $-1$, so $10$ is not prime.
2. $n$ is the square of a prime number, $n=p^2$. For example, $n=9=3^2$. Consider $(9-1)!=8!$. The factors in this product include $3$ and $6$.
   $$8!=8\times 7\times \mathbf{6}\times 5\times 4\times \mathbf{3}\times 2\times 1$$
   The product contains both $3$ and $6$. Their product is $3\times 6=18$. Since $18$ is a multiple of $9$, $8!$ must also be a multiple of $9$. Therefore, $8!\equiv 0(\mathrm{mod}9)$. Again, this is not $-1$, so $9$ is not prime. This logic works for any $p^2$ as long as $2p<p^2$, which is true for all primes $p>2$.

The only special case is $n=4$. Here, $(4-1)!=3!=6$. When we check $6(\mathrm{mod}4)$, we get a remainder of $2$. So $3!\equiv 2(\mathrm{mod}4)$. Since the result is not $-1$, the theorem correctly tells us that $4$ is not prime.

Wilson's Theorem: A Quick Reference Table

Seeing the results side-by-side can make the pattern crystal clear. This table shows how Wilson's Theorem behaves for the first few integers.

Notice the clear pattern: for every prime number, the result is congruent to $-1$. For every composite number greater than $4$, the result is $0$.

What Are Some Common Mistakes?

When first learning Wilson's Theorem, it's easy to make a few common errors. Be on the lookout for these pitfalls:

• Calculating the Wrong Factorial: The formula is for $(p-1)!$, not $p!$. Always subtract one from your number before you calculate the factorial. For $p=5$, you use $4!$, not $5!$.
• Misunderstanding $\equiv -1$: The result doesn't have to be the number $-1$. The expression $\equiv -1(\mathrm{mod}p)$ means the remainder is $p-1$. For $p=7$, the remainder is $6$, which satisfies the condition.
• Arithmetic Errors: Factorials get very large, very fast. A small mistake in multiplication can lead to the wrong conclusion. Always double-check your calculations.
• Assuming It's a Practical Test for Large Numbers: While the theorem is always true, it is incredibly inefficient for testing large numbers. Calculating $100!$ would take a very long time. The theorem is more of a theoretical tool than a practical one for programmers or cryptographers.
• Forgetting the 'If and Only If' Condition: Wilson's Theorem is powerful because it works both ways. Don't just remember that primes satisfy the rule; remember that if the rule is satisfied, the number must be prime.

Is Wilson's Theorem Actually Useful?

After seeing how quickly the factorials grow, you might be wondering if Wilson's Theorem has any practical use. If you want to check if a massive number like $1,234,567,891$ is prime, calculating the factorial of one less than that number is computationally impossible. Simpler methods, like trial division, are far more efficient for smaller numbers, and more advanced algorithms are used for very large numbers in fields like cryptography.

So, why do we learn it? The value of Wilson's Theorem is not in its computational speed but in its theoretical elegance. It provides a characterization of prime numbers—a simple, non-obvious property that is true for all prime numbers and for no other numbers. It's a perfect, self-contained definition in a single equation.

Mathematicians use theorems like this as building blocks to prove other, more complex results in number theory. It connects ideas about primes, factorials, and modular arithmetic in a deep and surprising way. It's a beautiful piece of mathematical structure, and understanding it gives you a deeper appreciation for the patterns that govern the world of numbers.

Wilson's Theorem in a Nutshell

Here is a quick summary of the most important points to remember about Wilson's Theorem.

• The Core Rule: An integer $p>1$ is a prime number if and only if $(p-1)!\equiv -1(\mathrm{mod}p)$.
• What it Means: If you take a prime number $p$, calculate the factorial of the number just below it, and divide by $p$, the remainder will always be $p-1$.
• For Composite Numbers: If $n$ is a composite number greater than $4$, then $(n-1)!\equiv 0(\mathrm{mod}n)$. For $n=4$, the result is $(4-1)!\equiv 2(\mathrm{mod}4)$. In all cases, the condition for primality fails.
• Theoretical vs. Practical: It is a theoretically beautiful and important theorem for proving other concepts in mathematics, but it is not a practical or efficient method for testing if large numbers are prime.