BlyxDocumentation
Browse chapters
Documentation / Language essentials

While loops and the Euclidean algorithm

Trace changing state and explain why a loop finishes.

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 passRemainderAfter the pass
48, 181218, 12
18, 12612, 6
12, 606, 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

Output Ready
Expected output
6
Open in the full playground →

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