Vantieghems theorem

In number theory, Vantieghems theorem is a primality criterion. It states that a natural number n≥3 is prime if and only if

: $\prod_{1 \leq k \leq n-1} \left( 2^k - 1 \right) \equiv n \mod \left( 2^n - 1 \right).$

Similarly, n is prime, if and only if the following congruence for polynomials in X holds:

: $\prod_{1 \leq k \leq n-1} \left( X^k - 1 \right) \equiv n- \left( X^n - 1 \right)/\left( X - 1 \right) \mod \left( X^n - 1 \right)$

or:

: $\prod_{1 \leq k \leq n-1} \left( X^k - 1 \right) \equiv n \mod \left( X^n - 1 \right)/\left( X - 1 \right).$

Example

Let n=7 forming the product 1*3*7*15*31*63 = 615195. 615195 = 7 mod 127 and so 7 is prime

Let n=9 forming the product 1*3*7*15*31*63*127*255 = 19923090075. 19923090075 = 301 mod 511 and so 9 is composite

{{cite journal | last=Kilford | first=L.J.P. | title=A generalization of a necessary and sufficient condition for primality due to Vantieghem | zbl=1126.11307 | journal=Int. J. Math. Math. Sci. | number=69–72 | pages=3889–3892 | year=2004 | volume=2004 | doi=10.1155/S0161171204403226 | arxiv=math/0402128 | bibcode=2004math......2128K | doi-access=free }}. An article with proof and generalizations.
{{cite journal | last=Vantieghem | first=E.| title=On a congruence only holding for primes | zbl=0734.11003 | journal=Indag. Math. |series=New Series | volume=2 | number=2 | pages=253–255 | year=1991 | doi=10.1016/0019-3577(91)90013-W| doi-access=free }}