Теорема Прота

В теории чисел теорема Прота является тестом простоты для чисел Прота.

Формулировка

Теорема Прота утверждает, что если p — это число Прота вида $k\cdot 2^n + 1$, где k — нечётно и $k < 2^n$, и для некоторого целого числа a выполняется сравнение:

$a^{(p-1)/2}\equiv -1 \pmod{p}\,\!$

то p — простое (называемое простым Прота).

Тестирование чисел Прота на простоту

Теорема Прота может быть использована для тестирования простоты чисел Прота, так как, если p — простое Прота, то любое выбранное a имеет шанс около 50% сработать.

Если p — квадратичный невычет по модулю a, то обратное утверждение также верно и испытание является окончательным. Такие a можно найти перебором небольших простых чисел, вычисляя символ Якоби до тех пор, пока не выполнится

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

Примеры

• для p = 3, 2 ¹ + 1 = 3 кратно 3, поэтому 3 является простым.
• для p = 5, 3 ² + 1 = 10 кратно 5, поэтому 5 является простым.
• p = 13, 5 ⁶ + 1 = 15626 делится на 13, 13 является простым.
• для p = 9, которая не является простым, не существует b таких что a ⁴ + 1 делится на 9.

Простые числа Прота

Простые числа Прота образуют последовательность:

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 … (последовательность A080076 в OEIS)

На июнь 2012 года, крупнейшее известное простое Прота, 19249 · 2^13018586 + 1, найдено проектом Seventeen or Bust. Оно имеет 3918990 десятичных цифр и является крупнейшим известным простым, не являющимся простым Мерсенна.^[1]

История

Франсуа Прот (англ.) (1852—1879) опубликовал теорему около 1878 года.

См. также

• Число Серпинского

Примечания

1. ↑ The Top Twenty Largest Known Primes (англ.)

Ссылки

• Weisstein, Eric W. Proth's Theorem (англ.) на сайте Wolfram MathWorld.
• «Тесты простоты», Кучин, 2005