Число простых чисел

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

Доказательство это принадлежит древнегреческому математику Евклиду и входит в его знаменитые "Начала". Оно относится к разряду доказательств "от противного". Предположим, что ряд простых чисел конечен, и обозначим последнее простое число в этом ряду буквой N. Составим произведение

1 × 2 × 3 × 4 × 5 × 6 × 7 × ... × N = N!

и прибавим к нему 1. Получим:

N! + 1.

Это число, будучи целым, должно содержать хотя бы один простой множитель, т. е. должно делиться хотя бы на одно простое число. Но все простые числа, по предположению, не превосходят N, число же N! + 1 не делится без остатка ни на одно из чисел, меньших или равных N, - всякий раз получится остаток 1.

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