Processing math: 100%

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

Лемма Евклида — классический результат элементарной теориичисел. Она сформулирована как предложение 30 в книге VII «Начал»Евклида. Если простое число p делит без остатка произведение двухцелых чисел x·y, то p делит x или y.

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


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

xu+pv=1 (соотношение Безу).
 Умножая обе части на y, получаем

(xy)u+pvy=y.
 Оба слагаемых в левой части делятся на p, значит, и правая частьделится на p, ч.т.д.