JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

The Division Algorithm and the Euclidean Algorithm

Every division leaves a unique quotient and remainder — and chasing remainders gives the fastest way ever found to compute a greatest common divisor.

Division with a remainder, made precise

When you divide one integer by another, you usually do not land exactly. The [[division-algorithm|division algorithm]] says this precisely: for any integer a and any positive integer b, there is exactly one pair of integers q (the quotient) and r (the remainder) with a = b·q + r and 0 ≤ r < b. The remainder is always nonnegative and strictly smaller than what you divided by.

Divide 47 by 6:
  47 = 6 · 7 + 5     (q = 7, r = 5,  0 ≤ 5 < 6) ✓

Divide -47 by 6 (watch the sign!):
  -47 = 6 · (-8) + 1   (q = -8, r = 1)
  NOT  6 · (-7) - 5, because r must satisfy 0 ≤ r < 6.

The remainder r = 0 exactly when b divides a.
The remainder must stay in the range 0 ≤ r < b — even for negative dividends.

Chasing remainders to the GCD

The [[greatest-common-divisor|greatest common divisor]] of two numbers is the same idea as the greatest common factor from Guide 1, just under a fancier name. Listing all factors is slow for big numbers. The [[euclidean-algorithm|Euclidean algorithm]] is dramatically faster, and it rests on one beautiful fact: gcd(a, b) = gcd(b, r), where r is the remainder when a is divided by b. Replacing the larger pair by a smaller one keeps the GCD unchanged, so you simply repeat until the remainder hits 0.

gcd(252, 105):
  252 = 105 · 2 + 42
  105 =  42 · 2 + 21
   42 =  21 · 2 +  0   ← remainder 0, stop

The last NONZERO remainder is 21.
So gcd(252, 105) = 21.

(Compare: 252 = 2^2·3^2·7, 105 = 3·5·7,
 shared part = 3·7 = 21. Same answer.)
Each line feeds its divisor and remainder into the next; the last nonzero remainder is the GCD.
  1. Divide the larger number by the smaller; record the remainder.
  2. Now divide the previous divisor by that remainder; record the new remainder.
  3. Keep going. When a remainder of 0 appears, the divisor on that line is the GCD.

A bonus: working backwards

If you run the Euclidean algorithm and then read the lines back upward, you can write the GCD as a combination d = a·x + b·y for some integers x and y. This is [[bezouts-identity|Bezout's identity]], and it is the engine behind solving the equations in the next guide. Two numbers are [[relatively-prime|relatively prime]] exactly when their GCD is 1 — when their factorizations share no prime at all.