Recipe

Compute gcd(a, b) and Bezout's x, y with the Euclidean algorithm

Use when: you're given two positive integers a and b and need gcd(a, b), or integers x, y with ax + by = gcd(a, b)

Goal: the greatest common divisor of a and b, and, if needed, integers x and y expressing it as ax + by

Taught in The greatest common divisor and group structure

1. 1

   Write a = bq + r using the division algorithm, with 0 \le r < b.

   Example

   For a=56, b=20: 56 = 20(2) + 16. New pair: (20, 16).

   ⚡ Shortcut

   If b divides a exactly, the very first leftover is 0 and \gcd(a,b)=b -- the whole algorithm ends after one division.

   Why: any common divisor of a and b also divides r = a - qb, so swapping in the pair (b, r) never loses or gains a common divisor.

2. 2

   Divide the previous divisor by the previous leftover, and keep going until a leftover of 0 turns up.

   Example

   Continuing with (20, 16): 20 = 16(1) + 4, new pair (16, 4). Then 16 = 4(4) + 0, leftover 0, so the algorithm stops.

   • the leftover is 0 — stop; the last nonzero leftover is \gcd(a, b).
   • the leftover is still nonzero — repeat this step again with the new pair.

   Why: each pass shrinks the pair while keeping every common divisor the same, so the process must reach a 0 leftover in finitely many steps, and whatever divisor survives to that point is \gcd(a, b).

3. 3

   Solve the second-to-last division for its leftover. Then, working back toward a and b, swap in each earlier leftover using the equation that produced it.

   Example

   From 20 = 16(1)+4: 4 = 20 - 16(1). Replace 16 using 56 = 20(2)+16, i.e. 16 = 56 - 20(2): 4 = 20 - (56 - 20(2))(1) = 20(3) - 56(1) So x=-1, y=3: check 56(-1) + 20(3) = -56+60 = 4.

   Why: every division equation from Step 1 or 2 can be solved for its leftover, then dropped into the equation after it. Working backward through the same equations writes the final gcd as ax+by.