Recover a gcd and the combination that produces it

Try

Compute gcd(84, 30). Division gives 84=2·30+24, 30=24+6 and 24=4·6. The final nonzero remainder is six. Back substitution gives 6=30−24=3·30−84. Thus the gcd is not just a common divisor: it is an integer combination of the original inputs. Verify the coefficients before generalizing the method.

Predict

Predict why replacing (84, 30) by (30, 24) preserves the gcd. Every common divisor divides the remainder 84−2·30. Conversely, a divisor of 30 and 24 divides their combination 84. The argument works in both directions. A procedure that merely produces a common divisor has not yet proved that it is the greatest one.

Experiment

Track remainder identities alongside their origin.

Remainder	Combination of 84 and 30
84	1·84+0·30
30	0·84+1·30
24	1·84−2·30
6	−1·84+3·30

Apply the same update to coefficient pairs that you apply to remainders. Then change the inputs to 85 and 30 and find the new gcd and combination. This tests the invariant rather than memorizing one trace.

Understand

For positive current divisor b, division produces 0≤r< b, so nonzero remainders strictly decrease. The Euclidean algorithm therefore terminates. The common-divisor invariant holds at each step, and at the final pair (d, 0), the positive gcd is d. Back substitution proves d=ua+vb. An independent proof chooses the least positive integer combination: dividing each input by that least positive d leaves a smaller nonnegative combination, so the remainder must vanish. Every common divisor divides d. This establishes the Bézout characterization without relying on the algorithm’s particular quotients.

Apply

If gcd(a, b)=1 and a divides bc, multiplying ua+vb=1 by c shows a divides c. This is a cancellation theorem with a hypothesis, not permission to cancel arbitrary factors in divisibility. For example, 6 divides 3·2 but does not divide 2 because gcd(6, 3)≠1. Bézout also provides modular inverses: ua+vm=1 means ua≡1 modulo m. If the gcd is larger than one, such an inverse cannot exist. The same identity supports proofs about primes and solutions of linear Diophantine equations.

The back-substitution coefficients are not unique. If ax+by=g and a, b are nonzero, replacing x by x+(b/g)t and y by y−(a/g)t preserves the identity for every integer t. This is the same freedom that appears in linear Diophantine equations. A computer trace should therefore verify the identity and gcd, not insist on one particular pair of coefficients. Negative inputs can be handled by first running the nonnegative remainder algorithm on absolute values and then restoring the signs in the coefficients. The special pair a=b=0 has gcd convention zero but has no least positive linear combination.

Continue

An extended Euclidean program should return the positive gcd and coefficients whose exact combination is checked independently. Include zero inputs, negative inputs and equal inputs, while treating (0, 0) according to an explicit convention. Work grows with the input size; counting remainder steps is different from counting bit operations on large integers. The next lesson uses the coprime-cancellation lemma to prove prime-factorization uniqueness, rather than assuming uniqueness to justify the gcd algorithm.

Return to the number theory unit to choose a targeted retry. Continue with prove that prime factors cannot hide inside a product.