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

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

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

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

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

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