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

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

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

Теорема Прота гласит: Шаблон:Рамка Если p — это число Прота вида $k\cdot 2^n+1$, где k — нечётно и $k<2^n$, то p — простое (называемое простым Прота) тогда и только тогда, когда для некоторого квадратичного невычета a выполняется сравнение:

$a^{(p-1)/2}\equiv -1(\mathrm{mod}p)$

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

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

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

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

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

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

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

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

Исход (4) является причиной того, что тест вероятностный. В случае (1) $a$ — квадратичный невычет по модулю $p$. Процедура повторяется пока простота $p$ не будет установлена. Если $p$ — простое, то тест с вероятностью $1/2$ подтвердит это за одну итерацию, так как количество квадратичных невычетов по модулю $p$ ровно $(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, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 … (Шаблон:OEIS)

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

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

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

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

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

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

История

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

См. также

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

Ссылки

• Шаблон:MathWorld
• «Обзор проверок на простоту», Кучин, 2005
• Шаблон:Книга