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

∏ 1 ≤ k ≤ n − 1 ( 2 k − 1 ) ≡ n mod ( 2 n − 1 ) . {\displaystyle \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:

∏ 1 ≤ k ≤ n − 1 ( X k − 1 ) ≡ n − ( X n − 1 ) / ( X − 1 ) mod ( X n − 1 ) {\displaystyle \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:

∏ 1 ≤ k ≤ n − 1 ( X k − 1 ) ≡ n mod ( X n − 1 ) / ( X − 1 ) . {\displaystyle \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

References

  • Kilford, L.J.P. (2004). "A generalization of a necessary and sufficient condition for primality due to Vantieghem". Int. J. Math. Math. Sci. 2004 (69–72): 3889–3892. arXiv:math/0402128. Bibcode:2004math......2128K. doi:10.1155/S0161171204403226. Zbl 1126.11307.. An article with proof and generalizations.
  • Vantieghem, E. (1991). "On a congruence only holding for primes". Indag. Math. New Series. 2 (2): 253–255. doi:10.1016/0019-3577(91)90013-W. Zbl 0734.11003.