Теорема Евклида

---

Теорема Евклида — основной элемент теории чисел. Она утверждает, что для любого конечного списка простых чисел найдётся простое число, не вошедшее в этот список (то есть существует бесконечно много простых чисел).

Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (Книга IX, Предложение 20^[1]). При этом Евклид не использует понятие бесконечности, а доказывает это утверждение в следующей формулировке: простых чисел больше, чем любое выбранное конечное их множество.

Предположим, что дан некоторый конечный список простых чисел ${\displaystyle a,b,\dots z}$. Евклид доказывает, что существует простое число, не входящее в этот список.

Пусть ${\displaystyle P}$ — наименьшее общее кратное этих чисел, ${\displaystyle P=a*b*...*z}$.

Евклид рассматривает число ${\displaystyle Q=P+1}$. Если ${\displaystyle Q}$ — простое, то найдено простое число, не входящее в данный список ${\displaystyle {a,b,....z}}$ (поскольку оно больше каждого числа из списка).

Если же ${\displaystyle Q}$ не является простым, то существует некоторое простое число ${\displaystyle x}$, на которое нацело делится число ${\displaystyle Q}$. Но ${\displaystyle x}$ не может быть одновременно и делителем ${\displaystyle Q}$, и элементом списка ${\displaystyle {a,b,....z}}$ , поскольку тогда при делении ${\displaystyle Q}$ на ${\displaystyle x}$ был бы остаток, не равный нулю. Значит, существует простое число ${\displaystyle x}$, не входящее ни в какой (конечный) список простых чисел ${\displaystyle {a,b,....z}}$.

---