Problem
COM-B2-M05-P007 The Difference Algorithm
#7
★★★☆☆ Level 3 of 5
Positive integers \(84\) and \(30\) are given. In one move, the larger number is replaced by the difference of the larger and the smaller. Prove that the pair \(7,7\) cannot be obtained.
Find an invariant related to common divisors.
When \((a,b)\) is replaced by \((a-b,b)\) for \(a\ge b\), the gcd does not change: \(\gcd(a,b)=\gcd(a-b,b)\). The same holds when \(b\) is replaced by \(b-a\).
Initially \(\gcd(84,30)=6\). The pair \(7,7\) has gcd \(7\). Since the gcd is invariant, this pair is unreachable.
Important: the problem does not ask to run the algorithm, only to prove impossibility.