Число Прота

Число Прота — натуральное число вида:

${\displaystyle k\cdot 2^{n}+1}$,

где ${\displaystyle k}$ является нечётным положительным целым числом и ${\displaystyle n}$ — положительное целое число, причём ${\displaystyle k<2^{n}}$ (без последнего условия числами Прота были бы все нечётные целые числа больше 1[1]).

Названы в честь французского математика Франсуа Прота^[англ.] (1852—1879).

Первые числа Прота[2]:

3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, …

Наибольший интерес представляют простые числа Прота, первые таковые[3]:

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857, …

Простота чисел Прота может проверяться с помощью теоремы Прота[4], которая утверждает, что число Прота ${\displaystyle p}$ является простым, только если существует целое ${\displaystyle a}$, для которого справедливо следующее сравнение:

${\displaystyle a^{\frac {p-1}{2}}\equiv -1\ {\pmod {p}}}$.

На ноябрь 2016 года наибольшим известным простым числом Прота является ${\displaystyle 10223\cdot 2^{31172165}+1}$[5], обнаруженное Петером Сабольчем (Peter Szabolcs) в проекте добровольных вычислений Seventeen or Bust[6], притом оно же является крупнейшим известным простым числом, не являющееся числом Мерсенна[7].

Числа Каллена ${\displaystyle (n\cdot 2^{n}+1)}$ и числа Ферма ${\displaystyle (2^{2^{n}}+1)}$ представляют собой частные случаи чисел Прота.

Каждый делитель числа Ферма ${\displaystyle F_{n}}$ при ${\displaystyle n>2}$ может быть представлен в виде ${\displaystyle k\cdot 2^{n+2}+1}$ (Эйлер, Люка, 1878). Однако, неравенство ${\displaystyle k<2^{n+2}}$ здесь может не выполняться.

См. также

• Число Серпинского
• PrimeGrid — проект добровольных вычислений по поиску больших простых Прота

Примечания

1. Weisstein, Eric W. Proth Number (англ.) на сайте Wolfram MathWorld.
2. последовательность A080075 в OEIS
3. последовательность A080076 в OEIS
4. Weisstein, Eric W. Proth's Theorem (англ.) на сайте Wolfram MathWorld.
5. Chris Caldwell, The Top Twenty: Proth Архивная копия от 11 октября 2017 на Wayback Machine, Prime Pages
6. Press Release by Seventeen or Bust Архивная копия от 12 ноября 2016 на Wayback Machine. 31 October 2016.
7. Chris Caldwell, The Top Twenty: Largest Known Primes Архивная копия от 16 июля 2012 на Wayback Machine, Prime Pages