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

31

О. Оре

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

Вероятно, одним из первых свойств чисел, открыты люdbми, был тот факт, что некоторые числа раскладываются на два меньших множители, например
$$6=2\cdot 3, 9=3\cdot 3, 30=2\cdot 15=3\cdot 10,$$
в то время как другие, например
$$3, 7, 13, 37,$$
на множители подобным образом не раскладываются.

Если число $c$ является произведением двух чисел $a$ и $b$ ($c=a\cdot b$), мы называем числа $a$ и $b$ множегелями или делимелями числа $c$. Каждое число имеет привальное (простейшее) разложение на множители:
$$c=1\cdot c=c\cdot 1.$$
Соответственно числа 1 и $c$ мы называем множегелями делимелями числа $c$.

Эта статья является открытом из книги О. Оре «Приглашение в теорию чисел», выходящей в 1980 г. в Библотечеке «Квант» (перевод Л. Савиной под ред. А. Савина).

Любое число $c>1$, у которого существует нетривиальное разложение на множители, называется составным. Если число, большее единицей, имеет только тривиальное разложение на множители, то оно называется простым. Среди первыхста чисел простыми являются следующие 25 чисел:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, а все остальные числа, кроме 1, являются составными.

За последние 200 лет было издано много таблиц простых чисел. Наноблее обширной из них является таблица Д. Н. Лехмера, содержащая все простые числа до 10000000.

Некоторые энтузинасты составили таблицы простых чисел, превозходящих 10000000, однako, по-видимому, нет большего смысла публиковать эти таблицы. Лишь в очень редких случаях математику, даже специальную по теории чисел, приходит решать вопрос, является ли какое-то большее число простым. Кроме того, большее число, о которых математик хочет узнать, является ли они простыми или составными, не возникают произвольно. Они обычно появляются в специальных математических задачах и поэтому имеют очень специфичную форму.

32

Рассскажем об одном из типов простых чисел, имеющим большую и интерсную историю. Эти числа впервые были введены Пьером Ферма (1601—1665), французским юристом, который был одновременно и выдающимся математиком *). Первые пятью простыми числами Ферма являются

$$F_0 = 2^{20} + 1 = 3, \quad F_1 = 2^{21} + 1 = 5, \quad F_2 = 2^{22} + 1 = 17, \quad F_3 = 2^{23} + 1 = 257, \quad F_4 = 2^{24} + 1 = 65537.$$

В соответствии с этой последовательностью общая формула для простых чисел Ферма должна иметь вид

$$F_n = 2^{2n} + 1.$$

Ферма был абсолотно уверен, что все числа такого вида являются простыми, хотя он не вычислил других чисел, кроме указанных пяты. Но после того, как Леонард Эйлер сделал еще один шаг, показав, что следующее число Ферма:

$$F_5 = 4294967297 = 641 \cdot 6700417$$

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

Правильным многоугольником называется многоугольник, вершины которого лежат на некоторой окружности на одинаковых расстояниях друг от друга (см. рисунок). Если у правильного многоугольника $n$ вершин, то мы называем его правильным $n$-угольником. Если мы проведем $n$ радиусов, соединяющих центр окружности с вершинами, то получим $n$ центральных углов величиной $\frac{1}{n} \cdot 360^\circ$ каждый. Если можно построить угол, имеющий эту величины, то можно построить и сам многоугольник.

Древние греки очень наутил методы построения правильных многоугольников с помощью циркуля

*) См. «Квант», 1976, № 8 (прим. ред.).

Леонард Эйлер (1707—1783).

ля и линейки. Разумеется, они умелистроить простые из них — равносторонний треугольник и квадрат. С помощью повторного деления пополам центрального угла они могли также построить правильные многоугольники с

8, 16, 32, …
6, 12, 24, …
вершинами. Кроме того, они умелистроить правильный пятуугольник и, следовательно, также правильные многоугольники с

10, 20, 40, …
вершинами. Был также получен еще один тип правильного многоугольника. Центральный угол в правильном 15-угольнике равен

$$\frac{1}{15} \cdot 360^\circ = 24^\circ,$$

33

Карл-Фридрих Гаусс (1777—1855).

и он может быть получен с помощью угла в 72°, соответствующего правильному пятугольнику, и угла в 120°, соответствующего правильному треугольнику, если удовлетворяющий угол и вычесть из него второй. Следовательно, мы можем построить правильные многоугольники с 15, 30, 60, 120, … сторонами.

В таком состоянии проблема оставалась до 1801 года. В том году молодой немецкий математик Карл-Фридрих Гаусс (1777—1855) опубликовал работу по теории чисел «Арифметические исследования». Эта работа открыла новую эпоху в математике. В ней Гаусс превозшел греческий геометров не только тем, что указыл метод для построения циркulum и линейной правильного 17-угольника — он пошел горздо дальше. Для всех чисел $n$ он определил, какие $n$-угольники могут быть построены таким образом, а какие нет. Сейчас мы опишем результаты, полученные Гауссом.

Мы уже говорили, что, для каждой центральной угол пополам, из правильного $n$-угольника можно получить правильный $2n$-угольник. С другой стороны, из $2n$-угольника можно получить $n$-угольник, использую лишь каждую вторую вершину. Это показывает, что достаточно провести понок многоугольников, которые могут быть построены с помощью циркуля и линейки, только среди многоугольников с нечетным числом вершин. Гаусс показал, что правильный многоугольник с нечетным числом вершин может быть построен с помощью циркуля и линейки, только среди многоугольников с нечетным числом вершин. Для $n=11$ и $n=13$ соответствующей $n$-угольник не может быть построен, но он может быть построен для $n=15=3.5$ и $n=17$.

Открытие Гаусаса, естественно, возникло интерес к числам Ферма. За последнее столетие были предложены понки «вручную», без помощи maшин, новых простых чисел Ферма. В настоящее время эти вычисления ведутся со все возможной скоростью при помощи ЭВМ, однокто до сих пор результаты были отрицательными. Ни одного нового простого числа Ферма пока не найдено. И сейчас многое математики склонны считать, что их больше нет.

Задание

1. Найдите все нечетные числа $n<100$, для которых можно построить правильный $n$-угольник.
2. Как построить правильный 51-угольник, имея правильный 17-угольник?
3. Если не существует простых чисел Ферма, кроме вышеуказанных пятей, то сколько существует правильных $n$-угольников ($n$ нечетно), которые могут быть построены циркуля и линейкой? Каково наиболее нечетное $n$, для которого можно построить правильный $n$-угольник?