Бесконечность множества простых чисел

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

Доказательство бесконечности множества простых чисел

Предположим обратное – множество простых чисел конечно. Тогда все остальные числа являются составными.

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

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

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

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

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

Рассмотрим примеры:

2 × 3 × 5 × 7 + 1 = 211. Число 211 само является простым.

2 × 3 × 5 × 7 × 11 × 13 + 1= 30031. Это число делится на 59, которое является простым.

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

Таким образом, какой бы исходный список простых чисел не взяли, мы так или иначе найдем новое простое число. Им окажется либо само произведение + 1, либо простое число, которое больше исходных сомножителей, если они были взяты подряд от самого наименьшего простого числа.