Euclidean Algorithm

gcd by repeated division; coprimality and the gcd·lcm identity.

The idea

The Euclidean algorithm computes the greatest common divisor of two integers without factoring either one. Here $\gcd(a, b)$, the greatest common divisor, is the largest integer that divides both $a$ and $b$.

The algorithm rests on one observation. Write $a = bq + r$. Any integer dividing both $a$ and $b$ divides $r = a - bq$, and any integer dividing both $b$ and $r$ divides $a = bq + r$. The pairs $(a, b)$ and $(b, r)$ therefore have the same common divisors, and in particular the same greatest one: $\gcd(a, b) = \gcd(b,\ a \bmod b).$ The algorithm repeats this step until the remainder is $0$:

Algorithm.

Algorithm: Euclidean Algorithm Input: integers a ≥ b ≥ 0, not both 0 Output: gcd(a, b) 1. if b = 0, return a // gcd(a, 0) = a 2. r = a mod b 3. a = b, b = r // replace (a, b) by (b, a mod b) 4. go to step 1

Each remainder is strictly smaller than the last, so the loop must stop, and it stops at a pair $(g, 0)$, whose gcd is $g$: the last nonzero remainder is the answer.

Two integers with $\gcd(a, b) = 1$ share no factor beyond $1$ and are called coprime. Neither has to be prime for that.

Ways to work on it

• Walkthrough. Run the Euclidean algorithm; coprimality.
• Proof. See why it lands on the gcd — dots grouped into unbreakable triangles.
• Practice. Compute a gcd with the Euclidean algorithm.
• Hardest. Find the gcd and then the lcm of the same pair of numbers.

Not sure where to start? Take the ten-question placement test.