Greatest Common Divisor and Least Common Multiple

What this move does

The largest of the divisors that integers $a$ and $b$ have in common is their greatest common divisor, written $(a,b)$. The smallest of their common positive multiples is their least common multiple, written $[a,b]$. When $(a,b)=1$ we say $a$ and $b$ are coprime.

Once the numbers get big, listing divisors one by one is too slow. The Euclidean algorithm relies on just one fact:

Any number that divides both $a$ and $b$ also divides $r=a-qb$, and any number that divides both $b$ and $r$ also divides $a=qb+r$. The two pairs have exactly the same common divisors, so of course they have the same greatest one.

1. Divide the bigger number by the smaller one and write $a=qb+r$.
2. Take (divisor, remainder) as the new pair and divide again. The numbers keep shrinking, so this must stop.
3. Stop when the remainder is $0$: the divisor on that line is $(a,b)$.

The rectangle on the workbench does the same thing: cut off $q$ squares of side $b$, which leaves a smaller $b\times r$ rectangle, and cut again.

Work through one

That last step was no accident. It works for any two numbers:

Bézout's identity For any integers $a$ and $b$, not both zero, there are integers $x$ and $y$ such that $ax+by=(a,b)$. In particular, $a$ and $b$ are coprime $⟺$ there are integers $x$ and $y$ with $ax+by=1$.

This immediately repairs the broken statement from the previous stop:

If $a\mid bc$ and $(a,b)=1$, then $a\mid c$.

Take $ax+by=1$ and multiply both sides by $c$: $c=a(cx)+(bc)y$. Both terms on the right are divisible by $a$, so $a\mid c$.

The least common multiple

Every time the rectangle is covered, the workbench also reports $[a,b]$. It is tied to $(a,b)$ by a fixed relation:

So you don't need a separate method for the lcm: find $(a,b)$ with the Euclidean algorithm, then divide $ab$ by it. Why this relation holds is something the “exponent bars” at the next stop show at a glance.

When it fails

Practice