§ 10.2. Числа Ферма

Мы уже видели, что если число простое, то тоже простое. Это соображение наводит на мысль попытаться поискать значения при которых выражение будет давать простые числа. Предположив, чтор простое, получим

Следовательно,

Таким образом, по ключевой лемме порядок элемента 2 группы делит Как и в предыдущей ситуации, мы должны точно вычислить этот порядок. Из равенства (2.1) вытекает, что порядок элемента 2 не может ни равняться ни быть его делителем. Но он все же делит поэтому искомый порядок должен быть четным, т.е. равным при каком-то натуральном Очевидно, делит число

Теперь, по определению порядка, что можно переписать в виде равенства в

По нашему предположению простое число. Значит

Следовательно, делит одно из чисел: или Но ввиду соотношений: такое возможно только если т. е. порядок элемента 2 группы равен

В силу равенства из теоремы Ферма вытекает, что

Поэтому порядок элемента 2 (а он равен ) делит число . В частности, должно быть степенью двойки. Итак, если число простое, то какая-то степень двойки.

Именно по этой причине в поисках простых мы ограничиваемся числами вида , т. е. числами Ферма. Как уже было замечено в главе 4, Ферма полагал, что все такие числа простые. Это верно для при Однако в 1730 году Эйлер показал, что число составное. Как ни странно, метод Эйлера близок способу самого Ферма, который тот использовал для поиска делителей чисел Мерсенна (мы его описали в § 10.1). Посмотрим, как работает метод Эйлера.

Предположим, что простой делитель числа Тогда

и, по ключевой лемме, порядок элемента 2 делит Но то же уравнение гарантирует, что этот порядок не может быть степенью двойки с показателем меньше к Значит, порядок элемента 2 в группе в точности равен Далее, по теореме Ферма порядок элемента 5 должен быть делителем числа так что

Метод Эйлера. Если простой делитель числа то найдется такое натуральное что

Опираясь на метод Эйлера, найдем делитель числа Прежде всего, любой такой простой делитель представляется в виде Таким образом, нам нужно определить, есть ли среди натуральных чисел

представимых в виде делители числа Ограничение на дает оценку ; к сожалению, работать с такой большой границей неудобно.

Наименьшее значение при котором число простое, равно 3, что соответствует Вычисления показывают:

Следовательно, 193 не делит число При мы имеем тоже простое число, но

т.е. 257 также не является искомым делителем. Следующее значение при котором будет простым, это причем И опять мимо:

Следующее простое что соответствует В этом случае

т.е. 577 не делит Наконец, дает долгожданный делитель числа

Нам еще повезло, что делитель оказался относительно маленьким, и все необходимые вычисления при его поиске можно выполнить на электронном калькуляторе. Эйлер, естественно, проделал их вручную. К сожалению, такая удача выпадает нечасто. Проблема в том, что является дважды показательной функцией. Поэтому даже для относительно небольших значений к поиск делителей приходится производить среди очень большого количества кандидатов, что практически невозможно осуществить методом Эйлера. Однако найти делитель конкретного числа Ферма можно более удобными методами (см. [33] и [37]). Более того, есть весьма эффективный тест, определяющий, является ли данное число Ферма простым или составным. Этим тестом мы займемся в следующей главе.

О числах Ферма известно довольно много. Например, выписаны разложения на простые множители чисел и всех при Кроме того, найден по крайней мере один делитель для каждого из чисел при к 32, за исключением 22, 24, 28 и 31. Получается, что среди чисел Ферма,

которые мы знаем, простыми являются только и возникает предположение, что других простых среди чисел Ферма нет.

Почему же числа Ферма привлекают столь большое внимание? Есть несколько причин, и конечно же не последняя среди них — наполненная драматическими событиями история этих чисел. Кроме того, они служат хорошим источником трудных для разложения на множители больших чисел, что делает их прекрасным объектом для испытания возможностей новых алгоритмов. Алгоритмы разложения, в свою очередь, часто требуют от компьютера огромного числа повторяющихся простых арифметических и логических операций. Поэтому их прогонка на вновь создаваемых компьютерах довольно эффективно помогает выловить недочеты в конструкции.

Числа Ферма интересны и с теоретической точки зрения. В 1801 году Гаусс показал, что если правильный -угольник можно построить с помощью циркуля и линейки, то равно некоторой степени двойки, умноженной на простое число Ферма. В частности, правильный -угольник можно построить таким образом, поскольку а начертить правильный семиугольник, используя только циркуль и линейку, не удастся, так как 7 не является числом Ферма. Интересующиеся этой проблемой могут обратиться к [6] ([Д.13]).