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

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

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

Если произведение нескольких сомножителей делится на простое число [math]\displaystyle{ p }[/math], то по крайней мере один из сомножителей делится на [math]\displaystyle{ p }[/math].

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

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

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

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

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

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

[math]\displaystyle{ (x\cdot y)\cdot u+p\cdot v\cdot y=y. }[/math]

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

Обобщения

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

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

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

Литература

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

Ссылки

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