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

В чисел теории теорема Вантигемса является критерием простоты . Он утверждает, что натуральное число n ≥3 является простым тогда и только тогда, когда

$\prod _{1\leq k\leq n-1}\left(2^{k}-1\right)\equiv n\mod \left(2^{n}-1\right).$

Аналогично, n является простым тогда и только тогда, когда выполняется следующее сравнение для многочленов из X :

$\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)$

или:

$\prod _{1\leq k\leq n-1}\left(X^{k}-1\right)\equiv n\mod \left(X^{n}-1\right)/\left(X-1\right).$

Пример

Пусть 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 по модулю 511, поэтому 9 является составным.

Ссылки

• Килфорд, LJP (2004). «Обобщение необходимого и достаточного условия простоты, предложенное Вантигемом» . Межд. Дж. Математика. Математика. Наука . 2004 (69–72): 3889–3892. arXiv : math/0402128 . Бибкод : 2004math......2128K . дои : 10.1155/S0161171204403226 . Збл   1126.11307 . . Статья с доказательствами и обобщениями.
• Вантигем, Э. (1991). «Сравнение справедливо только для простых чисел» . Индаг. Математика . Новая серия. 2 (2): 253–255. дои : 10.1016/0019-3577(91)90013-W . Збл   0734.11003 .