WikiDer > Теорема Протса - Википедия

В теория чисел, Теорема прота это тест на простоту за Числа прот.

Говорится^[1][2] что если п это Proth число, формы k2^п + 1 с k странно и k < 2^п, и если существует целое число а для которого

${ Displaystyle а ^ { гидроразрыва {p-1} {2}} Equiv -1 { pmod {p}},}$

тогда п является основной. В этом случае п называется Proth Prime. Это практический тест, потому что если п прост, любой выбранный а шанс сработать составляет около 50 процентов.

Если а это квадратичный невычет по модулю п тогда верно и обратное, и проверка окончательна. Такой а можно найти, повторяя а над малыми простыми числами и вычисляя Символ Якоби до того как:

${ displaystyle left ({ frac {a} {p}} right) = - 1.}$

Таким образом, в отличие от многих Монте-Карло тесты на простоту (рандомизированные алгоритмы, которые могут возвращать ложный положительный результат) алгоритм проверки простоты, основанный на теореме Прота, является Алгоритм Лас-Вегаса, всегда возвращает правильный ответ, но время выполнения изменяется случайным образом.

Числовые примеры

Примеры теоремы включают:

• за п = 3 = 1(2¹) + 1, имеем 2^(3-1)/2 + 1 = 3 делится на 3, поэтому 3 простое число.
• за п = 5 = 1(2²) + 1, имеем 3^(5-1)/2 + 1 = 10 делится на 5, поэтому 5 простое число.
• за п = 13 = 3(2²) + 1, имеем 5^(13-1)/2 + 1 = 15626 делится на 13, поэтому 13 простое число.
• за п = 9, что не является простым, нет а такой, что а^(9-1)/2 +1 делится на 9.

Первые простые числа Proth - это (последовательность A080076 в OEIS):

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ….

Самый крупный из известных Proth Prime по состоянию на 2016 год^{[Обновить]} является ${ displaystyle 10223 cdot 2 ^ {31172165} +1}$, и состоит из 9,383,761 цифры.^[3] Он был найден Петером Сабольчем в PrimeGrid проект распределенных вычислений который объявил об этом 6 ноября 2016 года.^[4] Это также самый крупный известный не-Мерсенн прайм и наибольшее число Кольбера.^[5] Второе по величине известное простое число протов - это ${ displaystyle 19249 cdot 2 ^ {13018586} +1}$, найдено Семнадцать или бюст.^[6]

Доказательство

Доказательство этой теоремы использует Тест на простоту Поклингтона-Лемера, и очень напоминает доказательство Тест Пепина. Доказательство можно найти на странице 52 книги Рибенбойма в ссылках.

История

Франсуа Прот (1852–1879) опубликовал теорему в 1878 году.^[7][8]

Смотрите также

• Тест Пепина (особый случай k = 1, где выбирается а = 3)
• Число Серпинского

Рекомендации

внешняя ссылка

• Вайсштейн, Эрик В. «Теорема Прота». MathWorld.