153
правки
Изменения
→Стандартный алгоритм Евклида
'''Корректность''' этого алгоритма вытекает из следующих двух утверждений:
# Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а <tex>r = a - bq = (t_1 - t_2*q)*k </tex> (выражение в скобках есть целое число, следовательно, k делит r без остатка)
# Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b.
# В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
}}
Проще сформулировать алгоритм Евклида так: если даны натуральные числа <tex>a</tex> и <tex>b</tex> и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.
