This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American
An easy way to tell whether a number is prime: it’s a holy grail, a million-dollar idea, a dream. That’s why I was so excited when I read about Wilson’s theorem on John D. Cook’s blog. It’s a theorem that gives a necessary and sufficient criterion for a number n to be prime. (A prime number is a whole number greater than 1 that is only divisible by itself and 1.)
Of course, there’s one other well-known necessary and sufficient condition for n to be prime: n is prime if and only if n/m is never a whole number for any m between 2 and n. But that condition is basically just the definition of a number being prime, and checking it requires dividing your number by potential divisors over and over. Even if you’re clever about it and rule out some potential divisors, you’ve got a lot of division on your hands.
Here’s Wilson’s theorem:
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
A whole number n is prime if and only if (n-1)!+1 is divisible by n.
(Here the exclamation point does not indicate excitement but factorial: n! is 1×2×3…× n.)
An example might be helpful: let’s say we want to determine whether 5 is prime. We take 4!, which is 24, add 1 to get 25, and divide that by 5. Because we get a whole number answer, 5 is prime. Success! That doesn’t prove Wilson’s theorem is true, but it gives an idea of what the theorem is saying.
I was surprised I hadn’t heard of Wilson’s theorem before: a one-line necessary and sufficient condition for primality? Why had I been kept in the dark? Was this part of the deep web? A backdoor to breaking encryption and reading my salacious secrets, like the nonstop "do we need anything from the store" chats my spouse and I send each other on a daily basis?
Maybe Wilson’s theorem was a portal into a new number regime. I could use it to test numbers to see if they were prime, maybe even use it to find a new largest-known prime. Move over, Great Internet Mersenne Prime Search, there’s a new prime generation machine in town!
No such luck. This theorem has been around a while. It’s named Wilson’s theorem after eighteenth-century English mathematician John Wilson, but it was also known by the Arab mathematician Ibn al-Haytham, who lived around 1000 CE. (It is a multi-national theorem: the first known proof was given by French mathematician Joseph-Louis Lagrange in 1771.) If this theorem were actually an effective way to determine primality or generate new primes, someone would already be using it for that.
That’s when I realized Wilson’s theorem was trolling me. And it’s all in that tricksy factorial symbol. The factorial operation might seem fun and cute and harmless, but like an adorable baby alligator, as it grows up, it gets teeth!
The factorial function grows fast. Six factorial is 720, seven factorial is 5040, ten factorial is over 3 million. To use Wilson’s theorem to determine whether 11 is prime, you need to take ten factorial, which is 3,628,800, add 1, and divide it by 11. It’s very easy to figure out that 11 is prime without dividing a seven-digit number by it, and things only get worse as n gets larger.
For 2017, the number John D. Cook used in his post where I learned about Wilson’s theorem, you’d have to divide the 5,789-digit number 2016!+1 by 2017. I really liked doing long division as a kid, but I'm pretty sure I never attempted it on a number that had thousands of digits.
Even though it's a troll, I can't get upset with Wilson’s theorem. I have a soft spot for laughably impractical mathematics. Wilson’s theorem is like the slowest way to draw a lute or the least practical way to determine the earth is a sphere: a pretty bit of mathematics trying to do a job it was never intended to do.