Простые числа Ферма: 2^(2^m)+1

14 July 2020
Пьер Ферма (1601-1665)
Пьер Ферма (1601-1665)

Свой рассказ о видах Простых чисел я решил начать с чисел Ферма. Это последовательность вида Fm = 2^(2^m) +1, имеет номер A000215 в Энциклопедии числовых последовательностей (OEIS). Дело в том, что в ней используется показательная функция. Если квадраты, кубы и более высокие степени (т.е. переменная в степени константа) были известны с древних времен, то показательная функция (т.е. константа/переменная в степени переменная) формально была введена Лейбницем только в 1695 году!

Во многом благодаря этому, математики получили возможность перейти к рассмотрению свойств гораздо больших чисел, т.к. до этого они были ограничены арифметической операцией "Умножение". Теперь же у них появился способ для компактного представления выражения с большим количеством ее повторений: a*a*a*...*a ⇒ a^n

Итак, Пьер Ферма (1601-1665) был математиком-самоучкой, и внес огромный вклад в формирование и развитие ряда математических дисциплин. Особенно много внимания он уделял Теории чисел. Весьма вероятно, что изначально его взгляд привлекла последовательность вида Fn = 2^n +1. Возможно, предпосылкой его интереса стала древняя задача-притча о шахматной доске и удваивающихся рисовых зернышках на каждой последующей клетке, этого уже не узнать.

Довольно быстро выяснилось, что почти все числа вида (2^n +1) являются составными. Действительно, если n = p*q при p и q > 0, то число сразу раскладывается на сомножители:

(2^n +1) = (2^p*q +1) = (2^p +1) * (2^q +1) * (...)

И только в случае n = 2^m картина становилась неординарной:

F0 = 2^(2^0) +1 = 2^1 +1 = 3 - Простое число!

F1 = 2^(2^1) +1 = 2^2 +1 = 5 - Простое число!

F2 = 2^(2^2) +1 = 2^4 +1 = 17 - Простое число!

F3 = 2^(2^3) +1 = 2^8 +1 = 257 - Простое число!

F4 = 2^(2^4) +1 = 2^16 +1 = 65537 - Простое число!

Хотя такой ряд и демонстрировал крайне быстрый рост (F5 = 2^32 +1 = 4294967297 - уже целых 10 цифр), но давал значительную надежду на сохранение закономерности.

Есть мнение, что сформулировав Малую Теорему Ферма (a^(p-1) -1 делится без остатка на p), Пьер применил ее для чисел p = 2^(2^m) +1 и увидел, что это условие всегда соблюдается. На такой волне оптимизма он и выдвинул гипотезу, что все такие числа и дальше будут являться Простыми. Лишь в 1732 Эйлер разложил следующее число на сомножители: F5 = 4294967297 = 641*6700417

С этого момента начался интенсивный поиск делителей, насколько это позволяли ручные методы расчетов. Всего за 312 лет (1640-1952) удалось найти лишь 16 делителей. Продвигаться вперед также помогало доказательство Люка в 1878 году, что все делители Fm = 2^(2^m) +1 должны иметь вид k*2^(m+2) +1.

В 1953 году началась компьютерная эпоха: Джон Селфридж запустил вычислительную программу на ЭВМ и... нашел 2 новых делителя! После этого наступило затишье на годы.

Следующим искателем стал Рафаэль Робинсон: в 1956-57 годах он нашел 20 новых делителей! И снова тишина на еще более долгий срок!

В последующие 2 десятилетия результаты были скромнее - в какие-то годы случался неожиданный всплеск, и снова все затихало.

Лишь начиная с 1976 года пошел ежегодный поток новых находок (кроме 1989 года). Абсолютный рекорд был поставлен в 2001 году (22 делителя) - во многом благодаря Леониду Дурману (читайте его статьи в Компьютерре - 1, 2, 3).

Помимо разложения, простоту чисел Ферма без известных множителей пробовали проверять с помощью теста Пепина. В 1999 году он проводился в последний раз - на многокомпьютерной вычислительной системе в течение 200 дней проверялось число F24. Результат оказался отрицательным - оно явно составное.

У чисел F25, F26, F27, F28, F29, F30 и F32 на тот момент уже были известны делители. В 2001 году Александр Круппа и Тони Форбс нашли делитель у F31. Это был своего рода финальный аккорд - следующим числом без известных делителей является F33 - потенциальный кандидат в Простые, но протестировать его с помощью теста Пепина у Человечества не предвидится технических возможностей в обозримом будущем.

Далее - только искать все новые и новые делители, отсеивая составных кандидатов. В настоящее время удается находить в среднем по 5-7 новых делителей в год. На июль 2020 года их уже насчитывалось 353 шт. А существует ли еще хотя бы одно Простое число Ферма - науке неизвестно!

В целом, ситуация стабилизировалась на такой картине:

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

F0 = P1 - Простое число из 1 цифры!

F1 = P1 - Простое число из 1 цифры!

F2 = P2 - Простое число из 2 цифр!

F3 = P3 - Простое число из 3 цифр!

F4 = P5 - Простое число из 5 цифр!

Разложены на множители полностью:

F5 = 641 * P7 - Здесь и далее указываю только младший делитель!

F6 = 274177 * P14

F7 = 59649589127497217 * P22

F8 = 1238926361552897 * P62

F9 = 2424833 * P49 * P99

F10 = 45592577 * P10 * P40 * P252

F11 = 319489 * P6 * P21 * P22 * P564

Разложены на множители частично или точно составные:

F12 = 114689 * P8 * P8 * P12 * P16 * P54 * C1133

F13 = 2710954639361 * P19 * P19 * P27 * C2391

F14 = ??? * 116928085873074369829035993834596371340386703423373313 * C4880

F15 = 1214251009 * P16 * P33 * C9808

F16 = 825753601 * P27 * C19694

F17 = 31065037602817 * P49 * C39395

F18 = 13631489 * P23 * C78884

F19 = 70525124609 * P12 * P35 * C157770

F20 = C315653

F21 = 4485296422913 * C631294

F22 = ??? * 64658705994591851009055774868504577 * C1262577

F23 = 167772161 * C2525215

F24 = C5050446

F14 и F22 - неизвестно, есть ли меньшие делители

F20 и F24 - составные, но нет известных делителей

Напоминаю обозначения:

Px - точно Простое число из x цифр

Cx - точно составное число из x цифр

Nx - неизвестно, Простое или составное число из x цифр

В нашей истории не обошлось и без курьезов: в 1996 году Ричард Гай и Джон Конвей (авторы книги «The Book of Numbers») поспорили на $20, что за следующие 20 лет ни одно число Ферма (F12 и более) не удастся разложить на множители полностью. За 3 года до истечения срока Ричард Гай забеспокоился, и обратился к Сообществу с просьбой активизировать усилия в разложении чисел F12 и F13, как наиболее перспективных кандидатов. Пообещал даже отдать эти $20 тому, кто сумеет разложить одно из этих чисел. Но в итоге подошел срок - 30 сентября 2016 года, новых полных разложений чисел Ферма так и не появилось, и Джон Конвей победил!

Читайте также:

Делители чисел Ферма >>>

Ссылки по теме:

Страница "хранителя" делителей чисел Ферма - Вилфрида Келлера >>>

Координирующий проект по поиску делителей чисел Ферма >>>

Раздел форума с обсуждением вопросов поиска делителей >>>

Оглавление - все мои публикации о Простых числах >>>

Пишите в комментариях, если тоже хотите поучаствовать в совместных поисках Простых чисел!