Don't let the name of this fool you into thinking you should actually use this to test for primality. Of course, you could, but it has no practical application, as we'll see in a minute:

Wilson's Theorem:
If p is prime,
(p - 1)! = -1 [mod p]

"Great!" you surely say? "A single equation to check for primality!" Well, yes, but unfortunately it takes much longer to calculate p! than to do a simple incremental search for factors.

"Okay then, why do we even bother recording this method?" you might be thinking. Well, I'll teach you to be so cynical. Over on Fermat's two square theorem, there's a perfect example of the power of having primality described in one equation. So although it has no practical application to finding primes, Sir John Wilson's test is a handy algebraic device.

Time for a proof. It's remarkably simple. Wilson noticed that (p - 1)! / p always has remainder p - 1. This is due to the following equation, which I believe is a consequence of Fermat's little theorem:

(x - 1)(x - 2) ... (x - (p - 1) ) = xp - 1 - 1 [mod p]

Now if we set x to p itself, we get Wilson's result:

(p - 1)! = -1 [mod p]

Log in or register to write something here or to contact authors.