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

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

Лемма Евклида — классический результат элементарной теории чисел. Она сформулирована как предложение 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 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.}$

Примечания

1. Виноградов, 1952, с. 20.
2. Калужнин Л. А. Основная теорема арифметики. — М.: Наука, 1969. — С. 13 (теорема 4). — 32 с. — (Популярные лекции по математике). Архивировано 26 января 2021 года.
3. Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. — С. 46 (теорема 41). — 384 с.
4. Ленг С. Алгебра. — М.: Мир, 1968. — С. 89—90. — 564 с.

Литература

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

Ссылки

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