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

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

Теорема Прота гласит:

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

(а) Пусть p — простое. Тогда для любого квадратичного невычета a : ${\displaystyle a^{(p-1)/2}\equiv -1{\pmod {p}}}$ по критерию Эйлера .

(б) Пусть ${\displaystyle a^{(p-1)/2}\equiv -1{\pmod {p}}}$ для некоторого квадратичного невычета a . Используем критерий Поклингтона , где ${\displaystyle n=2^{k}+1}$ . Тогда ${\displaystyle q=2}$ — единственный простой делитель ${\displaystyle n-1}$ . Проверим выполнение условий критерия:

1. ${\displaystyle a^{n-1}=(a^{(n-1)/2})^{2}\equiv 1{\pmod {n}}}$ — выполнено.
2. числа n и ${\displaystyle a^{(n-1)/q}-1}$ взаимно просты — выполнено.

Так как условие ${\displaystyle 2^{k}>{\sqrt {n}}-1}$ выполнено, n — простое.

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

Теорема Прота может быть использована для тестирования простоты чисел Прота. Алгоритм вероятностного теста, основанного на теореме, выглядит следующим образом: Случайным образом выбирается целое число ${\displaystyle a}$ , такое что ${\displaystyle a\not \equiv 1{\pmod {p}}\ }$ и вычисляет ${\displaystyle b\equiv a^{(p-1)/2}{\pmod {p}}\ }$ . Возможны следующие исходы:

1. ${\displaystyle b\equiv -1{\pmod {p}}\ }$ , тогда ${\displaystyle p}$ — простое по теорема Прота.
2. ${\displaystyle b\not \equiv \pm 1{\pmod {p}}\ }$ и ${\displaystyle b^{2}\equiv 1{\pmod {p}}\ }$ , тогда ${\displaystyle p}$ — составное, так как ${\displaystyle gcd(b\pm 1,p)}$ — нетривиальные делители ${\displaystyle p}$ .
3. ${\displaystyle b^{2}\not \equiv 1{\pmod {p}}\ }$ , тогда p — составное по малой теореме Ферма .
4. ${\displaystyle b\equiv 1{\pmod {p}}\ }$ , тогда результат теста неизвестен.

Исход (4) является причиной того, что тест вероятностный. В случае (1) ${\displaystyle a}$ — квадратичный невычет по модулю ${\displaystyle p}$ . Процедура повторяется пока простота ${\displaystyle p}$ не будет установлена. Если ${\displaystyle p}$ — простое, то тест с вероятностью ${\displaystyle 1/2}$ подтвердит это за одну итерацию, так как количество квадратичных невычетов по модулю ${\displaystyle p}$ ровно ${\displaystyle (p-1)/2}$ .

Примеры

• для 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 , , 257 , 353 , 449, 577, 641, 673, 769, 929, 1153 … (последовательность в OEIS )

На май 2017 года, крупнейшее известное простое Прота, 10223 · 2 ^31172165 + 1, найдено проектом Primegrid . Оно имеет 9383761 десятичных цифр и является крупнейшим известным простым, не являющимся простым Мерсенна .

Обобщенная теорема Прота

Лемма. Пусть ${\displaystyle n=l^{k}}$ для некоторого простого l и ${\displaystyle k\geqslant 1}$ . Пусть ${\displaystyle r^{e}}$ — степень простого числа, где ${\displaystyle r\neq l}$ . Если ${\displaystyle r^{e}{\mathcal {j}}\phi (n)}$ и ${\displaystyle r^{e}>{\sqrt {n}}}$ , то n — простое .

Доказательство. ${\displaystyle r^{e}}$ — делитель ${\displaystyle \phi (n)=(l-1)l^{k-1}}$ , поэтому ${\displaystyle r^{e}{\mathcal {j}}l-1}$ . Если ${\displaystyle k>1}$ , то ${\displaystyle \phi (n)\geqslant (l-1)l>r^{2}e>n}$ — противоречие. Следовательно ${\displaystyle k=1}$ и ${\displaystyle n}$ — простое.

Теорема (обобщенная теорема Прота). Пусть ${\displaystyle N=r^{e}t+1}$ для некоторого простого ${\displaystyle r}$ и целых ${\displaystyle e,t\geqslant 1}$ . Пусть ${\displaystyle r^{e}>t}$ . Если ${\displaystyle a^{N-1}\equiv 1(modN)}$ и ${\displaystyle a^{(N-1)/r}\not \equiv 1(modN)}$ для некоторого целого ${\displaystyle a}$ , то ${\displaystyle N}$ — простое.

Доказательство обобщенной теоремы можно найти в работе Sze .

История

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

См. также

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

Примечания

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• , Кучин, 2005
• Sze, T.W. . — University of Maryland, College Park, 2007. — ISBN 9780549451037 .