Лема Евкліда
Лема Евкліда — важлива лема, яка стосується питань подільності та простих чисел. У своїй найпростішій формі, лема стверджує, що просте число, яке ділить без остачі добуток двох цілих чисел, ділить без остачі принаймні одне з цих цілих чисел окремо. Цей ключовий факт вимагає надзвичайно витонченого доведення (використовуючи теорему Безу), та є необхідним кроком у стандартному доведенні фундаментальної теореми арифметики.
Доведення
Нехай 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.