Foundations — Euclidean algorithm — GCD computation

This page builds every symbol the parent note Euclidean algorithm — GCD computation uses, starting from the idea of a whole number. If you have never seen $\gcd$, $\mathrm{mod}$, $\mid$, or $q,r$ before, start here at line one. Nothing below is assumed.

1. Whole numbers and "fitting exactly"

The picture is tiles laid in a row with no gap and no overhang.

Look at the top row: three orange tiles of length $4$ exactly fill a bar of length $12$, so $4\mid 12$ (read "$4$ divides $12$"). In the bottom row, tiles of length $5$ overhang the bar of length $12$ — the last tile pokes out — so $5\nmid 12$ (read "$5$ does not divide $12$").

Prerequisite: 2.5.01-divisibility-and-division-algorithm.

2. Divisor and common divisor

Take $12$ and $18$.

• Divisors of $12$: $1,2,3,4,6,12$.
• Divisors of $18$: $1,2,3,6,9,18$.
• Living in both lists: $1,2,3,6$.

Those shared numbers are the common divisors. The picture: a tile length that lays perfectly along both bars at once.

3. The GCD — the star of the show

From the list above, the common divisors of $12$ and $18$ were $1,2,3,6$; the biggest is $6$, so $\gcd (12,18)=6$.

The magenta tile of length $6$ is the widest tile that still covers both the $12$-bar and the $18$-bar with no overhang. A tile of $7$ would overhang both; a tile of $3$ fits but is not the widest. That "widest fitting tile" is exactly what $\gcd$ means.

Contrast with the factorization route from 2.5.03-fundamental-theorem-of-arithmetic, which finds this same number by breaking each into primes.

4. Quotient and remainder — the division algorithm

When $b$ does not divide $a$, tiles overhang. The overhang is the star that makes the whole algorithm run.

For $a=18$, $b=12$: only one tile of length $12$ fits ($q=1$), and $18-12=6$ sticks out, so $r=6$. Written out: $18=12\cdot 1+6$. The rule $0\le r<b$ says the leftover is always smaller than the tile — otherwise you could have fit another whole tile.

5. The mod symbol

Examples you can check on your fingers:

• $18\mathrm{mod}12=6$
• $12\mathrm{mod}6=0$ (fits exactly — no leftover)
• $5\mathrm{mod}8=5$ (a small number mod a big one is itself, since zero big-tiles fit)

6. Putting the symbols together — why the swap works

Now every symbol in the parent's key line is defined. Read it aloud: $\gcd (a,b)=\gcd (b,a\mathrm{mod}b).$ In words: the biggest common tile of $a$ and $b$ equals the biggest common tile of $b$ and the leftover. That is precisely the "leftover trick" — any tile that fits $a$ and $b$ must also fit the leftover $r=a-bq$, because it fits $a$ and it fits every $b$-tile.

The magenta tile that covers both bars in the figure also lines up perfectly along the violet leftover chunk. Nothing about the biggest tile is lost when we throw away the big bar and keep the small bar + leftover — so we may safely shrink the problem. Repeat until the leftover is $0$; at that final step the right-hand number is $0$, and the base case $\gcd (a,0)=|a|$ from Section 3 hands back the answer — the last non-zero remainder.

7. One more symbol family: Fibonacci and $\varphi$

The parent's speed section mentions $F_n$ and $\varphi$.

Why the topic needs them: consecutive Fibonacci numbers are the worst case — every quotient $q=1$, so the leftover shrinks as slowly as possible. Because ${\varphi }^n$ grows fast, even the slowest case finishes in about $\log$-many steps.

Prerequisite map

Equipment checklist

Cover the right side and test yourself.

Next: with these symbols secured, revisit Euclidean algorithm — GCD computation, then extend to 2.5.08-extended-euclidean-algorithm and 2.5.10-bezouts-identity — the gateway to 3.2.04-rsa-encryption.