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

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

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

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


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

Пусть x·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, ч.т.д.