Name the repeated work
The greatest common divisor is the largest positive integer that divides both inputs exactly. For nonnegative inputs with at least one positive, dividing x by y leaves a remainder. A number divides both x and y exactly if and only if it divides y and that remainder.
Trace the state
A while loop checks its condition before executing the body. Each pass replaces (x, y) with (y, x % y). Save the remainder first because overwriting x earlier would lose one of the inputs.
| Before the pass | Remainder | After the pass |
|---|---|---|
| 48, 18 | 12 | 18, 12 |
| 18, 12 | 6 | 12, 6 |
| 12, 6 | 0 | 6, 0 |
Explain termination
When y is positive, the new remainder is at least zero and strictly smaller than y. Eventually y reaches zero. The guard prevents taking a remainder with a zero divisor and the final x supplies the answer.
Start with a small test
If the second argument already equals zero, no iteration runs. Swapping positive inputs can add a first iteration, but the same common divisors survive. Tracing two small examples by hand is a quick way to find a mistaken update order.
Try the program
Expected output
6
Practice
Use 35 and 15 as inputs. Predict each remainder and the final result.
Hint
Start with 35 % 15, then divide 15 by that remainder.
Worked solution
The remainders are 5 and 0, so the last positive divisor is 5.
Find
gcd(48, 18)Replace with
gcd(35, 15)Output after the change
5