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

Коллектив авторов

Математик получил несколько результатов на основе своего метода. Он послал Мерсенну пару решений, которые тот включил во вторую часть своей "Гармонии", опубликованной в 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ⁿ⁺¹ ложная.