Use remainder reduction and back-substitution to construct integer certificates.
Loading your saved responses…
Try
To find gcd(84,30), divide: 84=2·30+24, 30=24+6, 24=4·6. The last nonzero remainder is 6. The algorithm replaces large numbers with smaller ones while preserving their common divisors.
Predict
Predict why the update (a,b)→(b,a−qb) preserves the gcd. Any common divisor of a,b divides the difference; any divisor of b and that difference also divides a. For positive b, the division algorithm chooses remainder r with 0≤r<b.
Experiment
Run the remainders for 35 and 22, then write each remainder as a combination of its two predecessors. Reverse those equations to express the final gcd as a combination of the original inputs. Check the resulting identity by multiplication.
Understand
Worked certificate for 84 and 30: 6=30−24=30−(84−2·30)=3·30−84. Thus the gcd has a Bézout representation. More generally back-substitution produces integers u,v with au+bv=gcd(a,b) whenever a,b are not both zero.
Termination follows because the positive remainder strictly decreases at each division. At remainder zero, the preceding positive value divides both original numbers and has exactly their common divisors, so it is the gcd. For negative inputs, use absolute values for the positive gcd and adjust coefficient signs afterward.
Invalid rule: the first nonzero remainder is the gcd. A remainder need not divide the preceding divisor; the chain must continue until a zero remainder appears.
Apply
Show both the remainder chain and the final certificate. The certificate verifies a common-divisor bound, but also check that the proposed gcd divides both inputs. State conventions: gcd(a,0)=|a| for a≠0; this unit avoids relying on gcd(0,0).
Continue
Depth: Euclid is an algorithm with a divisibility invariant and a decreasing measure, linking number theory to program verification. Extended Euclid supplies modular inverses and Diophantine solutions, which the next lessons use.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Find gcd(252,198).
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Find the integer x in 30x+18(2)=6.
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
If a=qb+r, then:
For positive integer a, gcd(a,0) is:
Prove that a and b have the same common divisors as b and a−qb for any integer q.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Use Euclid and back-substitution to write gcd(35,22) as an integer combination of 35 and 22.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
