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

Простые числа – это такие, которые делятся только на себя или на единицу. Сколько существует таких чисел? Можно ли их все перечислить и запомнить? Оказывается, сколько ни найдут простых чисел, а всегда можно найти ещё.

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

Простых чисел бесконечного много.

Доказательство

Доказательство — от противного. Пусть простых чисел конечное число — N. Тогда все их перемножим и к произведению прибавим 1. Получится натуральное число AN+1:

1 + p1 × p2 × ... × pN = AN+1

Попробуем это число поделить на каждое из N простых чисел — и каждый раз в остатке будет получаться 1, то есть AN+1 не делится ни на какое из N простых чисел. Значит, AN+1 — это либо другое простое число,

AN+1 = pN+1

либо оно раскладывается в произведение других простых чисел.

AN+1 = pN+2 × pN+3

Выходит, что простых чисел не N, а больше, что противоречит предположению (о том, что их конечное число). Значит, предположение неверно, и простых чисел бесконечно много.