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

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

(а) Пусть 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 — простое. [1]

Теорема Прота может быть использована для тестирования простоты чисел Прота. Алгоритм вероятностного теста, основанного на теореме, выглядит следующим образом: Случайным образом выбирается целое число ${\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}$. [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, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 … (последовательность A080076 в OEIS)

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

Лемма. Пусть ${\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[4].

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

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

• Weisstein, Eric W. Proth's Theorem (англ.) на сайте Wolfram MathWorld.
• «Обзор проверок на простоту», Кучин, 2005
• Sze, T.W. On Solving Univariate Polynomial Equations Over Finite Fields and Some Related Problems. — University of Maryland, College Park, 2007. — ISBN 9780549451037.