Число Прота

В теории чисел число Прота, названное в честь математика Франсуа Прота (англ.), представляет собой число вида

$k \cdot 2^n+1$,

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

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

3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, … (последовательность A080075 в OEIS)

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

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

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, … (последовательность A080076 в OEIS)

Простота чисел Прота может проверяться с помощью теоремы Прота,^[2] которая утверждает, что число Прота p является простым, только если существует целое a, для которого справедливо следующее сравнение:

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

На июнь 2012 года наибольшим известным простым числом Прота является $19249 \cdot 2^{13018586} + 1$.^[3] Оно было обнаружено Константином Агафоновым в проекте распределённых вычислений Seventeen or Bust.^[4] Это также крупнейшее известное простое число, не являющееся числом Мерсенна.^[5]

Связь с другими числами специального вида

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

См. также

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

Примечания

1. ↑ Weisstein, Eric W. Proth Number (англ.) на сайте Wolfram MathWorld.
2. ↑ Weisstein, Eric W. Proth's Theorem (англ.) на сайте Wolfram MathWorld.
3. ↑ Chris Caldwell, The Top Twenty: Proth, Prime Pages.
4. ↑ Press Release by Seventeen or Bust. 5 May 2007.
5. ↑ Chris Caldwell, The Top Twenty: Largest Known Primes, Prime Pages.