У всех этих задач есть одна общая предпосылка: в каждой из них, прежде чем утверждать, можно считать число совершенным или пару чисел дружественными, или какое-то из них — мультисовершенным, нужно понять, являются ли некоторые числа определенной структуры простыми. Следовательно, нет ничего странного в том, что в переписке с Мерсенном в конце 1630-х годов Ферма все больше интересовало, существует ли способ установить, является ли число некоего вида простым.
Ферма понял, что основная задача теории чисел заключается в изучении простых чисел, проблемы разложения на простые множители и проблемы простоты числа (то есть определения, является ли число простым). Такое понимание делает его отцом современной теории чисел.
В античности Диофант опубликовал свою знаменитую "Арифметику", от которой сохранилась приблизительно половина. Это не трактат, как "Начала" Евклида, а сборник более чем 100 задач на определенные (с одним или небольшим количеством уникальных решений) и неопределенные уравнения (с бесконечным числом решений). В изложении его задач нет системного подхода, их решение обычно дается целенаправленно, индивидуально для каждой проблемы. Метод решения излагается в каждом отдельном случае в качестве примера. Когда Диофант сталкивался с неопределенным уравнением, он довольствовался тем, что находил только одно решение, игнорируя существование других возможных.
Поскольку греки считали, что числа бывают только рациональными положительными, числа же вроде √2 были странными "чудовищами", которые появлялись лишь в геометрии, то Диофант давал решения только для признаваемых греками чисел. Итак, игнорирование возможных решений, связанных с нерациональными числами, было характерным для Диофанта и все еще было живо в XVII веке. Рациональные числа в целом неразложимы на простые множители. Греки знали это, но хотя они были знакомы с простыми числами, они не создали дисциплину, посвященную исключительно числам, которые действительно разложимы на простые множители, то есть натуральным числам. Такую дисциплину основал Ферма, и он был первым, кто понял, что натуральные числа заслуживают отдельного изучения, и первым, кто заложил основы этого изучения анализом свойств простых чисел.
Простые числа — это кирпичи, из которых строятся все натуральные. Уже было рассмотрено несколько примеров, в которых важно, чтобы некая величина была простым числом. Но есть много других результатов, в которых все основывается на простых числах, поскольку исследование свойств этих кирпичиков позволяет делать утверждения, которые нельзя было бы сделать о натуральном числе в целом. У простых чисел есть интересные свойства, которыми не обладают составные (не простые) числа; следовательно, рассуждать о них и выводить свойства составных чисел на их основе — обычная стратегия в теории чисел.
Работы Ферма привлекли внимание математика по имени Бернар Френикль де Бесси (1605-1675), члена кружка Мерсенна. Френикль хотя и не обладал математическим гением Ферма, сделал впечатляющую догадку о свойствах очень больших чисел. Он, как и другие ученые, вел переписку с Ферма: она началась в 1640 году, длилась с перерывами и закончилась почти через 20 лет. Эти отношения, что вообще характерно для Ферма, были сложными. Однако Френикль, возможно, был человеком, который лучше всего понимал вклад этого ученого в теорию чисел.
Решето Эратосфена — самый древний метод определения, является ли число N простым. Для этого составляется список всех чисел до Ν. Исходя из первого простого числа, 2, из данного списка вычеркиваются все числа, кратные 2, до Ν. Затем то же самое делается для первого невычеркнутого числа в списке, то есть 3, затем для 5, и так далее, пока не встречается число, наиболее близкое к √N. Каждое первое невычеркнугое число простое. Если в какой-то момент этого процесса будет вычеркнуто N, мы будем знать, что N — составное число. Наоборот, если удастся дойти до последнего простого числа, наиболее близкого к √N, то N — простое число. Очевидно, что данный способ громоздкий, поскольку требуется узнать все простые числа до √N. Похожий метод — перебор делителей, когда число делится на все простые числа до √N (полученные заранее) либо на два и все нечетные числа до √N, пока не будет найдено число, являющееся делителем N, или не закончится список.