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

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

ФормулировкаПравить

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

Если p — это число Прота вида  , где k — нечётно и  , то p — простое (называемое простым Прота) тогда и только тогда, когда для некоторого квадратичного невычета a выполняется сравнение:

 

ДоказательствоПравить

(а) Пусть p — простое. Тогда для любого квадратичного невычета a:   по критерию Эйлера.

(б) Пусть   для некоторого квадратичного невычета a. Используем критерий Поклингтона, где   . Тогда   — единственный простой делитель  . Проверим выполнение условий критерия:

  1.   — выполнено.
  2. числа n и   взаимно просты — выполнено.

Так как условие   выполнено, n — простое. [1]

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

Теорема Прота может быть использована для тестирования простоты чисел Прота. Алгоритм вероятностного теста, основанного на теореме, выглядит следующим образом: Случайным образом выбирается целое число  , такое что   и вычисляет  . Возможны следующие исходы:

  1.  , тогда   — простое по теорема Прота.
  2.   и  , тогда   — составное, так как   — нетривиальные делители  .
  3.  , тогда N — составное по малой теореме Ферма.
  4.  , тогда результат теста неизвестен.

Исход (4) является причиной того, что тест вероятностный. В случае (1)   — квадратичный невычет по модулю  . Процедура повторяется пока простота   не будет установлена. Если   — простое, то тест с вероятностью   подтвердит это за одну итерацию, так как количество квадратичных невычетов по модулю   ровно  . [2]

ПримерыПравить

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

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

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

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

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

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

Лемма. Пусть   для некоторого простого l и  . Пусть   — степень простого числа, где  . Если   и  , то n — простое.

Доказательство.   — делитель  , поэтому  . Если  , то   — противоречие. Следовательно   и   — простое.

Теорема (обобщенная теорема Прота). Пусть   для некоторого простого   и целых  . Пусть  . Если   и   для некоторого целого  , то   — простое.

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

ИсторияПравить

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

См. такжеПравить

ПримечанияПравить

СсылкиПравить