Теорема прота - Proths theorem - Wikipedia

В теория чисел, Теорема прота это тест на простоту за Числа прот.

Говорится[1][2] что если п это Proth число, формы k2п + 1 с k странно и k < 2п, и если существует целое число а для которого

тогда п является основной. В этом случае п называется Proth Prime. Это практический тест, потому что если п прост, любой выбранный а шанс сработать составляет около 50 процентов.

Если а это квадратичный невычет по модулю п тогда верно и обратное, и проверка окончательна. Такой а можно найти, повторяя а над малыми простыми числами и вычисляя Символ Якоби до того как:

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

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

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

  • за п = 3 = 1(21) + 1, имеем 2(3-1)/2 + 1 = 3 делится на 3, поэтому 3 простое число.
  • за п = 5 = 1(22) + 1, имеем 3(5-1)/2 + 1 = 10 делится на 5, поэтому 5 простое число.
  • за п = 13 = 3(22) + 1, имеем 5(13-1)/2 + 1 = 15626 делится на 13, поэтому 13 простое число.
  • за п = 9, что не является простым, нет а такой, что а(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 ….

Самый крупный из известных Proth Prime по состоянию на 2016 год является , и состоит из 9,383,761 цифры.[3] Он был найден Петером Сабольчем в PrimeGrid проект распределенных вычислений который объявил об этом 6 ноября 2016 года.[4] Это также самый крупный известный не-Мерсенн прайм и наибольшее число Кольбера.[5] Второе по величине известное простое число протов - это , найдено Семнадцать или бюст.[6]

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

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

История

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

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

Рекомендации

  1. ^ Пауло Рибенбойм (1996). Новая книга рекордов простых чисел. Нью-Йорк, штат Нью-Йорк: Спрингер. п.52. ISBN  0-387-94457-5.
  2. ^ Ханс Ризель (1994). Простые числа и компьютерные методы факторизации (2-е изд.). Бостон, Массачусетс: Birkhauser. п.104. ISBN  3-7643-3743-5.
  3. ^ Крис Колдуэлл, Двадцатка лучших: Proth, от Prime Pages.
  4. ^ "Обнаружен мировой рекорд числа Колберта!".
  5. ^ Крис Колдуэлл, Двадцать лучших: наибольшие известные простые числа, от Prime Pages.
  6. ^ Колдуэлл, Крис К. «Двадцать лучших: наибольшие известные простые числа».
  7. ^ Франсуа Прот (1878). "Теоремы о премьерах чисел". Comptes rendus de l'Académie des Sciences de Paris. 87: 926.
  8. ^ Леонард Юджин Диксон (1966). История теории чисел. 1. Нью-Йорк, Нью-Йорк: Челси. п. 92.

внешняя ссылка