Числа Прота

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

Названі на честь французького математика Франсуа Прота (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)

Тест на простоту

Досі залишається відкритим питання, чи скінчена множина простих чисел Прота. Простоту чисел Прота перевірити легше, ніж багатьох інших чисел подібного розміру. Теорема Прота стверджує, що число Прота $p$ є простим, тільки якщо існує ціле $a$, для якого справедливе наступне порівняння:

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

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

Великі прості Прота

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

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

Оскільки кожен дільник числа Ферма $F_{n}$ при $n>2$ завжди має бути виду $k\cdot 2^{n+2}+1$ (Ейлер, Люка, 1878), то коли знайдено просте Прота, зазвичай одразу перевіряють, чи не ділить це просте якесь із чисел Ферма.

Див. також

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