  # A factorial primality test:The al-Haytham-Lagrange-Theorem.

An integer p is prime if and only if it divides (p - 1)! + 1.

Let us start with a comment taken from the MacTutor History of Mathematics archive:

Al-Haytham is [..] the first person that we know to state Wilson's theorem, namely that if p is prime then 1+(p-1)! is divisible by p. It is unclear whether he knew how to prove this result.

It is called Wilson's theorem because of a comment made by Waring in 1770 that John Wilson had noticed the result. There is no evidence that John Wilson knew how to prove it and most certainly Waring did not.

Lagrange gave the first proof in 1771 and it should be noticed that it is more than 750 years after al-Haytham before number theory surpasses this achievement of Arabic mathematics.

See also [Harvard Magazine] and [Wikipedia]. Wilson had contributed nothing to this theorem except drawing (as a student) the attention of his professor to this fact. To call this result Wilson's theorem today reflects ignorance, disrespect of intellectual achievement and of standards of academic behavior. Sometimes it reflects just Anglo-Saxon chauvinism. Hopefully this naming will be abandoned some day.

An integer p is prime if and only if it divides (p - 2)! - 1.

This is a special case of a generalized version of the al-Haytham-Lagrange-Theorem, which states:

An integer p greater than or equal to some positive integer k is prime
if and only if p divides (k - 1)! (p - k)! - (-1)k.

To prove this statement it suffices to observe that, modulo p, the largest factors of (p-1)! (namely, p-1, p-2, ... p-k+1) can be replaced by -1, -2, ... -(k-1), so that (p-1)! and -(-1)k(k-1)!(p-k)! are actually equal modulo p.  Another consequence of the al-Haytham-Lagrange-Theorem is:

An odd integer p ≥ 3 is prime if and only if
p divides (((p - 1)/2)!)2 - (-1)(p+1)/2.

See: Chia-Long Wu, Der-Chyuan Lou, Te-Jen Chang: Improved Wilson’s primality test method using in modern cryptosystem. In this paper an algorithm is proposed which only needs (n+1)[1-(1/2)k+1] multiplications, where k = log2[(n-1)/2] and n means any prime number. The authors claim that this method can efficiently perform deterministic primality tests.

Note also the following two sequences from the Online Encyclopedia of Sequences:

A002981  n! - 1 is prime for n = 3, 4, 6, 7, 12 14, 30, 32, 33, 38, 94, 166, 324, 379, 469, 546, 974,  ...

A002982  n! + 1 is prime for n = 0, 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, 340, 399, 427, 872,  ...