Лемма Евклида
- Все числа в данной статье подразумеваются целыми, если не оговорено иное.
Лемма Евклида — классический результат элементарной теории чисел. Она сформулирована как предложение 30 в книге VII «Начал» Евклида и является ключевой для доказательства основной теоремы арифметики. Современная формулировкаШаблон:Sfn:
Пример. 19 — простое число, и оно делит <math>19019 = 133 \cdot 143.</math> Следовательно, один из сомножителей делится на 19, а именно: <math>133 = 19 \cdot 7.</math>
Если <math>p</math> — не простое число, то теорема может не выполняться. Пример: <math>4 \cdot 15 = 60</math> делится на 20, однако ни один из сомножителей на 20 не делится.
Доказательство
Пусть <math>x\cdot y</math> делится на <math>p</math>, но <math>x</math> не делится на <math>p</math>. Тогда <math>x</math> и <math>p</math> — взаимно простые, следовательно, найдутся целые числа <math>u</math> и <math>v</math> такие, что
- <math>x\cdot u+p\cdot v=1</math> (соотношение Безу).
Умножая обе части на <math>y</math>, получаем
- <math>(x\cdot y)\cdot u+p\cdot v\cdot y=y.</math>
Оба слагаемых в левой части делятся на <math>p</math>, значит, и правая часть делится на <math>p</math>, ч. т. д.<ref>Шаблон:Книга</ref>
Обобщения
Лемма Евклида имеет место не только в кольце целых чисел, но и в других факториальных кольцах, где роль простых чисел играют неприводимые элементы. В частности, она справедлива в евклидовых кольцах<ref>Шаблон:Книга</ref>, например:
- Кольцо целых гауссовых чисел <math>\mathbb{Z}[i].</math>
- Кольцо многочленов от одной переменной <math>K[x]</math> над полем <math>K.</math>
Примечания
Литература
Ссылки
`* Шаблон:H