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

Простые числа Ферма — это простые числа, которые могут быть представлены в виде \( F_n = 2^{2^n} + 1 \), где \( n \) — неотрицательное целое число. Они названы в честь французского математика Пьера де Ферма, который в 1640 году выдвинул гипотезу, что все числа такого вида являются простыми. Впоследствии эта гипотеза была опровергнута: только пять первых чисел Ферма (для \( n = 0, 1, 2, 3, 4 \)) являются простыми, а для \( n \ge 5 \) все известные числа Ферма оказались составными. Простые числа Ферма играют важную роль в теории чисел, геометрии (в частности, в построении правильных многоугольников с помощью циркуля и линейки) и криптографии.

История

Гипотеза Ферма

В 1640 году Пьер Ферма в письме к Марену Мерсенну предположил, что числа вида \( 2^{2^n} + 1 \) всегда являются простыми. Он проверил это для \( n = 0, 1, 2, 3, 4 \), получив числа:

• \( F_0 = 2^{2^0} + 1 = 3 \)
• \( F_1 = 2^{2^1} + 1 = 5 \)
• \( F_2 = 2^{2^2} + 1 = 17 \)
• \( F_3 = 2^{2^3} + 1 = 257 \)
• \( F_4 = 2^{2^4} + 1 = 65537 \)

Все эти числа действительно являются простыми. Ферма не оставил доказательства своей гипотезы, и она оставалась недоказанной более ста лет.

Опровержение гипотезы

В 1732 году Леонард Эйлер показал, что число \( F_5 = 2^{2^5} + 1 = 4\,294\,967\,297 \) делится на 641, то есть является составным. Эйлер использовал метод, основанный на свойствах делителей чисел Ферма: любой простой делитель \( p \) числа \( F_n \) имеет вид \( p = k \cdot 2^{n+2} + 1 \). Для \( n = 5 \) это даёт \( p = 64k + 1 \), и перебором значений \( k \) он нашёл делитель 641. Таким образом, гипотеза Ферма была опровергнута.

Дальнейшие исследования

В XIX и XX веках были найдены делители для многих чисел Ферма с \( n \ge 5 \). На сегодняшний день (2025 год) известно, что все числа Ферма от \( F_5 \) до \( F_{32} \) являются составными, а для \( n \ge 33 \) полная простота не установлена, но ни одного нового простого числа Ферма не обнаружено. Поиск делителей чисел Ферма продолжается с помощью распределённых вычислительных проектов, таких как PrimeGrid.

Определение и свойства

Формальное определение

Числом Ферма называется число вида: \[ F_n = 2^{2^n} + 1, \] где \( n \ge 0 \). Простое число Ферма — это число Ферма, которое является простым. На данный момент известно только пять простых чисел Ферма: \( F_0, F_1, F_2, F_3, F_4 \).

Основные свойства

• Рекуррентное соотношение: Числа Ферма удовлетворяют рекуррентной формуле \( F_n = (F_{n-1} - 1)^2 + 1 \), что следует из определения.
• Взаимная простота: Любые два различных числа Ферма взаимно просты (не имеют общих делителей, кроме 1). Это свойство было доказано Эйлером и используется, например, в доказательстве бесконечности множества простых чисел.
• Делители: Если \( p \) — простой делитель \( F_n \), то \( p \equiv 1 \pmod{2^{n+2}} \). Это свойство сужает круг поиска делителей.
• Тест простоты: Для проверки простоты чисел Ферма используется тест Пепина (1877 год): число \( F_n \) (при \( n > 0 \)) является простым тогда и только тогда, когда \( 3^{(F_n - 1)/2} \equiv -1 \pmod{F_n} \). Этот тест эффективен для небольших \( n \), но для больших \( n \) требует огромных вычислительных ресурсов.

Классификация и известные примеры

Известные простые числа Ферма

Все пять известных простых чисел Ферма:

Эти числа являются единственными простыми числами Ферма, известными на 2025 год. Поиск новых простых чисел Ферма активно ведётся, но пока безуспешно.

Составные числа Ферма

Для \( n \ge 5 \) все числа Ферма, для которых удалось проверить простоту, оказались составными. Некоторые из них полностью факторизованы (например, \( F_5 \) до \( F_{11} \)), а для других известны лишь частичные делители. Например:

• \( F_5 = 2^{32} + 1 = 4\,294\,967\,297 = 641 \times 6\,700\,417 \)
• \( F_6 = 2^{64} + 1 = 18\,446\,744\,073\,709\,551\,617 = 274\,177 \times 67\,280\,421\,310\,721 \)

Применение

Геометрия: построение правильных многоугольников

Простые числа Ферма имеют прямое отношение к классической задаче построения правильных многоугольников с помощью циркуля и линейки. В 1796 году Карл Фридрих Гаусс доказал, что правильный \( n \)-угольник можно построить циркулем и линейкой тогда и только тогда, когда \( n \) является произведением степени двойки и различных простых чисел Ферма. Например:

• Правильный 17-угольник (соответствует \( F_2 \)) — построение было найдено Гауссом.
• Правильный 257-угольник (\( F_3 \)) — построение возможно, но крайне трудоёмко.
• Правильный 65 537-угольник (\( F_4 \)) — теоретически построим, но практическое построение не реализовано из-за сложности.

Это открытие стало одним из важнейших в геометрии и теории чисел, связав алгебраические и геометрические методы.

Криптография

Числа Ферма, в частности \( F_4 = 65\,537 \), используются в криптографии. Например, в алгоритме RSA часто выбирают открытую экспоненту \( e = 65\,537 \), так как это число является простым, имеет малый вес Хэмминга (в двоичной записи всего две единицы), что ускоряет операции возведения в степень. Однако использование чисел Ферма в криптографии не связано напрямую с их простотой — важны их арифметические свойства.

Теория чисел

Простые числа Ферма играют роль в доказательстве бесконечности простых чисел (через взаимную простоту чисел Ферма) и в изучении свойств простых чисел специального вида. Они также связаны с гипотезой о том, что множество простых чисел Ферма конечно — на данный момент это не доказано, но все известные данные указывают на то, что новых простых чисел Ферма не существует.

Критика и нерешённые проблемы

Гипотеза о конечности

До сих пор не доказано, что множество простых чисел Ферма конечно. Известно, что для \( n \ge 5 \) все проверенные числа Ферма составные, но для больших \( n \) (например, \( n = 33 \)) полная проверка простоты невозможна из-за колоссального размера числа (число \( F_{33} \) содержит более 2,5 миллиардов десятичных цифр). Поэтому вопрос о существовании шестого простого числа Ферма остаётся открытым.

Трудности проверки

Проверка простоты чисел Ферма с помощью теста Пепина требует возведения числа 3 в степень \( (F_n - 1)/2 \), что для \( n > 30 \) является вычислительно нереализуемой задачей на современных компьютерах. Поэтому для больших \( n \) исследования ограничиваются поиском малых делителей.

Связь с другими гипотезами

Простые числа Ферма связаны с гипотезой о том, что все числа Ферма бесквадратны (не содержат квадратов простых чисел). Это также не доказано, хотя для \( n \le 32 \) это свойство подтверждено.

Интересные факты

• Число \( F_4 = 65\,537 \) является самым большим известным простым числом Ферма. Оно часто используется в качестве примера в учебных курсах по теории чисел.
• В 2020 году в рамках проекта PrimeGrid был найден новый делитель для \( F_{12} \), но само число остаётся составным.
• Пьер Ферма ошибся в своей гипотезе, но его имя осталось в истории благодаря открытию важного класса чисел.