Доказательство. Предположим, что множество простых чисел конечно и состоит из чисел 2,3,5, ,p, где p – последнее самое большое простое число

Предположим, что множество простых чисел конечно и состоит из чисел 2,3,5,…, p, где p – последнее самое большое простое число. Рассмотрим натуральное число N =2∙3∙5∙…∙ p +1. Очевидно, что два не делит N, три не делит N, и так далее. Непосредственно видно, что при делении N на все числа 2,3,5,…, p получается остаток равный единице. Тогда или N само простое большее p или оно делится на простое число большее p. В обоих случаях существует простое число большее p. Наше предположение о конечности простых чисел неверно, следовательно, их бесконечно много.