Divisibility of Primes (Part One)— Wilson’s Theorem and Counting Primes
The study of primes dates back to Euclid’s time — 300 BC, ancient Greece. Ever since, primes have had a tendency to elude all order and revel in chaos. To this day, understanding the distribution of primes remains an open problem. In fact, it is arguably the biggest unsolved problem in mathematics. However, that is not to say that we cannot begin chipping away at understanding the properties of primes.
To do this, we go back to 1000 AD, the time of Ibn al-Haytham (pronounced alhazen). The first discovery of a curious property regarding the divisibility of primes. What is this property? Well, it is this:
Where p is prime. What does this mean? Simply put, it says that when you divide (p — 1)! by p, it leaves a remainder of — 1 (or, in other words, a remainder of p — 1).
Ibn al-Haytham, although is credited with discovering this property, could not prove it. It wasn’t until the 18th century that English mathematician John Wilson rediscovered it. As it turns out, this theorem is called Wilson’s theorem. But, contrary to one’s expectation, Wilson hadn’t proved it either. It took Lagrange’s genius to give the first proof in 1771. One version of the proof is as follows:
In fact, upon borrowing concepts from higher mathematics, it is possible to show that this condition is necessary and sufficient in proving the primality of numbers. That is, if a number satisfies this condition, then it is prime. And if a number is prime, it satisfies this condition.
Naturally, this suggests that it should be possible to count primes using this divisibility criterion. In fact, this is true. C. P. Willians, in a paper from 1964, managed to use Wilson’s theorem to obtain an expression for the prime counting function (a function that counts the number of primes less than a given number):
As it turns out, though, this formula is of little use. Since the factorial function grows absurdly quickly, implementing this formula even computationally seems like a long stretch. Yet, it is often the case in mathematics, that even the most unusable results may have potential applications as mathematical secrets begin unravelling themselves. For instance, if a closed-form to the factorial function can be found, it would be possible to not only concretely represent the prime counting function as a closed-form expression but it would also be possible to solve the twin-prime conjecture. More on this in the next article!
Thank you for reading and I hope you have a great day!
