Лема Евкліда

Матеріал з Вікіпедії — вільної енциклопедії.

Лема Евкліда — класичний результат елементарної теорії чисел.

[ред.] Формулювання

Якщо добуток двох цілих чисел x·y ділиться без остачі на просте число p, то або x або y діляться без остачі на p.


[ред.] Доведення

Нехай x·y ділиться на p, але x не ділится на p. Тоді x и p - взаємно прості числа, отже, існують такі цілі числа u та v, що x·u + p·v = 1 (співвідношення Безу). Домноживши обидві частини на y, отримаємо x·y·u + p·v·y = y. Обидва доданки в лівій частині діляться на p, отже, і права частина (тобто y) ділиться на p.

Іншими мовами