Текст книги "Самая сложная задача в мире. Ферма. Великая теорема Ферма"

Автор книги: авторов Коллектив

сообщить о нарушении

Текущая страница: 4 (всего у книги 9 страниц)

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

Изначальный подход Уайлса основывался на теории Ивасавы, от которой он отказался, поскольку она не давала результатов, заменив ее так называемым методом Колывагина – Флаха. Интересно отметить, что теория Ивасавы возникла как обобщение работы Куммера. В математике есть связи, которые постоянны в истории.

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

Дело в том, что доказательство, изложенное Уайлсом в знаменитой серии лекций, прочитанных 23 июня 1993 года в Кембридже, было основано на его второй стратегии, Колывагина – Флаха, поскольку он отбросил за бесполезностью изначальный метод. Однако это доказательство было опровергнуто, поскольку в нем содержалась роковая ошибка.

Французский математик Огюстен Лум Кошм доказал теорему Ферма о прямоугольных числах в 1812 году.

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

Эндрю Уайлс опубликовал в 1994 году окончательное доказательство Последней теоремы Ферма.

Уайлс натолкнулся на ту же самую стену, что и Коши, Ламе, Куммер и Мияока. Все они были убеждены в своем успехе, однако были разбиты в самый последний миг. Этот последний шаг, эта последняя карта не давалась ни одному из математиков. И теперь, казалось, она не далась и Уайлсу. Так же как и предыдущим исследователям, Уайлсу было предназначено стать очередным именем в длинном ряду провалов, который длился 350 лет.

Но это не было очевидно в начале, когда математику устроили овацию в конце лекции. Ошибка всплыла при подготовке к публикации, во время очень серьезного процесса, известного как "рецензирование". Как правило, во время рецензирования формулируются вопросы и сомнения, на которые автор должен ответить. На одно из таких сомнений Уайлс ответить не смог. Его ошибку, которую нашел американский математик Ник Катц, невозможно объяснить неспециалисту. Согласно самому Уайлсу, даже профессиональному математику потребовалось бы два или три месяца, чтобы понять ее. В конце концов ученый был вынужден признать правоту Катца: он ошибся в такой тонкости, что ее было практически не видно.

Это и была цена самоизоляции Уайлса. Открытое обсуждение с коллегами хода исследования является одним из неписаных правил в математической практике. Подобное обсуждение позволяет обнаружить возможные ошибки, обсудить методы, сопоставить идеи. Но есть и обратная сторона: если кто-то тебе что-то подсказывает, в публикуемой статье ты должен вынести ему благодарность или даже включить в число соавторов. Вот почему такие статьи часто подписаны десятками авторов.

Проблема работы с Ферма – в том, что ты можешь провести годы, ничего не получив [...].

Эндрю Уайлс

Уайлс знал о риске, которому подвергался, но премия была слишком важна для него, и он не хотел с кем-то ею делиться. Так что математик решил рискнуть... и совершил ошибку. В любом случае, в доказательстве Уайлса было столько новаторства, что оно само по себе обладало ценностью. Так же как в случае с Коши или Куммером, его попытки уничтожить стену открыли дверь в новые миры. Но Уайлс не был готов сдаться. Поскольку секретничать уже не было смысла, он начал работать со своим коллегой Ричардом Тейлором, чтобы попытаться исправить ошибку. В конце концов он нашел решение. Хитрость заключалась в том, чтобы совместить метод Ивасавы, от которого он отказался, с методом Колывагина – Флаха. Уайлс решил задачу в день своего рождения. Вдруг все стало ясно, выключатель нашелся, и комната наполнилась светом. Через некоторое время, в мае 1995 года, состоялась публикация двух статей в журнале Annals of Mathematics, одна была подписана Уайлсом и Тейлором, а другая – только Уайлсом. Им обоим наконец-то удалось доказать одну из самых сложных задач всех времен. Небольшого книжного поля, действительно, было недостаточно для ста страниц доказательства, которое нашел Уайлс, основываясь, в свою очередь, на невероятных идеях Таниямы, Симуры, Фрая и Рибета. Стена наконец-то пала. Одна из самых долгих и сложных осад в истории математики закончилась победой осаждающих.

Из теоремы самой по себе нельзя было вывести никаких революционных результатов, но попытки ее доказательства дали огромное количество новых и плодотворных путей исследования. Возможно, если бы Эйлер не заинтересовался этой теоремой, теория чисел была бы разработана намного позже; теория идеалов была изначально задумана Куммером как инструмент доказательства теоремы, хотя сегодня она применяется во многих других областях. Фальтингс и Мияока исследовали связи между дифференциальной геометрией и теорией чисел благодаря Последней теореме Ферма. И наконец, Уайлс, возможно, не занялся бы доказательством гипотезы Таниямы – Симуры с таким пылом, если бы не знал о связи между этой гипотезой и любимой задачей его детства.

Всем этим мы обязаны скромному утверждению, или, даже можно сказать, всего лишь любопытному замечанию – теореме, которую однажды Ферма написал на полях "Арифметики" Диофанта.

ГЛАВА 3
Современная теория чисел

Несмотря на важность Великой теоремы Ферма для последующего развития математики, если бы она стала его единственным вкладом в науку, фигура тулузского юриста не обладала бы такой значимостью. Но Ферма был первоклассным математиком, для многих историков – мыслителем, равным Архимеду, Эйлеру или Гауссу. Он внес важный вклад в одну из своих любимых областей – современную теорию чисел, которую сам же и создал.

Собственные делители числа, или его аликвоты (включая число 1, которое всегда является делителем любого числа),– это делители, отличающиеся от самого числа, на которые оно делится без остатка. А совершенное число – это число, равное сумме всех своих собственных делителей.

Приведем пример. Собственными делителями числа 6 являются 1,2 и 3, а 1+2 + 3 = 6. Следовательно, 6 – это совершенное число, первое, но не единственное из этих чисел. Пифагорейцы придавали большое значение мистике совершенных чисел. В частности, 6 сочетало в себе три первых числа, которые имели важное мистическое значение (единство, двойственность и троица как смесь единства и двойственности); 6 – объединение всех этих значений.

Греки обнаружили только четыре первых совершенных числа: 6, 28, 496 и 8128. Пятое было открыто лишь в XV веке: 33 550 336. Найти совершенное число нелегко. В марте 2012 года было известно только 47 из них, самое большое из которых содержит 25956377 знаков.

Евклид известен как великий геометр, но, однако, меньше всего обращают внимание на то, что в его "Началах" содержится много арифметических теорем. Знаменитому греческому математику мы обязаны, например, знанием того, что количество простых чисел бесконечно. В области совершенных чисел он доказал удивительный результат (см. рисунок): пусть N = 2ⁿ(2ⁿ⁺¹ – 1) – 2ⁿM, где под М мы подразумеваем множитель 2ⁿ⁺¹ – 1 (М – одно из так называемых чисел Мерсенна, как мы увидим далее). Тогда, говорит нам Евклид, N – совершенное число, если М – простое.

Как можно легко заметить, все эти числа N четные. Мы пока не знаем, существуют ли нечетные совершенные числа. Это одна из больших открытых проблем в теории чисел. Однако известно, что если они существуют, то они должны соответствовать ряду очень сложных условий. Многие математики думают, что было бы чудом, если бы они существовали. Мы также не знаем, бесконечно ли количество чисел вида Ν, поскольку неизвестно, бесконечно ли количество простых чисел вида M, то есть простых чисел Мерсенна. Через несколько лет после смерти Ферма Эйлер доказал, что теорема, обратная теореме Евклида, верна: любое совершенное число можно записать в виде Ν.

Очевидно, что существуют несовершенные числа. Они делятся на два типа: избыточные (сумма их собственных делителей меньше самого числа) и недостаточные (меньше этой суммы).

Графическое представление совершенного числа.

ДОКАЗАТЕЛЬСТВО БЕСКОНЕЧНОСТИ ПРОСТЫХ ЧИСЕЛ

Данное доказательство принадлежит Евклиду, и оно осуществляется уже известным нам методом от противного. Предположим, что вывод ложен и количество простых чисел конечно. Это означает, что существует самое большое простое число. Назовем его p_n. Теперь составим число N из произведения всех простых чисел плюс один: N = p₁p₂... p_n-1 p_n + 1 = A_n + 1. Такое число не делится ни на одно простое число от p₁ до p_n, поскольку тогда на них должно было бы делиться как A_n, так и 1, и ясно, что ни одно число не является делителем 1, кроме него самого. То есть либо N – простое число, либо оно содержит простые множители, большие p_n. Следовательно, мы нашли простое число, большее p_n, что противоречит нашей гипотезе о том, что p_n – самое большое простое число. Получается, гипотеза ложна и количество простых чисел бесконечно.

Наконец, есть другие числа, тесно связанные с совершенными: так называемые дружественные числа. Два числа называются дружественными, когда сумма собственных делителей одного равна другому, и наоборот. В античности единственной известной парой дружественных чисел были 220 и 284. Действительно, собственные делители 220 – это 1,2,4,5,10,11,20, 22,44,55,110,а 284– 1 + 2 + 4+ 5+ 10 + 11 + 20 + 22 + 44 + 55 + 110. Аналогично, собственные делители 284 – это 1, 2, 4, 71, 142, а 220 – 1 + 2 + 4 + 71 + 142.

У этой пары дружественных чисел также было магико-мистическое значение. В Средние века верили, что если два человека съедят два куска хлеба, на каждом из которых написано одно из этих чисел, то они будут друзьями навсегда, даже если раньше не были знакомы.

Возрождение пифагорейского мистицизма в начале Нового времени поддерживало интерес к этим проблемам.

В книге "Трактат о всеобщей гармонии" Мерсенн утверждал, что Ферма открыл пару дружественных чисел, 17 296 и 18416, первую такую пару, обнаруженную со времен античности. Также, если верить данной книге, Ферма доказал, что как 120, так и 672 являются недостаточными числами, равными половине суммы их собственных делителей (эта сумма равна 240 и 1344 соответственно). Такие числа известны как мультисовершенные, или k-совершенные.

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

Комментарий Марена Мерсенна в книге «Трактат о всеобщей гармонии» (1636)

Итак, уже в 1636 году Ферма задумывался о том, как определить сумму собственных делителей заданного числа. На тот момент он уже явно знал, как это сделать. Его способ так и не был опубликован и сейчас утерян. Однако до нас дошел метод, которым мы обязаны Рене Декарту. Поскольку любое число может быть выражено в виде произведения степеней его простых множителей, N =p₁^k1p₂^k2...p_n^kn , собственные делители – это все возможные сочетания между данными множителями. Например, 1452 = 2² · 3 · 11², и его собственными делителями являются 2, 3, 11, 2², 11², 2 · 3, 2² · 3 и так далее, включая все сочетания. Декарт нашел формулу, которая на основе предыдущих результатов предлагала новый собственный делитель, пока все они не заканчивались. Это известно как рекурсивная формула. Метод Ферма явно аналогичный.

Математик получил несколько результатов на основе своего метода. Он послал Мерсенну пару решений, которые тот включил во вторую часть своей "Гармонии", опубликованной в 1637 году. Например, он предлагал общий метод нахождения дружественных чисел, подобный по структуре способу, который применял Евклид для нахождения совершенных чисел. Так, если три числа А = 3² · 2^2n-1, В = 3 · 2^n-1 и С = 3 х 2^n-1 – 1 простые, то 2ⁿА и 2ⁿВС дружественные. Обратите внимание на сходство данного результата с результатом Евклида о совершенных числах. Второй результат содержал подобную формулу для особого случая мультисовершенных чисел, которые являются третьей частью от суммы их собственных делителей. Рассуждение было аналогичным: если число некоего вида простое, то результат формулы – это число, дающее при умножении на 3 сумму собственных делителей. Ферма утверждал, что нашел подобные формулы для других мультисовершенных чисел, но они так и не стали известны.

У всех этих задач есть одна общая предпосылка: в каждой из них, прежде чем утверждать, можно считать число совершенным или пару чисел дружественными, или какое-то из них – мультисовершенным, нужно понять, являются ли некоторые числа определенной структуры простыми. Следовательно, нет ничего странного в том, что в переписке с Мерсенном в конце 1630-х годов Ферма все больше интересовало, существует ли способ установить, является ли число некоего вида простым.

МАЛАЯ ТЕОРЕМА ФЕРМА

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

В античности Диофант опубликовал свою знаменитую "Арифметику", от которой сохранилась приблизительно половина. Это не трактат, как "Начала" Евклида, а сборник более чем 100 задач на определенные (с одним или небольшим количеством уникальных решений) и неопределенные уравнения (с бесконечным числом решений). В изложении его задач нет системного подхода, их решение обычно дается целенаправленно, индивидуально для каждой проблемы. Метод решения излагается в каждом отдельном случае в качестве примера. Когда Диофант сталкивался с неопределенным уравнением, он довольствовался тем, что находил только одно решение, игнорируя существование других возможных.

Поскольку греки считали, что числа бывают только рациональными положительными, числа же вроде √2 были странными "чудовищами", которые появлялись лишь в геометрии, то Диофант давал решения только для признаваемых греками чисел. Итак, игнорирование возможных решений, связанных с нерациональными числами, было характерным для Диофанта и все еще было живо в XVII веке. Рациональные числа в целом неразложимы на простые множители. Греки знали это, но хотя они были знакомы с простыми числами, они не создали дисциплину, посвященную исключительно числам, которые действительно разложимы на простые множители, то есть натуральным числам. Такую дисциплину основал Ферма, и он был первым, кто понял, что натуральные числа заслуживают отдельного изучения, и первым, кто заложил основы этого изучения анализом свойств простых чисел.

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

Работы Ферма привлекли внимание математика по имени Бернар Френикль де Бесси (1605-1675), члена кружка Мерсенна. Френикль хотя и не обладал математическим гением Ферма, сделал впечатляющую догадку о свойствах очень больших чисел. Он, как и другие ученые, вел переписку с Ферма: она началась в 1640 году, длилась с перерывами и закончилась почти через 20 лет. Эти отношения, что вообще характерно для Ферма, были сложными. Однако Френикль, возможно, был человеком, который лучше всего понимал вклад этого ученого в теорию чисел.

РЕШЕТО ЭРАТОСФЕНА И ЕГО СЛОЖНОСТЬ

Решето Эратосфена – самый древний метод определения, является ли число N простым. Для этого составляется список всех чисел до Ν. Исходя из первого простого числа, 2, из данного списка вычеркиваются все числа, кратные 2, до Ν. Затем то же самое делается для первого невычеркнутого числа в списке, то есть 3, затем для 5, и так далее, пока не встречается число, наиболее близкое к √N. Каждое первое невычеркнугое число простое. Если в какой-то момент этого процесса будет вычеркнуто N, мы будем знать, что N – составное число. Наоборот, если удастся дойти до последнего простого числа, наиболее близкого к √N, то N – простое число. Очевидно, что данный способ громоздкий, поскольку требуется узнать все простые числа до √N. Похожий метод – перебор делителей, когда число делится на все простые числа до √N (полученные заранее) либо на два и все нечетные числа до √N, пока не будет найдено число, являющееся делителем N, или не закончится список.

Эффективность вычислений

Такие методы, как решето Эратосфена, могут быть более или менее сложными. Изучение эффективности алгоритма вычислений является одной из самых важных ветвей исследования в науке о вычислениях. Появляются неразрешимые проблемы, если не существует алгоритма, который мог бы дать ответ. При этом мы можем оценить, за какое максимальное время решается проблема при заданном алгоритме. Это можно обозначить как O(f(n)), где f(n) – любая функция от n, которая, в свою очередь, является мерой «размера» проблемы (например, это может быть число элементов в списке). Могут быть алгоритмы, обладающие сложностью: O(n), O(n²), O(log n), O(nlog n), O(eⁿ) и так далее. С другой стороны, существуют проблемы, которые хоть и разрешимы, но требуют столько времени, что нереально пытаться их решить. Это проблемы экспоненциальной сложности – O(eⁿ) – или, что еще хуже, комбинаторной сложности – O(n!): например, посчитать все перестановки п объектов. Они получают название неразрешимых проблем. Есть и другой очень интересный класс проблем: те, что могли бы быть неразрешимыми, но мы не знаем, так ли это. По сути это проблемы, для которых очень легко проверить верность решения, если оно известно, но нахождение решения кажется неразрешимой проблемой. Мы говорим «кажется», поскольку никто не смог доказать, так ли это. Они называются проблемами NP. Проблема разложения числа на простые множители – самый важный пример для нас. Наконец, существуют разрешимые проблемы: мы знаем, что они решаемы в разумное, известное как полиномиальное, время. Это проблемы порядка O(n^k), O(n log n) или O(log n). Решето Эратосфена – это алгоритм сложности Ο(10^√N), явно экспоненциальной.

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

Всегда, когда Ферма работал над проблемами, которые волновали его современников, его вклад разумно признавался. Но в теории чисел он был один. Он был пионером. Никто его не понимал, никто не мог объяснить, почему эти, казалось бы, тривиальные задачи, нигде не применимые, имеют какое-либо значение. То, что никто не обращал на него внимания, вызвало у Ферма огромную горечь, которая начала проявляться постепенно во все большей враждебности по отношению к современникам.

В переписке через Мерсенна Френикль бросил Ферма вызов, предлагая найти совершенное число из 20 знаков. Ответ от тулузского математика поступил немедленно: не существует такого числа, как и нет такого числа из 21 знака, и это, в свою очередь, доказывает, что гипотеза о существовании по крайней мере одного совершенного числа в каждом интервале между 10ⁿ и 10ⁿ⁺¹ ложная.

В один из тех редких случаев, когда Ферма показал некоторые из своих достижений, в ответе Френиклю в 1640 году он утверждал, что числа Мерсенна М = 2^p – 1 являются простыми, когда показатель степени – простое число. Также если n простое число, то n – делитель 2^n-1 – 1, и, наконец, если п простое число, то единственно возможные делители 2ⁿ – 1 имеют вид k(2n) + 1. Но, как обычно, Ферма не предоставил никакого доказательства.

Первый результат очень важен, поскольку он позволяет отбросить большое количество чисел Мерсенна в качестве кандидатов в простые числа. Второй и третий – сокращенные пути. Второй позволяет найти по крайней мере один делитель некоего числа Мерсенна (который может быть самим числом, что доказывает 2^3-1 – 1 = 3, являющееся делителем 3), а третий позволяет ограничить вид множителей другого числа Мерсенна, в связи с чем его поиск (и последующая проверка того, является число простым или составным) оказывается намного эффективнее: он ограничивается числами такого вида, исключая все остальные. Хотя Ферма не знал лучших методов поиска простых чисел, чем решето грека Эратосфена Киренского (276-194 до н. э.), он все же мог определить простоту некоторых чисел очень быстро, благодаря этим сокращенным путям.

ОБРАТНАЯ ТЕОРЕМА

Прямое доказательство теоремы идет от гипотезы и шаг за шагом приближается к выводу. Некоторые из данных шагов можно инвертировать, а другие нет. В целом шаг, содержащий импликацию, нельзя инвертировать. Рассмотрим это на бытовом примере. Можно сделать вывод, что тротуар мокрый, из того факта, что идет дождь, но мы не можем сделать вывод о том, что идет дождь, из того, что тротуар мокрый. Последнее могло произойти из-за обстоятельств, не связанных с дождем: например, воду пролила проехавшая автоцистерна или тротуар полили из обыкновенного шланга. Если идет дождь, то тротуар мокрый; но необязательно наоборот. Значит, тот факт, что идет дождь, – достаточное условие для того, чтобы тротуар был мокрым, но не необходимое. Такая однонаправленность присутствует, среди прочего, в малой теореме.

Ферма воспользовался третьим результатом, чтобы доказать, что не существует ни одного совершенного числа из 20 или 21 знака. Для начала он установил, что 2³⁷-1 – единственное число Мерсенна, которое может образовать по формуле Евклида совершенное число из 20 или 21 знака (это предполагает знание и принятие за справедливую теорему, обратную теореме Евклида, доказанную Эйлером несколько лет спустя). Затем он доказал, что данное число Мерсенна не является простым, поскольку делится на 223 = 3 · (2 · 37) +1, что как раз имеет вид k(2n) + 1. Действительно, вместо того чтобы вычислять огромное количество простых чисел, которые могли бы быть делителями 37-го числа Мерсенна, Ферма было достаточно постепенно попробовать числа к(2 · 37) + 1 для различных значений к. На третьей попытке он уже нашел ответ.

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

В том же 1640 году Ферма ознакомил с малой теоремой Френикля. Малая теорема Ферма применима только к простым числам. В ее современной формулировке в теореме говорится, что при заданных простом числе p и натуральном числе a, если p не является делителем a, то a^p-1 – 1 делится на p. Сначала не очень ясна значимость данной теоремы, однако она устанавливает основополагающее свойство этих кирпичиков, простых чисел, что влечет за собой очень интересные последствия.

Годфри Харди около 1912 года отмечал, что теория чисел не имеет практического применения. Тем не менее ситуация радикально изменилась, когда в 1977 году был разработан шифровальный алгоритм под названием RSA, который основан на разложении числа на два простых множителя (нахождение решения) и умножении двух множителей для получения числа (сверка решения).

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

РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ МЕТОДОМ ФЕРМА

Ферма изобрел метод разложения на множители исходя из того, что нечетное неквадратное число нельзя записать как N = х² – y², где

x = (n₁+n₂)/2 и e = (n₁-n₂)/2.

Можно легко доказать, что N = n₁n₂. Если N – простое число, то n₁ = N, а n₂ = 1. В противном случае n₁ и n₂ – собственные делители N. Поскольку n₁ и n₂ нечетные, так как N нечетное, то х и у – целые числа. Отсюда следует, что решение предыдущих уравнений для х и у предполагает возможность разложения N на множители. Для решения этого уравнения прибегают к проверкам, начиная с целого числа m, которое выполняет некое свойство, и, если оно не является решением, продолжают с помощью другого числа m', которое получается на основе m, и продолжают таким образом, пока не получают собственный делитель или не доходят до самого числа N. Разложение на множители методом Ферма может стать очень эффективным в некоторых случаях, поскольку числа т должны быть квадратными, и очень часто бывает легко определить, является ли число квадратным, просто посмотрев на него. Действительно, идеальные квадраты могут заканчиваться только на 0,1,4,5,9,16,36,56, 76 и 96, что исключает 90% окончаний. Красота данного метода в том, что в нем не требуется знания всех простых чисел до определенного числа и что если N – составное число и имеет множитель, близкий к √n, то это разложение на множители быстро его определяет.

Как бы то ни было, после всеобщего внедрения RSA и тесты простоты числа (первый шаг алгоритма – найти два огромных простых числа), и алгоритмы разложения на простые множители (которые в худшем случае могли бы разрушить надежность RSA) получили огромную практическую важность.

Итак, Ферма был озабочен проблемой нахождения простого числа. В качестве элементарной проверки, является ли данное число простым, можно задаться вопросом, выполняет ли заданное число требования малой теоремы Ферма; однако заметьте, что здесь речь идет, скорее, про обратную теорему. Следовательно, нет никакой гарантии того, что число окажется простым. Действительно, известно, что так называемые числа Кармайкла не выполняют обратную теорему. Но даже тогда этот тест является настолько простым и быстрым, что он используется при исполнении алгоритма RSA, чтобы быстро отбросить составные числа. Ведь на самом деле тест простоты, основанный на малой теореме Ферма, заключается в том, чтобы выяснить, является ли число составным. В довершение всего малая теорема Ферма также используется, чтобы доказать, что алгоритм RSA верен.

Другие тесты на простоту делятся на вероятностные и детерминированные. К первым относится тест Миллера – Рабина, который также основывается на малой теореме Ферма, или тест Соловея – Штрассена, основанный на теореме Эйлера, обобщающей малую теорему. Последний тест никогда не утверждает, что число простое, если это не так, но он менее успешен с составными числами. Действительно, существуют тесты, более эффективные в том, чтобы показать, что число составное, а другие больше подходят для доказательства того, что оно простое.

Детерминированное продолжение теста Миллера – Рабина основывается на недоказанном результате: расширенной гипотезе Римана. Очевидно, что его эффективность зависит от того, истинна ли эта гипотеза. Однако в 2002 году впервые было объявлено о тесте под названием AKS, который является универсальным (работает для любого числа), детерминированным, безусловным (не зависит от недоказанных результатов) и эффективным (с полиномиальной сложностью вычислений). Алгоритм AKS также основан на обобщении малой теоремы Ферма.

Важно отличать тесты простоты от алгоритмов разложения на множители. В то время как любой алгоритм разложения на множители скрывает в себе тест простоты, тесты простоты не предполагают обязательного разложения на множители. Например, решето Эратосфена не разлагает число на множители (хотя при тривиальном обобщении оно могло бы это делать), а тест, основанный напрямую на малой теореме Ферма, не находит даже ни одного множителя, в то время как перебор делителей действительно разлагает число. Следовательно, даже если и был найден эффективный алгоритм теста простоты, проблема разложения на множители продолжает быть достаточно сложной для того, чтобы алгоритм RSA оставался актуальным. Тест AKS не разлагает число на множители: операции в интернете остаются надежными.

Существует много других результатов, зависящих от малой теоремы. Один из самых известных – то, что мы все замечали: количество знаков после запятой в рациональном числе повторяется периодически, если в данном рациональном числе, выраженном несократимой дробью, знаменатель – простое число р, отличное от 2 и 5 (которые являются простыми множителями 10). Именно поэтому 1/3 – 0,33333..., а 1/7 – – 0,142857142857..., но 1/5 – 0,2, без периодического повторения. Предыдущие рассуждения служат для того, чтобы понять: малая теорема – один из самых важных результатов в теории чисел.

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

Замечание немецкого математика Курта Гензеля в своей книге «Теория чисел» (Zablentheorie, 1913).

Конечно же, Ферма, верный своей традиции, не оставил ни одного доказательства. Теорема была доказана Эйлером, который не знал, что Лейбниц несколькими годами ранее уже доказал ее, хотя результат был опубликован только в XIX веке.

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