Лема Евкліда

Лема Евкліда — важлива лема, яка стосується питань подільності та простих чисел. У своїй найпростішій формі, лема стверджує, що просте число, яке ділить без остачі добуток двох цілих чисел, ділить без остачі принаймні одне з цих цілих чисел окремо. Цей ключовий факт вимагає надзвичайно витонченого доведення (використовуючи теорему Безу), та є необхідним кроком у стандартному доведенні фундаментальної теореми арифметики.

Доведення

Нехай 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.

Див. також

• Список об'єктів, названих на честь Евкліда
• Теорема Евкліда