Задача
COM-B2-M05-P007 Разностный алгоритм
#7
★★★☆☆ Уровень 3 из 5
Даны положительные целые числа \(84\) и \(30\). За ход большее число заменяют разностью большего и меньшего. Докажите, что нельзя получить пару \(7,7\).
Найдите инвариант, связанный с общими делителями.
При замене пары \((a,b)\) на \((a-b,b)\) при \(a\ge b\) НОД не меняется: \(\gcd(a,b)=\gcd(a-b,b)\). То же верно при замене \(b\) на \(b-a\).
В начале \(\gcd(84,30)=6\). У пары \(7,7\) НОД равен \(7\). Поскольку НОД является инвариантом, такая пара недостижима.
Важно: задача не просит выполнить алгоритм, только доказать невозможность.