# Vantieghems Theorem for Primality Test

Vantieghems Theorem is a necessary and sufficient condition for a number to be prime. It states that for a natural number n to be prime, the product of where , is congruent to .

In other words, a number n is prime if and only if.

Examples:

• For n = 3, final product is (21 – 1) * (22 – 1) = 1*3 = 3. 3 is congruent to 3 mod 7. We get 3 mod 7 from expression 3 * (mod (23 – 1)), therefore 3 is prime.
• For n = 5, final product is 1*3*7*15 = 315. 315 is congruent to 5(mod 31), therefore 5 is prime.
• For n = 7, final product is 1*3*7*15*31*63 = 615195. 615195 is congruent to 7(mod 127), therefore 7 is prime.
• For n = 4, final product 1*3*7 = 21. 21 is not congruent to 4(mod 15), therefore 4 is composite.

Another way to state above theorem is, if divides , then n is prime.

 `// CPP code to verify Vantieghem's Theorem ` `#include ` `using` `namespace` `std; ` ` `  `void` `checkVantieghemsTheorem(``int` `limit) ` `{ ` `    ``long` `long` `unsigned prod = 1; ` `    ``for` `(``long` `long` `unsigned n = 2; n < limit; n++) { ` ` `  `        ``// Check if above condition is satisfied ` `        ``if` `(((prod - n) % ((1LL << n) - 1)) == 0) ` `            ``cout << n << ````" is prime "````; ` ` `  `        ``// product of previous powers of 2 ` `        ``prod *= ((1LL << n) - 1); ` `    ``} ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``checkVantieghemsTheorem(10); ` `    ``return` `0; ` `} `

Output:

```2 is prime
3 is prime
5 is prime
7 is prime
```

The above code does not work for values of n higher than 11. It causes overflow in prod evaluation.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://tutorialspoint.dev/algorithm/mathematical-algorithms/vantieghems-theorem-primality-test", "fetch_time": 1620297817000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2021-21/segments/1620243988753.91/warc/CC-MAIN-20210506083716-20210506113716-00038.warc.gz", "warc_record_offset": 615269409, "warc_record_length": 7146, "token_count": 579, "char_count": 1626, "score": 4.3125, "int_score": 4, "crawl": "CC-MAIN-2021-21", "snapshot_type": "latest", "language": "en", "language_score": 0.7486603260040283, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00023-of-00064.parquet"}