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

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

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

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

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

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

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

$x\cdot u+p\cdot v=1$ (соотношение Безу).

Умножая обе части на $y$, получаем

$(x\cdot y)\cdot u+p\cdot v\cdot y=y.$

Оба слагаемых в левой части делятся на $p$, значит, и правая часть делится на $p$, ч. т. д.

Обобщения

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

• Кольцо целых гауссовых чисел $\mathbb{Z}[i].$
• Кольцо многочленов от одной переменной $K[x]$ над полем $K.$

Литература

• Шаблон:Книга
• Шаблон:Статья

Ссылки

`* Шаблон:H