Лемма Евклида

---

Лемма Евклида — классический результат элементарной теории чисел. Она сформулирована как предложение 30 в книге VII «Начал» Евклида и является ключевой для доказательства основной теоремы арифметики. Современная формулировка^[1]:

Если произведение нескольких сомножителей делится на простое число ${\displaystyle p}$, то по крайней мере один из сомножителей делится на ${\displaystyle p}$.

Пример. 19 — простое число, и оно делит ${\displaystyle 19019=133\cdot 143.}$ Следовательно, один из сомножителей делится на 19, а именно: ${\displaystyle 133=19\cdot 7.}$

Если ${\displaystyle p}$ — не простое число, то теорема может не выполняться. Пример: ${\displaystyle 4\cdot 15=60}$ делится на 20, однако ни один из сомножителей на 20 не делится.

Пусть ${\displaystyle x\cdot y}$ делится на ${\displaystyle p}$, но ${\displaystyle x}$ не делится на ${\displaystyle p}$. Тогда ${\displaystyle x}$ и ${\displaystyle p}$ — взаимно простые, следовательно, найдутся целые числа ${\displaystyle u}$ и ${\displaystyle v}$ такие, что

Оба слагаемых в левой части делятся на ${\displaystyle p}$, значит, и правая часть делится на ${\displaystyle p}$, ч. т. д.^[2]

---