Бендукидзе А. Д.

О простых числахБендукидзе А. Д. О простых числах // Квант. — 1973. — № 4. — С. 71⁠—⁠72.‍‍

В этой заметке рассказывается коечто о простых числах. Этими числами люди заинтересовались ещё в глубокой древности. Относительно простых чисел было поставлено множество интересных вопросов. Примечательно, что ответы на некоторые из них не известны и по сей день.

1. Возьмём ряд натуральных чисел: $$ 1,~2,~3,~4,~5,~{\ldots}. $$ В этом ряду нет наибольшего числа. Как это понимать? Это значит, что каким бы большим ни было натуральное число $n$‍,‍ существует ещё большее число. В самом деле, таким будет уже следующее натуральное число, — число $n+1$‍.‍ Итак, натуральных чисел бесконечно много. Именно этот факт и подразумевают математики, когда говорят, что множество натуральных чисел бесконечно.

2. Наименьшим в ряду натуральных чисел является число 1. У него только один делитель — это 1. Следующее число — 2. У этого числа два делителя: 1 и 2. Далее идёт 3. У него тоже два делителя: 1 и 3. Но уже у следующего числа, числа 4, три делителя: 1, 2, 4. У 5 два делителя, у 6 — четыре и т. д. Число может иметь и много делителей. Например, у числа 60 — 12 делителей: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.

Число, у которого только два делителя: 1 и само это число, — называется простым; если же у числа более двух делителей, то оно называется составным. Так, например, числа 2, 3, 5, 7, 11 — простые, а 4, 6, 8, 9, 10 — составные. А как быть с числом 1? Ведь у него только один делитель! Это число не является ни простым, ни составным.

Таким образом, множество натуральных чисел естественным образом разбивается на три части или, как принято говорить, на три подмножества. Первое из этих подмножеств состоит из одного числа, а именно, из числа 1; второе содержит все простые числа, а третье — составные. Заметим, что каждое натуральное число попадает в одно и только одно из этих подмножеств, т. е., как обычно говорят, эти подмножества попарно не пересекаются.

3. Легко догадаться, что множество составных чисел бесконечно. В самом деле, уже чисел вида $2^n$‍,‍ где $n$‍‍ принимает значения 2, 3, 4, $\dots$‍,‍ бесконечно много, а ведь кроме этих существуют и другие составные числа!

Ну, а что можно сказать относительно простых чисел — конечно или бесконечно их множество? Известный древнегреческий математик Евклид, который жил в III веке нашей эры, доказал, что множество простых чисел бесконечно.

Посмотрите, как остроумно рассуждает Евклид при доказательстве этого факта.

Пусть $p$‍‍ — некоторое простое число. Докажем, что существует простое число, большее $p$‍.‍ В самом деле, перемножим все простые числа до $p$‍,‍ включая само $p$‍,‍ и к этому произведению добавим единицу. Получим следующее число: $$ 2\cdot3\cdot5\cdot7\cdot\ldots\cdot p+1. $$

Это число, которое явно больше $p$‍,‍ будет или простым, или составным, Если оно простое, тем самым уже доказано, что существует простое число, большее чем $p$‍.‍ Если же оно составное, то оно должно делиться на некоторое простое число; но ни на одно из простых чисел 2, 3, 5, $\ldots$‍,‍ $p$‍‍ оно не делится — при делении на эти числа в остатке всегда будет получаться 1. Значит, оно должно делиться на простое число, большее чем $p$‍.‍ Итак, и в этом случае мы вынуждены признать, что существует простое число, большее чем $p$‍.‍ Но это и означает, что не существует наибольшего простого числа, откуда следует бесконечность множества простых чисел.

4. Таким образом, множество простых чисел бесконечно. При этом ясно, что множество простых чисел, не превосходящих некоторого $n$‍,‍ конечно. Как найти эти числа? Проще всего это сделать методом, который был предложен современником Архимеда, греческим математиком Эратосфеном. Познакомимся с этим методом.

Пусть требуется найти все простые числа, не превосходящие $n$‍.‍ Выпишем подряд числа от 1 до $n$‍:‍ $$ 1,~2,~3,~4,~5,~{\ldots},~n. $$

Первым стоит число 1. Оно, как мы уже знаем, не является простым. Поэтому вычеркнем его. Следующее число — 2. Оно простое. Оставляем это число и вычёркиваем все числа, кратные 2. Для этого достаточно вычеркнуть каждое второе число, начиная с 4. Идём дальше. Первое невычеркнутое число — 3. Оно простое. Оставляем его и вычёркиваем все числа, кратные ему, т. есть каждое третье число, начиная с 6. (При счёте следует учитывать и ранее вычеркнутые числа, поэтому некоторые числа вычёркиваются второй раз; такими будут 6, 12, 18, $\ldots$‍.)‍ После этой операции первым невычеркнутым, а значит и простым, будет 5. Его оставляем и вычёркиваем все числа, кратные 5, т. е. каждое пятое число, начиная с 10. Далее переходим к следующему невычеркнутому числу (таким будет 7) и т. д. Окончательно мы вычеркнем все составные числа, и у нас останутся только лишь простые. Вот, например, что у нас получится, если $n=60$‍:‍ $$ \def\z#1#2{\hphantom0\mathllap{#1}\mathrlap{#2}\mathclap{\htmlClass{color--red}{\raisebox{1pt}{\(\mathrlap{\diagdown}\diagup\)}}}\hphantom0} \def\n#1#2{\hphantom0\mathllap{#1}\mathrlap{#2}\hphantom0} {\begin{array}{|rrrrrrrrrr|}\hline\\[-9pt] \z{}1&\n{}2&\n{}3&\z{}4&\n{}5&\z{}6&\n{}7&\z{}8&\z{}9&\z10\\ \n11&\z12&\n13&\z14&\z15&\z16&\n17&\z18&\n19&\z20\\ \z21&\z22&\n23&\z24&\z25&\z26&\z27&\z28&\n29&\z30\\ \n31&\z31&\z33&\z34&\z35&\z36&\n37&\z38&\z39&\z40\\ \n41&\z42&\n43&\z44&\z45&\z46&\n47&\z48&\z49&\z50\\ \z51&\z52&\n53&\z54&\z55&\z45&\z57&\z58&\n59&\z60\\[3pt] \hline \end{array}} $$

По этой таблице мы находим все простые числа от 1 до 60. Их всего 17: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59.

Применяя метод Эратосфена, мы как бы отсеяли, пропустили через решето все составные числа и оставили только простые. Этот метод называется «решетом Эратосфена».

В заключение заметим, что, пользуясь решетом Эратосфена, вычёркивание можно прекратить, как только мы дойдём до простого $p$‍,‍ которое больше $\sqrt n$‍.‍ К этому моменту все невычеркнутые числа будут простыми. (Постарайтесь доказать это сами.) Так, при $n=60$‍‍ после того, как мы вычеркнули числа, кратные 7, дальнейшее вычёркивание можно не производить.

Предлагаем вашему вниманию одну простенькую задачу: докажите, что если $p$‍‍ — простое число больше трёх, то $p^2-1$‍‍ делится на 24.