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

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

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

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

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

x·u + p·v = 1

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

(x·y)·u + p·v·y = y.

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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home