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

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

Если произведение нескольких сомножителей делится на простое число $p$ , то по крайней мере один из сомножителей делится на $p$ .

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

Пример. 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$ , ч. т. д.[2]

Обобщения

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

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

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

Примечания

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

Литература

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

Ссылки

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_d5b20ad3c41dd4a3-1] Виноградов, 1952, с. 20.

[2] Калужнин Л. А. Основная теорема арифметики. — М.: Наука, 1969. — С. 13 (теорема 4). — 32 с. — (Популярные лекции по математике).

[3] Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966. — С. 46 (теорема 41). — 384 с.

[4] Ленг С. Алгебра. — М.: Мир, 1968. — С. 89—90. — 564 с.