Том 3. Простые числа. Долгая дорога к бесконечности - страница 18
Пусть р = 9 и а = 2, тогда 2>9 — 2 = 510. Эта разность не делится на 9, и мы заключаем, что 9 не является простым числом, что и так очевидно. Польза этого простого метода заключается в том, что его можно применять для очень больших чисел.
Нужно отметить, что малая теорема Ферма содержит необходимое, но не достаточное условие: если р — простое число, то условие выполняется, но выполнение условия не означает, что р будет простым. Например, если взять р = 4 и а = 5, то 5>4 — 5 = 620 делится на 4, но 4 = 2 х 2 является составным числом.
Числа Ферма
«Числами Ферма» называются натуральные числа вида:
Они обозначаются буквой F (по имени Ферма) с соответствующим индексом (n), так что F>0 обозначает первое число Ферма, F>1 — второе и так далее. Посчитаем значения первых пяти чисел Ферма, учитывая, что любое число в степени 0 равно 1:
2>0 = 1; 2>1 = 2; 2>2 = 4; 2>3 = 8.
Подставляя в формулу, получим:
Ферма предположил, что все числа, полученные таким способом, являются простыми. Первые пять чисел — 3, 5, 17, 257 и 65537 — действительно простые.
Но при n = 5 получается число:
Ферма не смог определить, является ли это число простым. Но Эйлеру в 1732 г. удалось представить это число в виде произведения двух множителей:
4294967297 = 641 х 6700417.
Тем самым Эйлер показал, что гипотезы Ферма могут быть ложными. Нечто подобное произошло впервые. И хотя гипотеза оказалась ошибочной, числа Ферма продолжают играть важную роль — не только потому, что благодаря им возникли новые идеи и гипотезы, но и потому, что они оказались полезными для выявления простых чисел.
В настоящее время известно, что только первые пять чисел Ферма являются простыми. Но это вовсе не означает, что других простых чисел Ферма не существует: на самом деле их может быть бесконечное множество. Разложение на множители было проделано лишь для чисел Ферма с индексом до n = 11. Представление числа в виде произведения простых множителей является нелегкой задачей. Как мы позже покажем, эта трудность лежит в основе одного из самых популярных методов шифрования, используемых сегодня.
Не существует ни одной области классической математики, будь то дифференциальное и интегральное исчисление, дифференциальные уравнения, аналитическая и дифференциальная геометрия, теория чисел или теория рядов, в которой бы не появлялось имя швейцарского математика и физика Леонарда Эйлера (1707–1783). Он был одним из самых плодовитых математиков своего времени. После его смерти в Санкт-Петербурге его сочинения продолжают вызывать восхищение и регулярно переиздаются Санкт-Петербургской Академией наук. Швейцарская академия наук планирует опубликовать полное собрание его работ, которое составит около 90 томов.
Банкнота 10 швейцарских франков 1997 г. выпуска с портретом Эйлера и изображениями гидравлической турбины, солнечной системы и света, проходящего через линзу. Все это иллюстрирует вклад Эйлера в математику.
Эйлер всегда проявлял особый интерес к простым числам. Он составил таблицу всех простых чисел от 1 до 100 000 и нашел формулы, которые позволяли ему получать невероятные количества таких чисел. Одной из наиболее интересных является следующая формула:
х>2+ х + q,
которая генерирует простые числа для любых значений х, больших 0 и меньших q — 2.
Эйлер нашел все такие простые числа для q = 2, 3, 5, 7, 11 и 17. В то время математика была экспериментальной, ее целью было получение практических результатов, поэтому строгие доказательства часто отсутствовали. Однако в отличие от Ферма Эйлер не скрывал своей работы. Если у него было доказательство, он публиковал его, а если факт приводился без доказательства, значит, оно не было найдено.
Работы Эйлера привели к важным изменениям в мире математики, вызвав медленный, но неумолимый сдвиг научной мысли. Среди многочисленных достижений Эйлера есть три, которые оказали решающее влияние на дальнейшие исследования в теории простых чисел: понятия функции, бесконечных сумм и мнимых величин.
Позже мы еще вернемся к ним.
Функции
Эйлер заложил основы того, что в последующие века будет называться математическим анализом. Именно он ввел обозначение функции,