Теорема Прота - Proth's theorem

В теории чисел , Теорема Прот является тестом на простоту для Числа Прота .

Это указывает , что если р является число Proth , вида к 2 ^п + 1 с K нечетное и K <2 ^п , и если существует целое число , для которого

${\ Displaystyle а ^ {\ гидроразрыва {p-1} {2}} \ Equiv -1 {\ pmod {p}},}$

то р является премьер . В этом случае p называется простым числом Прота . Это практический тест, потому что, если p простое, любой выбранный a имеет около 50% шансов работать.

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

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

Таким образом, в отличие от многих тестов на простоту Монте-Карло (рандомизированные алгоритмы, которые могут возвращать ложные срабатывания ), алгоритм проверки на простоту, основанный на теореме Прота, является алгоритмом Лас-Вегаса , всегда возвращающим правильный ответ, но с временем выполнения, которое изменяется случайным образом.

Числовые примеры

Примеры теоремы включают:

• для p = 3 = 1 (2 ¹ ) + 1 имеем, что 2 ^{(3-1) / 2} + 1 = 3 делится на 3, поэтому 3 простое число.
• для p = 5 = 1 (2 ² ) + 1 имеем, что 3 ^{(5-1) / 2} + 1 = 10 делится на 5, поэтому 5 простое число.
• для p = 13 = 3 (2 ² ) + 1 имеем, что 5 ^{(13-1) / 2} + 1 = 15626 делится на 13, поэтому 13 простое число.
• для p = 9, которое не является простым, не существует такого a , что a ^{(9-1) / 2} + 1 делится на 9.

Первые простые числа Proth (последовательность A080076 в OEIS ):

3, 5, 13, 17, 41 , 97 , 113 , 193 , 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153….

Наибольшее известное простое число протов по состоянию на 2016 год составляет 9 383761 цифру. Оно было обнаружено Питером Сабольчем в проекте распределенных вычислений PrimeGrid, о котором было объявлено 6 ноября 2016 года. Это также крупнейшее известное простое число, отличное от Мерсенна, и наибольшее число Кольбера. Второе по величине известное простое число протов - это семнадцать или бюст . ${\ displaystyle 10223 \ cdot 2 ^ {31172165} +1}$ ${\ displaystyle 19249 \ cdot 2 ^ {13018586} +1}$

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

Доказательство этой теоремы использует тест на простоту Поклингтона-Лемера и очень похоже на доказательство теста Пепина . Доказательство можно найти на странице 52 книги Рибенбойма в ссылках.

История

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

Смотрите также

• Тест Пепена (частный случай k  = 1, где выбирается a  = 3)
• Число Серпинского

использованная литература

внешние ссылки

• Вайсштейн, Эрик В. «Теорема Прота» . MathWorld .