Number Theory: GCD & Modular Arithmetic

Most of this course has measured algorithms against the size of their input: $n$ elements, $V$ vertices, $h$ levels of a tree. Number-theoretic algorithms break that habit. Their inputs are single integers, and the interesting cost is measured against the magnitude of those integers, or equivalently the number of bits needed to write them down. The oldest non-trivial algorithm we know, Euclid's, from around 300 BCE, lives here, and it is still the right way to compute a greatest common divisor. This lesson develops it carefully, extends it to solve linear Diophantine equations, and uses both to lay the foundations of modular arithmetic, the arithmetic that underlies hashing, cryptography, and the math problems you will meet in practice.

Divisibility and the greatest common divisor

For integers $a$ and $d$ we say $d$ divides $a$ (written $d ∣ a$ ) if $a = k d$ for some integer $k$ . A common divisor of $a$ and $b$ is an integer dividing both. The greatest common divisor $gcd (a, b)$ is the largest such integer, with the conventions $gcd (a, 0) = ∣ a ∣$ and $gcd (0, 0) = 0$ . Throughout we take $a, b \geq 0$ ; signs only flip the answer's sign.¹

The naive way to compute $gcd (a, b)$ , factoring both numbers and multiplying the shared prime powers, is a trap: integer factorization is believed to be hard, and the sieve and factorization methods that find those prime powers are themselves a separate study. Euclid's insight is that you never need the factorization at all.

Euclid's algorithm

The entire algorithm rests on one recurrence.

The base case is immediate: every integer divides $0$ , so the largest divisor of $a$ and $0$ is $a$ itself. The recurrence follows from a sharper claim: the two pairs share exactly the same set of common divisors, hence the same greatest one.

Because the second argument strictly shrinks ( $a mod b < b$ ) and stays non-negative, the recursion must terminate, and it terminates at a pair $(g, 0)$ whose answer is $g = gcd (a, b)$ .

Algorithm:

\textsc{Euclid}(a, b)

— greatest common divisor,

O(\log\min(a,b))

1
while $b \ne 0$ do
2
$r \gets a \bmod b$
3
$a \gets b$
4
$b \gets r$
5
return $a$

Why it is fast

Each iteration replaces $(a, b)$ with $(b, a mod b)$ . The key fact is that two iterations at least halve the larger argument.

So after every two steps the first argument drops below half its value; the number of iterations is therefore $O (log a) = O (log min (a, b))$ once the first swap orders the arguments.² Each iteration does one division on numbers of $O (log a)$ bits, so the bit-complexity is polynomial in the input size, exponentially better than factoring. (For a refresher on this kind of logarithmic bound, see asymptotic analysis.)

The worst case is slow precisely because every quotient is the smallest it can be, $⌊ a / b ⌋ = 1$ , so each step subtracts $b$ only once and the pair merely slides to the previous Fibonacci pair. A single larger quotient would collapse the chain far faster.

Fibonacci inputs are the worst case: every quotient is

1

, so the pair steps down through every Fibonacci number one rung at a time.

Each iteration simply replaces the pair by $(b, a mod b)$ and recurses; tracing $gcd (48, 18)$ shows the second argument collapsing to $0$ in three steps.

Euclid's remainder steps for

gcd (48, 18) = 6

. Each arrow applies

(a, b) \to (b, a mod b)

: the divisor

b

slides down to become the new first argument and the remainder becomes the new second, until the second argument hits

0

and the first is the answer.

Euclid, geometrically

Replacing $a mod b$ by repeated subtraction gives the subtractive form of the algorithm, and it has a geometric reading: tile an $a \times b$ rectangle greedily with the largest squares that fit. Cut off a $b \times b$ square as many times as you can, then recurse on the leftover $b \times (a mod b)$ strip. The side of the last square is the gcd.

gcd (a, b)

as the largest square that tiles an

a \times b

rectangle

Extended Euclid: Bézout's identity

Euclid tells us what the gcd is; the extended algorithm tells us how to build it out of $a$ and $b$ .

The coefficients $x, y$ fall out of running Euclid in reverse. At the base case $gcd (a, 0) = a$ we have the trivial identity $a \cdot 1 + 0 \cdot 0 = a$ , so $(x, y) = (1, 0)$ . For the recursive step, suppose the recursive call on $(b, a mod b)$ has already returned $(x^{'}, y^{'})$ with $b x^{'} + (a mod b) y^{'} = gcd (a, b) .$ Substitute $a mod b = a - ⌊ a / b ⌋ b$ and regroup by $a$ and $b$ :

a y^{'} + b (x^{'} - ⌊ \frac{a}{b} ⌋ y^{'}) = gcd (a, b) .

So the back-substitution recurrence is

x = y^{'}, y = x^{'} - ⌊ \frac{a}{b} ⌋ y^{'} .

Algorithm:

\textsc{Extended-Euclid}(a, b)

— returns

(g, x, y)

with

ax+by=g=\gcd(a,b)

1
if $b = 0$ then
2
return $(a,\ 1,\ 0)$
3
$(g,\ x',\ y') \gets \textsc{Extended-Euclid}(b,\ a \bmod b)$
4
$x \gets y'$
5
$y \gets x' - \lfloor a / b \rfloor \cdot y'$
6
return $(g,\ x,\ y)$

It performs the same divisions as plain Euclid, so it is also $O (log min (a, b))$ . The table below traces $gcd (240, 46)$ : the forward pass fills the remainder/quotient columns top-down, and the coefficients $(x, y)$ are filled bottom-up by the back-substitution recurrence, landing on Bézout coefficients for the original pair in the top row.

back-substitution yields

a x + b y = gcd

for

gcd (240, 46) = 2

When does $a x + b y = c$ have a solution?

Bézout pins down solvability of the general linear Diophantine equation.

Why. Let $g = gcd (a, b)$ . Any combination $a x + b y$ is a multiple of $g$ , so $g ∣ c$ is necessary. Conversely, if $c = k g$ , scale Bézout's coefficients by $k$ : from $a x_{0} + b y_{0} = g$ we get $a (k x_{0}) + b (k y_{0}) = c$ . This is exactly the predicate behind the Water and Jug Problem (can we measure $c$ liters using jugs of capacity $a$ and $b$ ? iff $g ∣ c$ and $c \leq a + b$ ) and Check if Point Is Reachable, where the reachable lattice is governed by the gcd of the allowed steps.

Modular arithmetic

Fix a modulus $m > 0$ . We say $a$ is congruent to $b$ modulo $m$ , written $a \equiv b (mod m) \leftrightarrow m ∣ (a - b),$ i.e. $a$ and $b$ leave the same remainder on division by $m$ . Congruence is an equivalence relation, and it partitions the integers into $m$ residue classes ${0, 1, \dots, m - 1}$ . The decisive property is that the class operations are well-defined: if $a \equiv a^{'}$ and $b \equiv b^{'}$ , then $a + b \equiv a^{'} + b^{'}, a - b \equiv a^{'} - b^{'}, a \cdot b \equiv a^{'} \cdot b^{'} (mod m) .$ So you may reduce mod $m$ at any point in a chain of $+$ , $-$ , $\times$ without changing the final residue, the foundation of every answer modulo $1 0^{9} + 7$ problem and of combinatorics modulo a prime.³

When two coprime moduli are at play, the residue classes interlock perfectly: the pair $(x mod 3, x mod 5)$ pins $x$ down uniquely modulo $15$ . The grid below tabulates that bijection, with $x = 10 (x mod 3) + 6 (x mod 5)$ landing in each cell, the constructive heart of the Chinese Remainder Theorem we revisit in combinatorics.

x mod 15

recovered from

(x mod 3, x mod 5)

— a bijection of residues

Modular inverse and linear congruences

A modular inverse of $a$ modulo $m$ is an integer $a^{- 1}$ with $a \cdot a^{- 1} \equiv 1 (mod m)$ . It is exactly what lets you divide by $a$ .

Why. The congruence $a x \equiv 1 (mod m)$ is the Diophantine equation $a x + m y = 1$ , which by the corollary above is solvable iff $gcd (a, m) ∣ 1$ , i.e. $gcd (a, m) = 1$ . There are two standard ways to produce the inverse:

Extended Euclid. Run $Extended-Euclid (a, m)$ to get $a x + m y = 1$ . Reducing mod $m$ kills the $m y$ term, leaving $a x \equiv 1 (mod m)$ , so $x mod m$ is the inverse. This works for any coprime modulus and costs $O (log m)$ .
Fermat's little theorem. When $m$ is prime, every $a \neq \equiv 0$ is coprime to $m$ , and $a^{m - 1} \equiv 1 (mod m)$ , hence $a^{- 1} \equiv a^{m - 2} (mod m)$ . Computed by fast exponentiation in $O (log m)$ multiplications, the subject of the next lesson, on modular exponentiation and primality.

The reason an inverse exists exactly when $gcd (a, m) = 1$ is visible directly: multiplying every nonzero residue by such an $a$ permutes them, so some residue must land on $1$ , and that residue is $a^{- 1}$ . Below, multiplying ${1, \dots, 6}$ by $3$ modulo $7$ shuffles the set, and the arrow into $1$ comes from $5$ , so $3^{- 1} \equiv 5$ .

3 \cdot 5 \equiv 1 (mod 7)

, so

3^{- 1} \equiv 5

; multiplying by

3

permutes

{1, \dots, 6}

Algorithm:

\textsc{Mod-Inverse}(a, m)

— inverse of

a

modulo

m

, or "none"

1
$(g,\ x,\ y) \gets \textsc{Extended-Euclid}(a \bmod m,\ m)$
2
if $g \ne 1$ then
3
return "no inverse"
not coprime
4
return $((x \bmod m) + m) \bmod m$
normalize into $[0, m)$

The same machinery solves the general linear congruence $a x \equiv b (mod m)$ . Let $g = gcd (a, m)$ .

When $g = 1$ this reduces to multiply both sides by $a^{- 1}$ and yields the single solution $x \equiv a^{- 1} b (mod m)$ , the everyday case. The general count $g$ is what you reach for when the modulus and coefficient share a factor.

Takeaways

$gcd (a, b)$ is computed by Euclid's algorithm via $gcd (a, b) = gcd (b, a mod b)$ , base $gcd (a, 0) = a$ ; the recurrence is exact because $(a, b)$ and $(b, a mod b)$ have identical common divisors.
Euclid runs in $O (log min (a, b))$ iterations because two steps at least halve the argument; the worst case is consecutive Fibonacci numbers.
Extended Euclid returns Bézout coefficients $x, y$ with $a x + b y = gcd (a, b)$ , and $a x + b y = c$ is solvable iff $gcd (a, b) ∣ c$ , the test behind Water-and-Jug and Check-if-Point-Is-Reachable.
Modular arithmetic is arithmetic on residue classes; $+, -, \times$ are well-defined, but division requires an inverse and overflow must be guarded.
A modular inverse $a^{- 1} mod m$ exists iff $gcd (a, m) = 1$ , found by extended Euclid, or by Fermat ( $a^{m - 2}$ ) when $m$ is prime; the linear congruence $a x \equiv b (mod m)$ is solvable iff $gcd (a, m) ∣ b$ , with exactly $gcd (a, m)$ solutions.

CLRS, Ch. 31 — Number-Theoretic Algorithms (§31.1–31.2): divisibility, common divisors, and the recursive characterization of the gcd. ↩
CLRS, Ch. 31 — Number-Theoretic Algorithms (§31.2): Euclid's and the extended algorithm; the Fibonacci worst case bounds the iteration count to $O (log min (a, b))$ . ↩
Skiena, § — Number Theory: residue classes, congruences, and practical modular-arithmetic pitfalls (overflow, negative remainders). ↩

Divisibility and the greatest common divisor

Euclid's algorithm

Why it is fast

Euclid, geometrically

Extended Euclid: Bézout's identity

When does ax+by=c have a solution?

Modular arithmetic

Modular inverse and linear congruences

Takeaways

Footnotes

When does $a x + b y = c$ have a solution?