Vantieghems theorem

From Wikipedia, the free encyclopedia

In number theory, Vantieghems theorem is a primality criterion. It states, that a natural number n 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).

[edit] References

  • L. J. P. Kilford, A generalization of a congruence due to Vantieghem only holding for primes, 2004, arXiv:math/0402128. An article with proof and generalizations.
Languages