Ферма. Великая теорема Ферма

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

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

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

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

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