Euclidean Algorithm

Compute the GCD with repeated division, shown as tiling a rectangle with squares

Beginner
Try:

Enter two whole numbers between 1 and 1000.

Why repeated division works

The greatest common divisor of a and b is the largest number that divides both. Instead of listing factors, Euclid noticed that if a = q·b + r, then gcd(a, b) = gcd(b, r): any number that divides a and b also divides r = a − q·b, and any number that divides b and r also divides a. So we can replace the pair with a smaller pair without changing the answer.

The remainders shrink every step, so they must eventually reach 0. At that point gcd(g, 0) = g, and the last non-zero remainder is the GCD.

Geometrically, the GCD is the side of the largest square tile that can cover an a × b rectangle exactly. Cutting off as many b × b squares as possible leaves an r × b strip, and any square that tiles the whole rectangle must also tile that strip. Repeat until the strip is covered by squares with no leftover.

Key formulas

Division step

a = q·b + r  ⟹  gcd(a, b) = gcd(b, r)

q
the quotient, ⌊a / b⌋
r
the remainder, 0 ≤ r < b

Least common multiple

lcm(a, b) = a·b / gcd(a, b)

Compute it as (a / gcd)·b to keep the intermediate numbers small.

Bézout's identity

gcd(a, b) = s·a + t·b

s, t
integers found by the extended Euclidean algorithm

Running the division steps backwards (back-substitution) writes the GCD as a combination of a and b. When gcd = 1, s is the inverse of a modulo b, which is how RSA keys are computed.

How to use this visualizer

  1. 1
    Enter two whole numbers a and b, or pick one of the suggested pairs.
  2. 2
    Press Start over, then Next step to perform one division at a time. Each row and its squares share a colour.
  3. 3
    Watch the rectangle: each step places the largest squares that fit in the strip left over by the previous step.
  4. 4
    When the remainder reaches 0, read off the GCD (the side of the smallest square) and the LCM.
  5. 5
    Tick "Show extended Euclid" to see the table that produces the Bézout coefficients s and t.

The algorithm in code

Python
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b

Time complexity

O(log min(a, b))

The remainder at least halves every two steps. Consecutive Fibonacci numbers, such as 89 and 55, are the slowest case.

Space complexity

O(1)

Only the current pair is kept.

Practice problems

Problem 1: GCD and LCM

Use the Euclidean algorithm to find gcd(252, 105), then find lcm(252, 105).
Show solution

252 = 2 × 105 + 42

105 = 2 × 42 + 21

42 = 2 × 21 + 0

gcd(252, 105) = 21

lcm = 252 × 105 / 21 = 12 × 105 = 1260

Problem 2: Bézout coefficients

Find integers s and t with 240s + 46t = gcd(240, 46).
Show solution

240 = 5 × 46 + 10

46 = 4 × 10 + 6

10 = 1 × 6 + 4

6 = 1 × 4 + 2

4 = 2 × 2 + 0, so gcd = 2

Back-substitute:

2 = 6 − 4 = 6 − (10 − 6) = 2·6 − 10

  = 2(46 − 4·10) − 10 = 2·46 − 9·10

  = 2·46 − 9(240 − 5·46) = 47·46 − 9·240

s = −9, t = 47 (check: −2160 + 2162 = 2)

Discussion

Questions, ideas or a different approach? Join the conversation.