Modular Arithmetic and the Euclidean Algorithm

Work with remainders like clock numbers, then use repeated division to find the greatest common divisor.

By Rishipal Singh · · 6 min read

Remainders wrap around a clock; repeated remainders reveal the GCD.
Visual guide: Remainders wrap around a clock; repeated remainders reveal the GCD.

Modular arithmetic is arithmetic with remainders. A clock is a familiar example: after 12 comes 1, so adding hours behaves like arithmetic modulo 12.

Remainders wrap around

We write a ≡ b (mod m) when a and b have the same remainder after division by m. For example, 17 ≡ 5 (mod 12). This lets us keep numbers small when only their remainders matter.

Congruences work well with addition and multiplication: if two numbers are replaced with congruent numbers, their sums and products remain congruent under the same modulus.

Find a greatest common divisor

The greatest common divisor (GCD) of two integers is the largest positive integer that divides both. The Euclidean algorithm uses the fact that the common divisors of a and b are exactly the common divisors of b and the remainder of a divided by b.

gcd(a, b) = gcd(b, a mod b)

Repeat the step until the remainder is zero. The last non-zero value is the GCD. For example, gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = 6.

Where these ideas show up

Remainders help with cyclic schedules, checksums, and modular hashes. The Euclidean algorithm is used in number theory and cryptography, and its repeated shrinking makes it efficient even for large integers.

Practice: run one Euclidean step

Using gcd(48, 18) = gcd(18, 48 mod 18), what pair remains after the first step?

Reveal the explanation

48 mod 18 is 12, so the next pair is (18, 12). Continue with (12, 6), then the remainder is 0, so the GCD is 6.