Задача
COM-B2-M05-P017 Алгоритм Евклида как процесс
Даны два положительных целых числа \(a\) и \(b\). За ход большее число заменяют разностью большего и меньшего. Докажите, что процесс обязательно придёт к паре \(d,d\), где \(d=\gcd(a,b)\).
НОД сохраняется, а сумма чисел уменьшается, пока числа не равны.
НОД пары не меняется при замене \((a,b)\) на \((a-b,b)\) или \((a,b-a)\), потому что общие делители сохраняются в обе стороны.
Если числа не равны, то один ход уменьшает сумму \(a+b\): большее число заменяется на положительно меньшее число. Сумма — положительное целое число, поэтому процесс не может продолжаться бесконечно.
Когда ходов больше нет, числа равны: пусть это \(c,c\). НОД всё время сохранялся, значит, \(c=\gcd(c,c)=\gcd(a,b)=d\). Итак, конечная пара равна \(d,d\).
Смешанная задача: инвариант определяет финал, моноинвариант доказывает завершение.