ПРИЛОЖЕНИЕ А. Доказательство бесконечности числа простых чисел

Используемое здесь рассуждение представляет собой так называемое косвенное доказательство, именуемое также доказательством от противного, или reductio ad absurdum (приведением к абсурду). В доказательстве такого типа допускается, что сделанное предположение ложно, а затем из этого допущения выводится противоречие. В случае рассматриваемого предложения мы предполагаем, таким образом, что имеется лишь конечное число простых чисел.

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

Это обозначение подразумевает, что всего имеется k простых чисел, где k — некоторое натуральное число. Если считать, что простые числа, перечислены в порядке возрастания, то, конечно, и т. д. Тем не менее в процессе доказательства удобнее использовать обозначения и т. д. вместо 2, 3, 5 и т. д.

Так как каждое натуральное число можно разложить на простые множители, то каждое натуральное число должно делиться хотя бы на одно из чисел

поскольку, согласно сделанному предположению, других простых чисел нет.

Рассмотрим, однако, натуральное число получающееся от перемножения всех простых чисел и последующего добавления единицы:

Число не делится на поскольку при делении на частное и остаток равны соответственно и 1. Если бы делилось на то остаток был бы равен 0. Значит, не делится на

Аналогично доказывается, что не делится ни на одно из чисел

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