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

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

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

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

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

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

Если произведение ${\displaystyle bc}$ делится на ${\displaystyle a}$ и ${\displaystyle a,b}$ взаимно просты, то^[3] ${\displaystyle c}$ делится на ${\displaystyle a.}$

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

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

• Виноградов И. М. Основы теории чисел. — М.—Л.: ГИТТЛ, 1952. — 180 с.
• Жиков В.В. Основная теорема арифметики // Соросовский Образовательный Журнал. — 2000. — Т. 6, № 3. — С. 112—117.

`* Weisstein, Eric W. Euclid's Lemma (англ.) на сайте Wolfram MathWorld.