Euclidean algorithm — GCD computation: Exercises

Before we start, one reminder of every symbol we use, in plain words:

Definition Notation refresher

$g cd (a, b)$ ::: the greatest common divisor: the largest whole number that divides both $a$ and $b$ with no leftover.
$a mod b$ ::: the remainder left when you divide $a$ by $b$ . If $a = b q + r$ with $0 \leq r < b$ , then $a mod b = r$ .
$d ∣ n$ ::: " $d$ divides $n$ ", meaning $n$ is a whole-number multiple of $d$ (no remainder). The bar here means "divides".
$∣ n ∣$ ::: the absolute value of $n$ — its size ignoring sign, so $∣ - 7 ∣ = 7$ and $∣7∣ = 7$ . The two vertical bars around a number mean "size"; do not confuse them with the single divisibility bar $d ∣ n$ between two numbers.
coprime ::: two numbers whose $g cd$ is $1$ — they share no common factor bigger than $1$ .
$lcm (a, b)$ ::: the least common multiple: the smallest positive whole number that is a multiple of both $a$ and $b$ . It is tied to the GCD by $lcm (a, b) = \frac{ab}{g cd ( a , b )}$ .
$φ (n)$ ::: Euler's totient — the count of whole numbers from $1$ to $n$ that are coprime to $n$ (share no factor bigger than $1$ with $n$ ). Example: $φ (6) = 2$ because only $1$ and $5$ are coprime to $6$ .

Level 1 — Recognition

Exercise 1.1

Perform one step of the Euclidean algorithm on $g cd (84, 30)$ . Write the division $84 = 30 q + r$ and state the new pair $(b, r)$ you would work with next.

Recall Solution 1.1

We ask: how many whole times does $30$ fit into $84$ ? Twice, since $30 \cdot 2 = 60$ and $30 \cdot 3 = 90 > 84$ . So $q = 2$ . $84 = 30 \cdot 2 + 24 \Rightarrow r = 24.$ The next pair is $(b, r) = (30, 24)$ . We now forget $84$ entirely and continue with $g cd (30, 24)$ .

Exercise 1.2

Which of these already tells you the algorithm has finished: $g cd (30, 24)$ , $g cd (24, 0)$ , $g cd (6, 6)$ ? State the GCD wherever it is finished.

Recall Solution 1.2

The stopping condition is when the second number is $0$ .

$g cd (30, 24)$ — not finished ( $24 \neq = 0$ ).
$g cd (24, 0)$ — finished. When $b = 0$ the answer is $a$ , so this equals $24$ .
$g cd (6, 6)$ — not the stop rule yet, but one step gives $6 = 6 \cdot 1 + 0$ , so it becomes $g cd (6, 0) = 6$ . Answers: $g cd (24, 0) = 24$ , and $g cd (6, 6) = 6$ .

Level 2 — Application

Exercise 2.1

Compute $g cd (252, 105)$ using the full algorithm. Show every division line.

Recall Solution 2.1

Each line writes $a = b q + r$ , then we slide $(a, b) \to (b, r)$ : $252 = 105 \cdot 2 + 42$ $105 = 42 \cdot 2 + 21$ $42 = 21 \cdot 2 + 0$ The last nonzero remainder is $21$ , so $g cd (252, 105) = 21$ .

Exercise 2.2

Compute $g cd (18, 48)$ — note the smaller number is written first. Explain what the very first step does.

Recall Solution 2.2

With $a = 18, b = 48$ we compute $18 mod 48$ . Since $48$ fits into $18$ zero times: $18 = 48 \cdot 0 + 18 \Rightarrow r = 18.$ So the pair $(b, r) = (48, 18)$ — the algorithm swapped them for us. Continuing: $48 = 18 \cdot 2 + 12, 18 = 12 \cdot 1 + 6, 12 = 6 \cdot 2 + 0.$ Answer: $g cd (18, 48) = 6$ . No pre-sorting was needed.

Exercise 2.3

Compute $g cd (600, 276)$ with the algorithm, then confirm your answer divides both the friendly pair $600, 276$ and the two big numbers $1160718174$ and $316258250$ from which they were shrunk down.

Recall Solution 2.3

$600 = 276 \cdot 2 + 48$ $276 = 48 \cdot 5 + 36$ $48 = 36 \cdot 1 + 12$ $36 = 12 \cdot 3 + 0$ $g cd (600, 276) = 12$ . Check on the friendly pair: $600/12 = 50$ and $276/12 = 23$ , both whole numbers. ✓ Now the big inputs — run the algorithm honestly, no shortcuts. We must not guess; we apply the same divide-take-remainder loop to the actual numbers: $1160718174 = 316258250 \cdot 3 + 211943424$ $316258250 = 211943424 \cdot 1 + 104314826$ $211943424 = 104314826 \cdot 2 + 3313772$ $104314826 = 3313772 \cdot 31 + 1587894$ $3313772 = 1587894 \cdot 2 + 137984$ $1587894 = 137984 \cdot 11 + 70070$ $137984 = 70070 \cdot 1 + 67914$ $70070 = 67914 \cdot 1 + 2156$ $67914 = 2156 \cdot 31 + 1078$ $2156 = 1078 \cdot 2 + 0$ The last nonzero remainder is $1078$ , so $g cd (1160718174, 316258250) = 1078$ . Does $12$ divide these big numbers? Test $12 = 2^{2} \cdot 3$ directly. For divisibility by $4$ : the last two digits of $1160718174$ are $74$ , and $74/4 = 18.5$ is not whole, so $4 ∤ 1160718174$ — hence $12 ∤ 1160718174$ . So $12$ is the GCD of the small pair only; the big numbers were a decoy with a completely different GCD of $1078$ . The lesson: a divisor of a shrunk-down pair need not divide the original numbers — you must run the algorithm on the actual inputs, exactly as we just did.

Level 3 — Analysis

Exercise 3.1

You run the algorithm on $(a, b)$ and the sequence of remainders is $147, 21, 0.$ Two facts follow immediately about $g cd (a, b)$ and about which remainder is the GCD. State the GCD and explain why the second-to-last remainder is always the answer.

Recall Solution 3.1

The GCD is the last nonzero remainder, which is $21$ . Why: the very last line is $147 = 21 \cdot 7 + 0$ , meaning $21 ∣ 147$ . Now use the Euclidean Lemma stated at the top of this page — $g cd (a, b) = g cd (b, a mod b)$ — which says every consecutive pair in the chain has the same GCD (each pair shares exactly the same common divisors). Walking that equality backward: $g cd (a, b) = g cd (b, 147) = g cd (147, 21) = g cd (21, 0) = 21.$ Because the last pair is $g cd (21, 0) = 21$ (edge case: $g cd (n, 0) = n$ ), the value $21$ threads unchanged all the way back up to the original $a$ and $b$ . That is why the last nonzero remainder is always the answer.

Exercise 3.2

Suppose $g cd (a, b) = 1$ (coprime). Show that $g cd (a, a + b) = 1$ as well.

Recall Solution 3.2

Apply the Euclidean Lemma to the pair $(a + b, a)$ . Divide: $(a + b) = a \cdot 1 + b \Rightarrow (a + b) mod a = b .$ So $g cd (a + b, a) = g cd (a, b) = 1$ . Since $g cd$ does not care about order, $g cd (a, a + b) = 1$ too. Reading it aloud: any common divisor of $a$ and $a + b$ must divide their difference $b$ ; but nothing bigger than $1$ divides both $a$ and $b$ , so nothing bigger than $1$ survives.

Exercise 3.3

Using $lcm (a, b) = \frac{ab}{g cd ( a , b )}$ , find $lcm (48, 18)$ .

Recall Solution 3.3

$lcm$ is the least common multiple (see the notation refresher). From the parent note, $g cd (48, 18) = 6$ . Then $lcm (48, 18) = \frac{48 \cdot 18}{6} = \frac{864}{6} = 144.$ Sanity check: $144 = 48 \cdot 3 = 18 \cdot 8$ , a multiple of both. ✓

Level 4 — Synthesis

The next two problems are geometric. The Euclidean algorithm is literally the answer to: "what is the largest square tile that perfectly fills a rectangle?" Read the figure carefully — its labels drive the whole solution.

Figure — Euclidean algorithm — GCD computation

Figure s01 — walk-through. The yellow outline is the whole $48 \times 18$ rectangle (blue width label $48$ along the bottom, height label $18$ up the left side). We first lay down the biggest squares that fit — side $18$ (blue squares, marked with their side length). Two of them fit, and a $12$ -wide strip is left over on the right. Into that strip we fit one square of side $12$ (green), leaving a $6$ -wide sliver. That sliver takes two squares of side $6$ (red), which fill it exactly — no scrap. Each colour is one row of the algorithm; the smallest square's side is the GCD.

Exercise 4.1

A rectangle is $48 \times 18$ . Using the tiling picture above, cut the largest possible squares repeatedly. How many squares of each size appear, and what is the side of the smallest square? Connect the tile counts to the quotients of the algorithm.

Recall Solution 4.1

Run $g cd (48, 18)$ and record the quotients — each quotient counts how many squares of that size fit (match them to the coloured blocks in figure s01): $48 = 18 \cdot 2 + 12 (two blue 18 \times 18 squares)$ $18 = 12 \cdot 1 + 6 (one green 12 \times 12 square)$ $12 = 6 \cdot 2 + 0 (two red 6 \times 6 squares, exact fit)$ So the tiling uses two $18$ -squares, one $12$ -square, and two $6$ -squares. The smallest square has side $6$ — which is exactly $g cd (48, 18) = 6$ . The remainder-zero step is the moment the leftover strip is perfectly filled with no scrap.

Exercise 4.2

Look at the second figure: an $89 \times 55$ rectangle (consecutive Fibonacci sides). Predict — before tiling — that every square will have quotient exactly $1$ except possibly the last, and that the smallest square has side $1$ . Verify with the algorithm.

Figure s02 — walk-through. The yellow outline is the $89 \times 55$ rectangle (blue width $89$ along the bottom, height $55$ on the left). Because the sides are consecutive Fibonacci numbers, each cut peels off exactly one square (labelled with its side) and leaves a smaller rectangle whose sides are again consecutive Fibonacci numbers — $55, 34, 21, 13, \dots$ . The squares spiral inward, getting smaller by one Fibonacci step each time, until the final square has side $1$ . This "one square per step" pattern is the slowest the algorithm can ever shrink — the worst case.

Recall Solution 4.2

Because $89$ and $55$ are consecutive Fibonacci numbers, each division peels off exactly one square then leaves the previous Fibonacci number (trace the inward spiral in figure s02): $89 = 55 \cdot 1 + 34, 55 = 34 \cdot 1 + 21, 34 = 21 \cdot 1 + 13, 21 = 13 \cdot 1 + 8,$ $13 = 8 \cdot 1 + 5, 8 = 5 \cdot 1 + 3, 5 = 3 \cdot 1 + 2, 3 = 2 \cdot 1 + 1, 2 = 1 \cdot 2 + 0.$ Every quotient is $1$ (the last is $2$ ), so we get a spiral of one-of-each squares — this is the slowest possible shrinkage, the worst case. The smallest square has side $g cd (89, 55) = 1$ , confirming the numbers are coprime.

Level 5 — Mastery

Exercise 5.1

Find all integers $x$ with $0 \leq x < 26$ such that $g cd (x, 26) = 1$ . (These are exactly the numbers that have a modular inverse mod $26$ , and hence the valid multiplier keys in a simple cipher.) How does this count relate to $φ (26)$ ?

Recall Solution 5.1

Recall $φ (n)$ is Euler's totient — the count of numbers coprime to $n$ (notation refresher above). Here $26 = 2 \cdot 13$ . A number is coprime to $26$ iff it is divisible by neither $2$ nor $13$ . Remove even numbers and multiples of $13$ ( $0, 13$ ). What remains from $1$ to $25$ : ${1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25} .$ Counting them gives $12$ values. Now the totient formula, using $26 = 2 \cdot 13$ : $φ (26) = 26 (1 - \frac{1}{2}) (1 - \frac{1}{13}) = 26 \cdot \frac{1}{2} \cdot \frac{12}{13} = 12.$ So the list length is $φ (26) = 12$ : the count of coprime residues below $26$ equals Euler's totient of $26$ , and these $12$ values are exactly the numbers that possess a modular inverse mod $26$ .

Exercise 5.2

Two gears mesh: one has $84$ teeth, the other $60$ . After how many teeth of the small gear will a marked tooth on each gear return to its starting contact simultaneously? (Hint: this is an LCM, built from a GCD.)

Recall Solution 5.2

They re-align after $lcm (84, 60)$ teeth (least common multiple, see refresher). First the GCD: $84 = 60 \cdot 1 + 24, 60 = 24 \cdot 2 + 12, 24 = 12 \cdot 2 + 0 \Rightarrow g cd = 12.$ Then $lcm (84, 60) = \frac{84 \cdot 60}{12} = \frac{5040}{12} = 420.$ The marks realign after $420$ teeth pass the contact point.

Exercise 5.3

Here is the real reason this algorithm powers RSA. In RSA one must check that a public exponent $e$ is usable by confirming $g cd (e, φ) = 1$ , where $φ$ is Euler's totient of the key modulus (the count of numbers coprime to it — see the refresher). Take $e = 17$ , $φ = 3120$ . Is $e$ a valid RSA exponent? Show the algorithm.

Recall Solution 5.3

Test $g cd (17, 3120)$ : $3120 = 17 \cdot 183 + 9$ $17 = 9 \cdot 1 + 8$ $9 = 8 \cdot 1 + 1$ $8 = 1 \cdot 8 + 0$ The last nonzero remainder is $1$ , so $g cd (17, 3120) = 1$ . Yes, $e = 17$ is valid — it is coprime to $φ$ , so an inverse exists (found by the extended algorithm) via Bézout's identity $17 x + 3120 y = 1$ .

Wrap-up recall

Recall The one sentence that solves every problem above

Replace the larger number by (larger $mod$ smaller), repeat, and the last nonzero remainder is the GCD — which also unlocks LCM, coprimality tests, and RSA key checks, all without ever factoring.