Kalpana Kalpana (Editor)

Vantieghems theorem

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

∏ 1 ≤ k ≤ n − 1 ( 2 k − 1 ) ≡ n mod ( 2 n − 1 ) .

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 )

or:

∏ 1 ≤ k ≤ n − 1 ( X k − 1 ) ≡ n mod ( X n − 1 ) / ( X − 1 ) .

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

Vantieghems theorem Wikipedia
(Text) CC BY-SA