В теории чисел , Теорема Прот является тестом на простоту для Числа Прота .
В нем говорится , [1] [2] , что если р является число Proth , вида к 2 п + 1 с к нечетной и к <2 п , и если существует целое число , для которого
то р является премьер . В этом случае p называется простым числом Прота . Это практический тест, потому что, если p простое, любой выбранный a имеет примерно 50-процентную вероятность срабатывания.
Если a - квадратичный невычет по модулю p, то верно и обратное, и проверка окончательна. Такой может быть найдено итерацией над небольшими простыми числами и не вычислением символа Якоби до:
Таким образом, в отличие от многих тестов на простоту Монте-Карло (рандомизированные алгоритмы, которые могут возвращать ложные срабатывания ), алгоритм проверки простоты, основанный на теореме Прота, является алгоритмом Лас-Вегаса , всегда возвращающим правильный ответ, но с временем выполнения, которое изменяется случайным образом.
Числовые примеры
Примеры теоремы включают:
- для p = 3 = 1 (2 1 ) + 1 имеем, что 2 (3-1) / 2 + 1 = 3 делится на 3, поэтому 3 простое число.
- для p = 5 = 1 (2 2 ) + 1 имеем, что 3 (5-1) / 2 + 1 = 10 делится на 5, поэтому 5 простое число.
- для p = 13 = 3 (2 2 ) + 1 имеем, что 5 (13-1) / 2 + 1 = 15626 делится на 13, поэтому 13 простое число.
- для p = 9, которое не является простым, не существует такого, что a (9-1) / 2 + 1 делится на 9.
Первые простые числа Proth (последовательность A080076 в OEIS ):
Самый крупный известный Proth Prime по состоянию на 2016 год[Обновить] является и состоит из 9,383,761 цифры. [3] Оно было обнаружено Питером Сабольчем в проекте распределенных вычислений PrimeGrid, о котором было объявлено 6 ноября 2016 года. [4] Это также наибольшее известное простое число, отличное от Мерсенна, и наибольшее число Кольбера. [5] Второе по величине известное простое число Прота -, найденный Seventeen или Bust . [6]
Доказательство
Доказательство этой теоремы использует тест на простоту Поклингтона-Лемера и очень похоже на доказательство теста Пепина . Доказательство можно найти на странице 52 книги Рибенбойма в ссылках.
История
Франсуа Прот (1852–1879) опубликовал теорему в 1878 году. [7] [8]
Смотрите также
- Тест Пепена (частный случай k = 1, где выбирается a = 3)
- Число Серпинского
Рекомендации
- ^ Пауло Рибенбоим (1996). Новая книга рекордов простых чисел . Нью-Йорк, штат Нью-Йорк: Спрингер. п. 52 . ISBN 0-387-94457-5.
- ^ Ханс Ризель (1994). Простые числа и компьютерные методы факторизации (2-е изд.). Бостон, Массачусетс: Биркхаузер. п. 104 . ISBN 3-7643-3743-5.
- ↑ Крис Колдуэлл, Двадцать лучших: Прот , от Prime Pages .
- ^ "Обнаружен мировой рекорд числа Колберта!" .
- ^ Крис Колдуэлл, Двадцать лучших: наибольшие известные простые числа , от Prime Pages .
- ^ Колдуэлл, Крис К. «Двадцать лучших: наибольшие известные простые числа» .
- ^ Франсуа Прот (1878). «Теоремы о премьерах чисел». Comptes rendus de l'Académie des Sciences de Paris . 87 : 926.
- ^ Леонард Юджин Диксон (1966). История теории чисел . 1 . Нью-Йорк, Нью-Йорк: Челси. п. 92.
Внешние ссылки
- Вайсштейн, Эрик В. «Теорема Прота» . MathWorld .