Лема Евкліда

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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