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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Если простое число делит без остатка произведение двух целых чисел , то делит или .

Доказательство[править | править код]

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

(соотношение Безу).

Умножая обе части на , получаем

Оба слагаемых в левой части делятся на , значит, и правая часть делится на , ч. т. д.

Ссылки[править | править код]