WikiSort.ru - Не сортированное

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

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

Пусть ${\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}$ , ч. т. д.

Ссылки

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

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.

Для улучшения этой статьи по математике желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное.