Том 3. Простые числа. Долгая дорога к бесконечности - [14]

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

Два числа называются взаимно простыми, если они не имеют общих делителей.

Например, 8 и 27 взаимно просты, так как не имеют общих делителей: 8 = 2³ и 27 = 3³ С другой стороны, 12 и 15 не являются взаимно простыми, так как у них есть общий делитель 3: 12 = 3 х 4, 15 = 3 х 5.

Таким образом, теорема утверждает, что для простого числа р и числа а, взаимно простого с р, разность (а^р  — а) делится на р.

Например, возьмем простое число 3 и число 8, которое не делится на 3. Тогда число 8³ — 8 = 512 — 8 = 504 делится на 3. И действительно, 504/3 = 168.

Можно сказать, что малая теорема Ферма — малая, да удалая (название «малая» впервые использовал в 1913 г. немецкий математик Курт Гензель), так как она наиболее часто используется в «тестах простоты», определяющих, является ли некое большое число простым.

Даже сам Ферма, скорее всего, пользовался ей для разложения больших простых чисел на множители. Известно, например, что ему удалось представить число 100 895 598169 в виде простых множителей 898 423 и 112 303 в ответ на вопрос Мерсенна, который хотел знать, является ли исходное число простым. Однако неясно, как Ферма мог работать с такими большими числами.

Теорема была впервые доказана Эйлером в 1736 г. У Лейбница было похожее доказательство, но он его не опубликовал. Гаусс также привел еще одно доказательство в своей знаменитой книге «Арифметические исследования», опубликованной в 1801 г. Эйлер позже нашел еще два доказательства. Самым простым является первое доказательство Эйлера, которое можно понять, имея лишь элементарные знания математики (см. Приложение).

* * *

КИТАЙСКАЯ ГИПОТЕЗА

Некоторые документальные источники подтверждают, что еще за две тысячи лет до Ферма математики из Поднебесной сформулировали так называемую «китайскую гипотезу», похожую на малую теорему Ферма. Эта гипотеза утверждает, что число р является простым числом тогда и только тогда, когда 2^Р — 2 делится на р. Китайская гипотеза, таким образом, является частным случаем малой теоремы Ферма. Однако обратное утверждение, что если это условие выполняется, то р будет простым, — неверно, поэтому в целом китайская гипотеза ошибочна.

* * *

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

Пусть р = 9 и а = 2, тогда 2⁹ — 2 = 510. Эта разность не делится на 9, и мы заключаем, что 9 не является простым числом, что и так очевидно. Польза этого простого метода заключается в том, что его можно применять для очень больших чисел.

Нужно отметить, что малая теорема Ферма содержит необходимое, но не достаточное условие: если р — простое число, то условие выполняется, но выполнение условия не означает, что р будет простым. Например, если взять р = 4 и а = 5, то 5⁴ — 5 = 620 делится на 4, но 4 = 2 х 2 является составным числом.

Числа Ферма

«Числами Ферма» называются натуральные числа вида:

Они обозначаются буквой F (по имени Ферма) с соответствующим индексом (n), так что F₀  обозначает первое число Ферма, F₁ — второе и так далее. Посчитаем значения первых пяти чисел Ферма, учитывая, что любое число в степени 0 равно 1:

2⁰  = 1; 2¹ = 2; 2² = 4; 2³ = 8.

Подставляя в формулу, получим:

Ферма предположил, что все числа, полученные таким способом, являются простыми. Первые пять чисел — 3, 5, 17, 257 и 65537 — действительно простые.

Но при n = 5 получается число:

Ферма не смог определить, является ли это число простым. Но Эйлеру в 1732 г. удалось представить это число в виде произведения двух множителей:

4294967297 = 641 х 6700417.

Тем самым Эйлер показал, что гипотезы Ферма могут быть ложными. Нечто подобное произошло впервые. И хотя гипотеза оказалась ошибочной, числа Ферма продолжают играть важную роль — не только потому, что благодаря им возникли новые идеи и гипотезы, но и потому, что они оказались полезными для выявления простых чисел.

В настоящее время известно, что только первые пять чисел Ферма являются простыми. Но это вовсе не означает, что других простых чисел Ферма не существует: на самом деле их может быть бесконечное множество. Разложение на множители было проделано лишь для чисел Ферма с индексом до n = 11. Представление числа в виде произведения простых множителей является нелегкой задачей. Как мы позже покажем, эта трудность лежит в основе одного из самых популярных методов шифрования, используемых сегодня.

Леонард Эйлер

Не существует ни одной области классической математики, будь то дифференциальное и интегральное исчисление, дифференциальные уравнения, аналитическая и дифференциальная геометрия, теория чисел или теория рядов, в которой бы не появлялось имя швейцарского математика и физика Леонарда Эйлера (1707–1783). Он был одним из самых плодовитых математиков своего времени. После его смерти в Санкт-Петербурге его сочинения продолжают вызывать восхищение и регулярно переиздаются Санкт-Петербургской Академией наук. Швейцарская академия наук планирует опубликовать полное собрание его работ, которое составит около 90 томов.