1. Что такое простые числа?

К понятию простых чисел приводят уже самые простые задачи, которые возникают в связи с таким элементарным арифметическим действием, как умножение натуральных, т. е. целых положительных чисел.

Как известно, произведение двух натуральных чисел всегда является числом натуральным, Следовательно, существуют натуральные числа, представляющие собой произведения двух натуральных чисел, больших единицы» Но существуют также натуральные числа, большие единицы, которые не являются произведениями двух натуральных чисел, больших единицы, например числа 2, 3, 5 или 13. Именно такие числа мы называем простыми.

Итак, простым числом мы называем каждое натуральное число, большее единицы, которое не является произведением двух натуральных чисел, ббльших единицы.

Напрашивается вопрос, имеем ли мы возможность относительно каждого натурального числа установить, простое оно или нет. Оказывается, само определение простых чисел позволяет ответить на этот вопрос.

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

следовательно, а есть делитель натурального числа больший 1 и меньший чем Поэтому, чтобы убедиться в том, что натуральное число является простым, достаточно убедиться, что оно не имеет натурального делителя Для этого достаточно выполнить делений числа поочередно на числа Если ни на одно из них число не делится без остатка, то в этом и только в этом случае число является простым.

Итак, по крайней мере теоретически, мы всегда сумеем (при помощи конечного числа делений) убедиться, является ли данное натуральное число простым или нет. На практике описанный способ может порождать значительные трудности, когда большое число. Так, до сих пор мы не можем, ввиду длинноты необходимых вычислений, применить этот способ к числу , имеющему тридцать одну цифру (в десятичной системе счисления), хотя другим путем доказано, что это число является составным. Впрочем, до сих пор неизвестно ни одного разложения этого числа в произведение двух натуральных чисел, больших единицы (хотя мы и знаем, что такое разложение существует). Также неизвестно, является ли число (имеющее 39 457 цифр) простым или нет.