Числа Прота — натуральні числа N виду ${\displaystyle N=k\cdot 2^{n}+1}$, де ${\displaystyle k}$ є непарним додатним цілим числом і ${\displaystyle n}$ — додатне ціле число, таке що ${\displaystyle k<2^{n))$. Без останньої умови числами Прота були б усі непарні цілі числа більші за 1^[1].

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

Перші числа Прота:

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] стверджує, що число Прота ${\displaystyle p}$ є простим, тільки якщо існує ціле ${\displaystyle a}$, для якого справедливе наступне порівняння:

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

Цю теорему можна застосовувати як імовірнісний тест простоти шляхом перевірки чи ${\displaystyle a^{\frac {p-1}{2))\equiv -1\ {\pmod {p))}$ для випадкових значень ${\displaystyle a}$. Якщо це не виконується для кількох випадкових ${\displaystyle a}$, то дуже ймовірно, що число ${\displaystyle p}$ є складеним. Так працює алгоритм Лас-Вегас: він ніколи не повертає хибно-позитивний результат, але може повертати хибно-негативний; іншими словами, він ніколи не повідомляє про складене число, що воно "ймовірно просте", але може повідомляти про просте число, що воно "можливо складене".

Станом на 2022 рік найбільшим відомим простим числом Прота було ${\displaystyle 10223\cdot 2^{31172165}+1}$^[3], яке містить 9 383 761 цифр. Його знайшов Петер Сабольч (Peter Szabolcs) у підпроєкті Seventeen or Bust проєкту добровільних обчислень PrimeGrid 31 жовтня 2016 року^[4]. До того ж воно є найбільшим відомим простим числом, що не є числом Мерсенна^[5].

Числа Каллена ${\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), то коли знайдено просте Прота, зазвичай одразу перевіряють, чи не ділить це просте якесь із чисел Ферма.

• Числа Каллена
• Числа Ферма
• Числа Мерсенна
• PrimeGrid