Лемма Евклида
Все числа в данной статье подразумеваются целыми, если не оговорено иное.

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

Пример. 19 — простое число, и оно делит  Следовательно, один из сомножителей делится на 19, а именно: 

Если  — не простое число, то теорема может не выполняться. Пример:  делится на 20, однако ни один из сомножителей на 20 не делится.

Доказательство 
Пусть  делится на , но  не делится на . Тогда  и  — взаимно простые, следовательно, найдутся целые числа  и  такие, что
  (соотношение Безу).
Умножая обе части на , получаем
 
Оба слагаемых в левой части делятся на , значит, и правая часть делится на , ч. т. д.

Обобщения 

Лемма Евклида имеет место не только в кольце целых чисел, но и в других факториальных кольцах, где роль простых чисел играют неприводимые элементы. В частности, она справедлива в евклидовых кольцах, например:
 Кольцо целых гауссовых чисел 
 Кольцо многочленов от одной переменной  над полем

Примечания

Литература

Ссылки 
`* 

Теория чисел
Теоремы о простых числах
Евклида