Теорема Вантигемса - Vantieghems theorem

В теория чисел, Теорема Вантигемса это первобытность критерий. В нем говорится, что натуральное число п является премьер если и только если

${displaystyle prod _ {1leq kleq n-1} left (2 ^ {k} -1ight) эквивалент nmod left (2 ^ {n} -1ight).}$

Так же, п является простым, если и только если следующие соответствие для многочлены в Икс держит:

${displaystyle prod _ {1leq kleq n-1} left (X ^ {k} -1ight) эквивалент n-left (X ^ {n} -1ight) / left (X-1ight) mod left (X ^ {n} - 1 ночь)}$

или:

${displaystyle prod _ {1leq kleq n-1} left (X ^ {k} -1ight) эквивалент nmod left (X ^ {n} -1ight) / left (X-1ight).}$

пример

Пусть n = 7, образуя произведение 1 * 3 * 7 * 15 * 31 * 63 = 615195. 615195 = 7 по модулю 127, поэтому 7 простое
Пусть n = 9 образует произведение 1 * 3 * 7 * 15 * 31 * 63 * 127 * 255 = 19923090075. 19923090075 = 301 mod 511, поэтому 9 составное

использованная литература

• Килфорд, L.J.P. (2004). «Обобщение необходимого и достаточного условия простоты из-за Вантигема». Int. J. Math. Математика. Sci. (69–72): 3889–3892. arXiv:математика / 0402128. Bibcode:2004математика ...... 2128K. Zbl  1126.11307.. Статья с доказательствами и обобщениями.
• Вантигхем, Э. (1991). «По сравнению только для простых чисел». Indag. Math., New Ser. 2 (2): 253–255. Zbl  0734.11003.