Читаем без скачивания Самая сложная задача в мире. Ферма. Великая теорема Ферма - Коллектив авторов

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

Работы Ферма привлекли внимание математика по имени Бернар Френикль де Бесси (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(n2), O(log n), O(nlog n), O(en) и так далее. С другой стороны, существуют проблемы, которые хоть и разрешимы, но требуют столько времени, что нереально пытаться их решить. Это проблемы экспоненциальной сложности — O(en) — или, что еще хуже, комбинаторной сложности — O(n!): например, посчитать все перестановки п объектов. Они получают название неразрешимых проблем. Есть и другой очень интересный класс проблем: те, что могли бы быть неразрешимыми, но мы не знаем, так ли это. По сути это проблемы, для которых очень легко проверить верность решения, если оно известно, но нахождение решения кажется неразрешимой проблемой. Мы говорим "кажется", поскольку никто не смог доказать, так ли это. Они называются проблемами NP. Проблема разложения числа на простые множители — самый важный пример для нас. Наконец, существуют разрешимые проблемы: мы знаем, что они решаемы в разумное, известное как полиномиальное, время. Это проблемы порядка O(nk), O(n log n) или O(log n). Решето Эратосфена — это алгоритм сложности Ο(10√N), явно экспоненциальной.

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

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

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

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

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

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

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