Wilson Primes

The relationship between prime numbers and the simple operation of multiplication has fascinated mathematicians for millennia. Hidden within the integers are elegant patterns and profound truths, often revealed by asking deceptively simple questions. What if we could test if a number is prime using a secret handshake, a calculation so specific that only primes know the correct response? This article delves into such a handshake, known as Wilson's Theorem, which establishes a beautiful and absolute link between a number $n$ and its factorial $(n-1)!$. We will explore this theorem not just as a theoretical curiosity but as a gateway to a deeper, more challenging mystery.

This journey will unfold in two parts. In the "Principles and Mechanisms" chapter, we will uncover the elegant proof behind Wilson's Theorem, understand why it works so perfectly, and then see what happens when we strengthen its conditions, leading to the birth of the elusive Wilson primes. Following this, the "Applications and Interdisciplinary Connections" chapter will demonstrate that the theorem's true power lies not in its obvious use as a primality test, but as a fundamental tool that builds surprising bridges between number theory, algebra, and even graph theory, highlighting the interconnected web of mathematical thought.

Let's begin our journey not with a grand declaration, but with a simple, playful experiment. Imagine you have a function that takes an integer, let's call it $n$, and performs a peculiar calculation: it multiplies all the numbers from 1 up to $n-1$, and then tells you the remainder when you divide this huge product by $n$. In the language of mathematicians, we're calculating $(n-1)! \pmod{n}$. What can we learn from this little game?

Let's try a few numbers. If we pick a prime number, say $n=7$, we calculate $6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720$. When we divide 720 by 7, we get $720 = 102 \times 7 + 6$. The remainder is 6. Notice that 6 is just $7-1$. Interesting. Let's try another prime, $n=13$. After a bit more sweat, you'd find that $12!$ divided by 13 leaves a remainder of 12, which is $13-1$. A pattern seems to be emerging for prime numbers.

Now, what if we choose a number that isn't prime, a composite number? Let's take $n=9$. We need to calculate $8! = 40320$. Dividing this by 9, we find $40320 = 4480 \times 9 + 0$. The remainder is 0! A starkly different result. What about a composite number like $n=10$? Well, $9! = 362880$, which clearly ends in a zero, so it's divisible by 10. The remainder is 0 again.

This simple game reveals a deep truth: the value of $(n-1)! \pmod{n}$ seems to know whether $n$ is prime or composite. For primes, the result is always one less than the number itself. For most composite numbers, the result is zero. It's like a secret handshake; only prime numbers know the right response.

This "secret handshake" is a celebrated result in number theory known as ​​Wilson's Theorem​​. It states, with beautiful certainty, that an integer $n > 1$ is a prime number if and only if:

Remember that in modular arithmetic, "being congruent to $-1$" is the same as having a remainder of $n-1$. So this formula perfectly captures the pattern we discovered.

But why is this true? The beauty of mathematics isn't just knowing the what, but understanding the why. Imagine all the numbers from $1$ to $p-1$ in a dance hall, where $p$ is a prime number. The rule of the dance is multiplication modulo $p$. For any number $a$ in this hall, there's a unique partner, its inverse $a^{-1}$, such that their product $a \times a^{-1}$ is 1. So, when we calculate $(p-1)!$, we are multiplying everyone in the hall together. Almost everyone can be paired up with their inverse, and each pair's product vanishes into a 1.

The question is, does anyone dance alone? Or rather, is any number its own partner? That would mean a number $x$ such that $x^2 \equiv 1 \pmod{p}$. This is equivalent to $x^2 - 1 \equiv 0 \pmod{p}$, or $(x-1)(x+1) \equiv 0 \pmod{p}$. Because $p$ is prime, this can only mean $x-1$ or $x+1$ is a multiple of $p$. So, the only numbers that are their own inverses are $x=1$ and $x=p-1$ (which is $-1 \pmod{p}$).

So, the grand product of everyone, $(p-1)!$, simplifies to the product of all the pairs (which is 1) times the two lonely dancers, 1 and $p-1$. The result? $1 \times (p-1) \equiv -1 \pmod{p}$. It’s a stunningly elegant argument.

And why does it fail for composite numbers? If $n$ is a composite number, say $n=a \times b$ where $a$ and $b$ are different numbers smaller than $n$, then both $a$ and $b$ will appear in the list of numbers being multiplied to form $(n-1)!$. This means that their product, $n$, must divide $(n-1)!$, leading to a remainder of 0. The only tricky case is the square of a prime, like $n=p^2$, but for $p>2$, both $p$ and $2p$ are distinct factors in the factorial, so $p^2$ still divides it. The only exception is the number 4, where $3! = 6 \equiv 2 \pmod{4}$. For every other composite number greater than 4, the remainder is 0.

The "if and only if" nature of Wilson's Theorem makes it a theoretically perfect test for primality. Unlike other tests, such as the one based on Fermat's Little Theorem, Wilson's Theorem has no exceptions, no "pseudoprimes" or "Carmichael numbers" that pretend to be prime. So why isn't it the basis for all internet security? Because computing $(n-1)!$ for a large number $n$ is a monstrously slow task. It is a beautiful diamond, but far too difficult to wield as a practical tool.

Here, our story takes a turn, one that is characteristic of the mathematical spirit. When faced with a beautiful equation, a mathematician's impulse is to ask, "Can we make it stronger?"

Wilson's theorem, $(p-1)! \equiv -1 \pmod p$, tells us that $(p-1)!+1$ is always a multiple of the prime $p$. This allows us to define an integer, now called the ​​Wilson quotient​​, for any prime $p$:

We know $W_p$ is an integer, but what kind of integer is it? Is there a pattern to it? A natural, burning question arises: what if we ask for this quotient to also be a multiple of $p$?

For $W_p$ to be a multiple of $p$, we would need $W_p \equiv 0 \pmod p$. Substituting the definition of $W_p$, this is equivalent to:

Multiplying by $p$ on both sides seems strange, but it leads us to the heart of the matter. This condition means that $(p-1)! + 1$ must be divisible not just by $p$, but by $p^2$. Rearranging this gives us a new, much more stringent congruence:

A prime that satisfies this remarkable condition is called a ​​Wilson prime​​. While every prime satisfies the Wilson congruence modulo $p$, only a select few are powerful enough to satisfy it modulo $p^2$. It's like asking a weightlifter who can lift 100 kg to lift 10,000 kg instead.

So, do any such primes exist? Let's go hunting.

• For $p=2$: $1! = 1$, and $-1 \pmod{2^2}$ is $3$. $1 \not\equiv 3 \pmod 4$. No.
• For $p=3$: $2! = 2$, and $-1 \pmod{3^2}$ is $8$. $2 \not\equiv 8 \pmod 9$. No.
• For $p=5$: $4! = 24$, and $-1 \pmod{5^2}$ is $24$. $24 \equiv 24 \pmod{25}$. Yes! We have found one. The number 5 is a Wilson prime.

The thrill of finding the first one is immense. Are there others? The search is not easy. The next one is $p=13$. A tedious but direct calculation confirms that $12! = 479,001,600$, and $13^2 = 169$. Dividing one by the other, we find $12! \equiv 168 \equiv -1 \pmod{169}$. So, 13 is also a Wilson prime!.

After 13, the landscape becomes barren. After extensive computer searches, only one more Wilson prime has ever been found: the rather large number 563. To date, the complete list of known Wilson primes is just ​​5, 13, and 563​​. Searches have gone up to $2 \times 10^{13}$ without finding another. Are these three just numerical flukes, or are there more, hiding in the vast expanse of the number line?

This is where we stand, at the edge of the known mathematical world. The rarity of Wilson primes is a profound mystery. To get a handle on it, let's try a bit of "physicist's reasoning" – a heuristic argument.

We know from Wilson's theorem that for any prime $p$, $(p-1)!$ must be of the form $k p - 1$ for some integer $k$. This means the remainder of $(p-1)!$ when divided by $p^2$ must be one of the numbers $-1, -1+p, -1+2p, \dots, -1+(p-1)p$. There are exactly $p$ possibilities. A prime $p$ is a Wilson prime if, out of these $p$ possible outcomes, we happen to land on the very first one: $-1$.

Now, let's make a naive assumption: suppose that there is no deep reason for the value of $(p-1)! \pmod{p^2}$ to prefer one of these $p$ possibilities over another. Let's assume it behaves like a random dart thrown at $p$ targets. The probability of hitting our special target, $-1$, would be $1/p$.

This simple model predicts that the probability of a prime $p$ being a Wilson prime is about $1/p$. What does this imply about the total number of Wilson primes? It suggests that the expected number of Wilson primes up to a large number $x$ should be roughly the sum of these probabilities: $\sum_{p \le x} \frac{1}{p}$.

And here is the beautiful twist. This sum, the sum of the reciprocals of the primes, is known to diverge. It goes to infinity! However, it does so with agonizing slowness, growing as the natural logarithm of the natural logarithm of $x$, a function written as $\log(\log(x))$.

This provides a stunningly elegant, though unproven, explanation for the mystery. If this model is right, there should be infinitely many Wilson primes, fulfilling our hope for a rich structure. But they are so incredibly sparse, and the expected number grows so slowly, that our current predicament is not surprising at all. The expected number of Wilson primes up to $2 \times 10^{13}$ is about $\log(\log(2 \times 10^{13})) \approx 3.4$. Finding only three—5, 13, and 563—is perfectly consistent with this simple, beautiful guess.

We are left with a tantalizing cliffhanger. A simple question about factorials has led us through a beautiful theorem, into a computational puzzle, and finally to the frontiers of number theory, where a simple probabilistic model gives us hope, but no certainty. And that is the very essence of the mathematical adventure.

After our journey through the fundamental principles of Wilson's theorem and the curious nature of Wilson primes, it's natural to ask: What is all of this good for? Is it merely a mathematical curiosity, a strange pattern in the tapestry of numbers? Or is it a key that unlocks deeper secrets? The answer, as is so often the case in science, is that its true value lies not in a single, narrow application, but in the unexpected bridges it builds and the powerful new perspectives it offers.

One might first look at Wilson's theorem and see its most obvious application: a test for primality. The theorem states, with beautiful and absolute certainty, that an integer $n>1$ is a prime number if, and only if, the quantity $(n-1)!+1$ is perfectly divisible by $n$. There are no exceptions, no probabilities, no 'maybes.' It is a crisp, clean line drawn in the sand separating the primes from the composites. What more could we ask for in a test?

Well, we could ask for it to be useful! And here we encounter a wonderful lesson in the gulf that can exist between theoretical perfection and practical reality. Imagine you want to test if a number like $101$ is prime using this method. You would need to calculate $100!$, a number with 158 digits, and then check if it's one less than a multiple of $101$. For a computer, this is manageable. But what about a number with a few hundred digits, the kind routinely used in modern cryptography? The number of operations needed to compute $(n-1)!$ grows exponentially with the number of digits in $n$. The calculation becomes not just difficult, but astronomically impossible. Our perfect theoretical sword is too heavy to lift. It is a flawed gem, an exquisite tool that serves mainly to prove that a better tool is needed. This realization itself is a profound insight, driving mathematicians toward a deeper understanding of computational complexity and motivating the development of algorithms like the Agrawal–Kayal–Saxena (AKS) test, which proved that primality testing could, in principle, be both definitive and efficient.

To dismiss Wilson's theorem as merely a failed primality test, however, is to miss its genius entirely. Its true power is not as a gatekeeper deciding "prime" or "not prime," but as a computational tool within the strange and wonderful world of modular arithmetic. The theorem gives us a fixed point, an anchor in a swirling sea of numbers: for any prime $p$, we know for a fact that $(p-1)! \equiv -1 \pmod{p}$. This isn't just a curiosity; it's a simplification rule of immense power.

For instance, if you were asked to find the remainder of $18!$ when divided by the prime $23$, you wouldn't need to multiply out that enormous number. Instead, you could use Wilson's theorem as a shortcut, working backwards from the known value of $22! \pmod{23}$ to find the answer with just a few clever steps of modular arithmetic. This theorem allows us to derive other useful identities, like the surprisingly simple fact that for any prime $p>2$, $(p-2)! \equiv 1 \pmod{p}$.

This theorem truly shines when it works in concert with other great theorems of number theory. Problems that seem impossibly complex can suddenly collapse into elegant solutions when Wilson's theorem is combined with tools like Fermat's Little Theorem or the Chinese Remainder Theorem. Whether one is designing cryptographic schemes, verifying digital signatures, or solving abstract systems of congruences, Wilson's theorem often provides a crucial piece of the puzzle. It is a fundamental tool in the number theorist's kit.

Perhaps the most beautiful aspect of Wilson's theorem is how it transcends number theory, creating stunning and unexpected connections to other fields of mathematics. It acts as a kind of Rosetta Stone, translating problems from one domain into the language of another.

Consider a puzzle from graph theory. You are a network engineer for a data center with $p$ servers, where $p$ is a prime number. The network is fully connected. How many unique "tours" can a diagnostic packet make, starting from one server, visiting every other server exactly once, and returning to its origin? A little thought reveals the answer is the number of ways to order the $p-1$ other servers, which is simply $(p-1)!$. Now, let's ask a quintessentially number-theoretic question: what is the remainder when this enormous number of tours is divided by the number of servers, $p$? Combinatorial problems rarely have clean answers when you start asking about divisibility. But here, Wilson's theorem steps in and says, with astonishing simplicity, the remainder is always $p-1$. A question about counting paths is answered by a deep property of prime numbers.

Let's turn to the world of algebra. Imagine a polynomial, $P(x)$, whose roots are all the non-zero numbers in the world of "clock arithmetic" modulo a prime $p$—that is, the roots are the integers $\{1, 2, \ldots, p-1\}$. The polynomial would look like $P(x)=(x-1)(x-2)\cdots(x-(p-1))$. What is the value of this polynomial at $x=0$? Evaluating $P(0)$ gives us $(-1)^{p-1}(p-1)!$. Since any prime $p>2$ is odd, $p-1$ is even, and this simplifies to just $(p-1)!$. So, the constant term of this special polynomial is exactly the factorial that appears in Wilson's theorem. The theorem tells us that, when viewed modulo $p$, this constant term is always $-1$. The structure of polynomials over finite fields is thus intimately tied to this fundamental property of primes.

Finally, we can journey even deeper, into the structure of squares and roots. A pivotal question in number theory is: when does $-1$ have a square root in the world modulo $p$? The existence of such a number, an $x$ such that $x^2 \equiv -1 \pmod p$, fundamentally changes the arithmetic in that world. Wilson's theorem provides a surprising link to this concept. For example, solving an equation like $x^2 \equiv (p-1)! \pmod p$ is trivialized by the theorem. It immediately becomes $x^2 \equiv -1 \pmod p$. Thus, Wilson's theorem directly relates the factorial to the problem of finding the square root of $-1$ modulo $p$. We know from other work that this is only possible when the prime $p$ has the form $4k+1$. Thus, Wilson's theorem connects the value of a factorial to the profound theory of quadratic residues, linking primality to the deepest algebraic structures within modular systems..

From a failed primality test to a master key unlocking secrets in combinatorics, algebra, and number theory, Wilson's theorem reveals the interconnected beauty of mathematics. And this brings us back to our central mystery: the Wilson primes. The condition $(p-1)! \equiv -1 \pmod p$ is a foundational law. The condition for a Wilson prime, $(p-1)! \equiv -1 \pmod{p^2}$, is a demand for a much higher, more perfect degree of conformity. It's like discovering a physical law that not only works, but works to an uncanny level of precision. The extreme rarity of the known Wilson primes—5, 13, and 563—tells us that this higher-order harmony is incredibly special. The ongoing search for more is not just a hunt for trophies; it's an exploration into the deepest, most subtle symmetries of the integers, a quest to understand why this beautiful pattern holds, and why it does so with such breathtaking rarity.