Все числа в данной статье подразумеваются целыми, если не оговорено иное.
Лемма Евклида — классический результат элементарной теории чисел. Она сформулирована как предложение 30 в книге VII «Начал» Евклида и является ключевой для доказательства основной теоремы арифметики. Современная формулировка:
Пример. 19 — простое число, и оно делит Следовательно, один из сомножителей делится на 19, а именно:
Если — не простое число, то теорема может не выполняться. Пример: делится на 20, однако ни один из сомножителей на 20 не делится.
Доказательство Пусть делится на , но не делится на . Тогда и — взаимно простые, следовательно, найдутся целые числа и такие, что (соотношение Безу). Умножая обе части на , получаем
Оба слагаемых в левой части делятся на , значит, и правая часть делится на , ч. т. д.
Обобщения
Лемма Евклида имеет место не только в кольце целых чисел, но и в других факториальных кольцах, где роль простых чисел играют неприводимые элементы. В частности, она справедлива в евклидовых кольцах, например: Кольцо целых гауссовых чисел Кольцо многочленов от одной переменной над полем
Примечания
Литература
Ссылки `*
Категория:Теория чисел Категория:Теоремы о простых числах Евклида