Vantieghems theorem
In number theory, Vantieghems theorem is a primality criterion. It states that a natural number n is prime if and only if
Similarly, n is prime, if and only if the following congruence for polynomials in X holds:
or:
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. (69-72): 3889–3892. arXiv:math/0402128. Zbl 1126.11307.. An article with proof and generalizations.
- Vantieghem, E. (1991). "On a congruence only holding for primes". Indag. Math., New Ser. 2 (2): 253–255. Zbl 0734.11003.
This article is issued from Wikipedia - version of the 12/23/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.