§ 4. Простые числа

a. Число 1 имеет только один положительный делитель, именно L В этом отношении число 1 в ряде натуральных чисел стоит совершенно особо.

Всякое целое, большее 1, имеет не менее двух делителей, именно 1 и самого себя; если этими делителями исчерпываются все положительные делители целого числа, то оно называется простым. Целое, большее 1, имеющее кроме 1 и самого себя другие положительные делители, называется составным.

b. Наименьший отличный от единицы делитель целого, большего единицы, есть число простое.

Действительно, пусть - наименьший отличный от 1 делитель целого а, большего 1. Если бы q было бы составным, то оно имело бы некоторый делитель с условием причем число а, делясь на q, должно (1, b, § 1) делиться на это противоречило бы нашему предположению относительно числа

Наименьший отличный от единицы делитель составного числа а (согласно b он будет простым) не превосходит .

Действительно, пусть - этот делитель, тогда откуда, перемножая и сокращая на с, получим

Простых чисел бесконечно много.

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

е. Для составления таблицы простых чисел, не превосходящих данного целого N, существует простой способ, называемый решетом Эратосфена. Он состоит в следующем.

Выписываем числа

Первое большее 1 число этого ряда есть 2. Оно делится только на 1 и на самого себя и, следовательно, оно простое.

Вычеркиваем из ряда (1) (как составные) все числа, кратные 2, кроме самого 2. Первое следующее за 2 невычеркнутое число есть 3. Оно не делится на 2 (иначе оно оказалось бы вычеркнутым). Следовательно, 3 делится только на 1 и на самого себя, а потому оно также будет простым.

Вычеркиваем из ряда (1) все числа, кратные 3, кроме самого 3. Первое следующее за 3 невычеркнутое число есть 5. Оно не делится ни на 2, ни на 3 (иначе оно оказалось бы вычеркнутым). Следовательно, 5 делится только на 1 и на самого себя, а потому оно также будет простым.

И т. д.

Когда указанным способом уже вычеркнуты все числа, кратные простых, меньших простого , то все невычеркнутые, меньшие , будут простые. Действительно, всякое составное а, меньшее , нами уже вычеркнуто, как кратное его наименьшего простого делителя, который Отсюда следует:

1. Приступая к вычеркиванию кратных простого , это вычеркивание следует начинать с

2. Составление таблицы простых чисел, не превосходящих N, закончено, как только вычеркнуты все составные кратные простых, не превосходящих