Лема Евкліда
Матеріал з Вікіпедії — вільної енциклопедії.
Лема Евкліда — класичний результат елементарної теорії чисел.
[ред.] Формулювання
Якщо добуток двох цілих чисел 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.