Глава 3 м4. Евклидово доказательство бесконечности множества простых чисел

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

2, 3, 5, 7, 11, ... , P.

Перемножив все их между собой и прибавив к произведению единицу, получим число N:

N = 235711 ... P + 1.

Очевидно, N не делится ни на 2, ни на 3, ни на 5, ни на 7, ни на 11, ни... , ни на P, так как при делении на каждое из этих чисел в остатке получается 1. Итак, N не делится ни на одно из простых чисел из нашего списка. Следовательно, либо это число само является простым, либо делится на какое-нибудь простое число, не вошедшее в список. В каждом из этих случаев наш предполагаемый список всех простых чисел оказывается неполным. Поэтому множество простых чисел бесконечно.

Например, если бы кто-нибудь стал утверждать, что простыми являются только числа 2, 3 и 5, то он получит N=31, это простое число. Если затем он добавит число 31 к списку простых чисел, то

N = 23531+1 = 931 =7719,

и он получит простые числа 7 и 19, не входящие в список, и так далее до бесконечности.