---
title: "Number Theory: GCD & Modular Arithmetic"
module: Mathematical Algorithms
moduleNumber: 10
lessonNumber: 1
order: 1001
summary: |
  This lesson opens the mathematical-algorithms module with the bedrock of
  computational number theory. We prove Euclid's recurrence
  $\gcd(a,b)=\gcd(b,\,a\bmod b)$ and its $O(\log\min(a,b))$ running time, extend
  it to recover Bézout coefficients $x,y$ with $ax+by=\gcd(a,b)$, and build
  modular arithmetic on residue classes — including when a modular inverse
  $a^{-1}\bmod m$ exists and how to compute it.
topics: [Number Theory]
sources:
  - book: CLRS
    ref: "Ch. 31 — Number-Theoretic Algorithms"
  - book: Skiena
    ref: "§ — Number Theory"
  - book: Erickson
    ref: "Ch. — (number theory)"
practice:
  - title: 'Greatest Common Divisor of Strings'
    slug: greatest-common-divisor-of-strings
    difficulty: Easy
  - title: 'Find Greatest Common Divisor of Array'
    slug: find-greatest-common-divisor-of-array
    difficulty: Easy
  - title: 'Water and Jug Problem'
    slug: water-and-jug-problem
    difficulty: Medium
  - title: 'Check if Point Is Reachable'
    slug: check-if-point-is-reachable
    difficulty: Hard
---

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, belongs to this family, 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 \mid a$) if
$a = kd$ 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 \ge 0$; signs only flip the answer's sign.[^clrs-gcd]

The naive way to compute $\gcd(a,b)$, factoring both numbers and multiplying the
shared prime powers, is a mistake: integer factorization is believed to be hard, and
the [sieve and factorization methods](/algorithms/mathematical-algorithms/sieve-and-factorization)
that find those prime powers are themselves a separate study. Euclid's insight is
that the factorization is never needed.

## Euclid's algorithm

The entire algorithm rests on one recurrence.

> **Theorem (Euclid).** For $a \ge 0$ and $b > 0$,
> $$\gcd(a,b) = \gcd\parens{b,\ a \bmod b}, \qquad \gcd(a,0) = a.$$

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.

> **Lemma.** The common divisors of $(a,b)$ are precisely the common divisors of
> $(b,\ a \bmod b)$.
>

> **Proof.** Write $r = a \bmod b$, so $a = qb + r$ for the quotient $q =
> \lfloor a/b \rfloor$. Suppose $d \mid a$ and $d \mid b$. Then $d$ divides the
> integer combination $r = a - qb$, so $d$ is a common divisor of $b$ and $r$.
> Conversely, suppose $d \mid b$ and $d \mid r$. Then $d$ divides $a = qb + r$,
> so $d$ is a common divisor of $a$ and $b$. The two divisor sets thus contain
> each other and are equal; their maxima coincide. $\qed$

Because the second argument strictly shrinks ($a \bmod 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
caption: $\textsc{Euclid}(a, b)$ — greatest common divisor, $O(\log\min(a,b))$
while $b \ne 0$ do
  $r \gets a \bmod b$
  $a \gets b$
  $b \gets r$
return $a$
```

::impl{algo="gcd"}

### Why it is fast

Each iteration replaces $(a,b)$ with $(b, a \bmod b)$. The key fact is that two
iterations _at least halve_ the larger argument.

> **Lemma.** If $a > b > 0$ then $a \bmod b < a/2$.
>

> **Proof.** If $b \le a/2$ then $a \bmod b < b \le a/2$. If $b > a/2$ then
> $\lfloor a/b\rfloor = 1$, so $a \bmod b = a - b < a/2$. $\qed$

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.[^clrs-euclid] 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](/algorithms/foundations/asymptotic-analysis).)

> **Intuition.** The _worst case_ is the slowest possible shrinkage, and it is
> achieved by **consecutive Fibonacci numbers**: $\gcd(F_{k+1}, F_k)$ runs for
> exactly $k$ iterations, because $F_{k+1} \bmod F_k = F_{k-1}$ reproduces the
> next Fibonacci pair. Since $F_k \approx \varphi^k$, the iteration count is
> $\Theta(\log_\varphi a)$; the constant in the logarithm is as bad as it can
> get precisely on Fibonacci inputs.

The worst case is slow precisely because every quotient is the smallest it can
be, $\lfloor a/b\rfloor = 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.

$$
% caption: Fibonacci inputs are the worst case: every quotient is $1$, so the pair steps
%          down through every Fibonacci number one rung at a time.
\begin{tikzpicture}[
  every node/.style={font=\small},
  box/.style={draw, minimum width=22mm, minimum height=8mm, inner sep=2pt},
  >=stealth, y=12mm]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-2.7,0.6) rectangle (3.0,-5.3);
  \node[box] (r0) at (0,0) {$\gcd$(13, 8)};
  \node[box] (r1) at (0,-1) {$\gcd$(8, 5)};
  \node[box] (r2) at (0,-2) {$\gcd$(5, 3)};
  \node[box] (r3) at (0,-3) {$\gcd$(3, 2)};
  \node[box] (r4) at (0,-4) {$\gcd$(2, 1)};
  \node[box, fill=acc!15, draw=acc, very thick] (r5) at (0,-5) {$\gcd$(1, 0) = 1};
  \draw[->] (r0) -- node[right=1mm, font=\footnotesize] {q = 1, r = 5} (r1);
  \draw[->] (r1) -- node[right=1mm, font=\footnotesize] {q = 1, r = 3} (r2);
  \draw[->] (r2) -- node[right=1mm, font=\footnotesize] {q = 1, r = 2} (r3);
  \draw[->] (r3) -- node[right=1mm, font=\footnotesize] {q = 1, r = 1} (r4);
  \draw[->] (r4) -- node[right=1mm, font=\footnotesize] {q = 2, r = 0} (r5);
  \node[acc, font=\footnotesize, align=center] at (-1.55,-2.5) {every\\ q = 1};
\end{tikzpicture}
$$

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

$$
% caption: Euclid's remainder steps for $\gcd(48,18)=6$. Each arrow applies
%          $(a,b)\to(b,\ a\bmod 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.
\begin{tikzpicture}[
  every node/.style={font=\small},
  box/.style={draw, minimum width=24mm, minimum height=9mm, inner sep=2pt},
  >=stealth, y=15mm]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-1.6,0.85) rectangle (3.6,-3.35);
  \node[font=\footnotesize, acc] at (0,0.7) {(a, b) to (b, a mod b)};
  \node[box] (r0) at (0,0) {$\gcd$(48, 18)};
  \node[box] (r1) at (0,-1) {$\gcd$(18, 12)};
  \node[box] (r2) at (0,-2) {$\gcd$(12, 6)};
  \node[box, fill=acc!15, draw=acc, very thick] (r3) at (0,-3) {$\gcd$(6, 0) = 6};
  \draw[->] (r0) -- node[right=1mm, font=\footnotesize] {48 mod 18 = 12} (r1);
  \draw[->] (r1) -- node[right=1mm, font=\footnotesize] {18 mod 12 = 6} (r2);
  \draw[->] (r2) -- node[right=1mm, font=\footnotesize] {12 mod 6 = 0} (r3);
\end{tikzpicture}
$$

### Euclid, geometrically

Replacing $a \bmod 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 \bmod
b)$ strip. The side of the _last_ square is the gcd.

$$
% caption: $\gcd(a,b)$ as the largest square that tiles an $a\times b$ rectangle
\begin{tikzpicture}[scale=0.42, every node/.style={font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % a x b rectangle, a = 13 wide, b = 8 tall ; squares of side 8, 5, 3, 2, 2(gcd? gcd=1) -> use 12x8 gcd 4
  % Use 12 x 8: squares 8, then 4x4 twice ; gcd = 4
  \draw[thick] (0,0) rectangle (12,8);
  % first 8x8 square
  \draw (0,0) rectangle (8,8);
  \node at (4,4) {$8$};
  % remaining 4 x 8 strip -> two 4x4 squares
  \draw (8,0) rectangle (12,4);
  \node at (10,2) {$4$};
  % the final square = gcd, highlighted
  \draw[acc, very thick] (8,4) rectangle (12,8);
  \node[acc] at (10,6) {$\gcd$};
  \node at (6,-1.2) {$a = 12$};
  \node[rotate=90] at (-1.2,4) {$b = 8$};
\end{tikzpicture}
$$

## 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$.

> **Theorem (Bézout).** For all integers $a,b$ there exist integers $x,y$ with
> $$ax + by = \gcd(a,b).$$

> **Proof.** Run 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 \bmod b)$ has already
> returned $(x', y')$ with
> $$b\,x' + (a \bmod b)\,y' = \gcd(a,b).$$
> Substitute $a \bmod b = a - \lfloor a/b\rfloor\, b$ and regroup by $a$ and $b$:
> $$a\,y' + b\Bigl(x' - \Bigl\lfloor \tfrac{a}{b}\Bigr\rfloor\,y'\Bigr) = \gcd(a,b).$$
> The recursion bottoms out at the base case, so by induction the coefficients
> exist at every level. $\qed$

So the **back-substitution recurrence** is
$$
x = y', \qquad y = x' - \Bigl\lfloor \tfrac{a}{b}\Bigr\rfloor\, y'.
$$

```algorithm
caption: $\textsc{Extended-Euclid}(a, b)$ — returns $(g, x, y)$ with $ax+by=g=\gcd(a,b)$
if $b = 0$ then
  return $(a,\ 1,\ 0)$
$(g,\ x',\ y') \gets \textsc{Extended-Euclid}(b,\ a \bmod b)$
$x \gets y'$
$y \gets x' - \lfloor a / b \rfloor \cdot y'$
return $(g,\ x,\ y)$
```

::impl{algo="extended_gcd"}

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.

$$
% caption: back-substitution yields $ax+by=\gcd$ for $\gcd(240,46)=2$
\begin{tikzpicture}[scale=1, every node/.style={font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % header
  \node at (0,0) {$a$};
  \node at (1.4,0) {$b$};
  \node at (2.9,0) {q = f\/loor(a/b)};
  \node at (4.8,0) {$r$};
  \node at (6.0,0) {$x$};
  \node at (7.0,0) {$y$};
  \draw[thick] (-0.6,-0.35) -- (7.6,-0.35);
  % rows
  \node at (0,-0.9) {240};  \node at (1.4,-0.9) {46};  \node at (2.9,-0.9) {5};  \node at (4.8,-0.9) {10};  \node at (6.0,-0.9) {-9}; \node at (7.0,-0.9) {47};
  \node at (0,-1.6) {46};   \node at (1.4,-1.6) {10};  \node at (2.9,-1.6) {4};  \node at (4.8,-1.6) {6};   \node at (6.0,-1.6) {2};  \node at (7.0,-1.6) {-9};
  \node at (0,-2.3) {10};   \node at (1.4,-2.3) {6};   \node at (2.9,-2.3) {1};  \node at (4.8,-2.3) {4};   \node at (6.0,-2.3) {-1}; \node at (7.0,-2.3) {2};
  \node at (0,-3.0) {6};    \node at (1.4,-3.0) {4};   \node at (2.9,-3.0) {1};  \node at (4.8,-3.0) {2};   \node at (6.0,-3.0) {1};  \node at (7.0,-3.0) {-1};
  \node at (0,-3.7) {4};    \node at (1.4,-3.7) {2};   \node at (2.9,-3.7) {2};  \node at (4.8,-3.7) {0};   \node at (6.0,-3.7) {0};  \node at (7.0,-3.7) {1};
  \node at (0,-4.4) {2};    \node at (1.4,-4.4) {0};   \node at (2.9,-4.4) {-};  \node at (4.8,-4.4) {-};   \node at (6.0,-4.4) {1};  \node at (7.0,-4.4) {0};
  % highlight the Bezout coefficients in the top row
  \draw[acc, very thick] (5.55,-0.6) rectangle (7.45,-1.2);
  \node[acc] at (3.6,-5.2) {240 (-9) + 46 (47) = 2 = $\gcd$(240, 46)};
\end{tikzpicture}
$$

### When does $ax + by = c$ have a solution?

Bézout characterizes exactly when the general **linear Diophantine equation** is
solvable.

> **Corollary.** $ax + by = c$ has an integer solution $(x,y)$ **if and only if**
> $\gcd(a,b) \mid c$.

> **Proof.** Let $g = \gcd(a,b)$. Any combination $ax+by$ is a multiple of $g$,
> so $g \mid c$ is necessary. Conversely, if $c = kg$, scale Bézout's
> coefficients by $k$: from $ax_0 + by_0 = g$ we get $a(kx_0) + b(ky_0) = c$.
> $\qed$

This is the
predicate behind the **Water and Jug Problem** (can we measure $c$ liters using
jugs of capacity $a$ and $b$? iff $g \mid c$ and $c \le a+b$) and **Check if
Point Is Reachable**, where the reachable lattice is governed by the gcd of the
allowed steps.

::impl{algo="linear_diophantine"}

## Modular arithmetic

Fix a modulus $m > 0$. We say $a$ is **congruent** to $b$ modulo $m$, written
$$a \equiv b \pmod m \iff m \mid (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', \quad a - b \equiv a' - b', \quad a\cdot b \equiv a'\cdot b' \pmod 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 $10^9+7$"
problem and of [combinatorics modulo a prime](/algorithms/mathematical-algorithms/combinatorics).[^skiena-mod]

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

$$
% caption: $x\bmod 15$ recovered from $(x\bmod 3,\ x\bmod 5)$ — a bijection of residues
\begin{tikzpicture}[every node/.style={font=\small}, x=8mm, y=8mm]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \c/\lab in {0/0,1/1,2/2,3/3,4/4}{
    \node at (\c+1,1) {$\lab$};
  }
  \foreach \r/\lab in {0/0,1/1,2/2}{
    \node at (0,-\r) {$\lab$};
  }
  \node[font=\footnotesize] at (3,2) {$x\bmod 5$};
  \node[font=\footnotesize, rotate=90] at (-1,-1) {$x\bmod 3$};
  \fill[acc!15] (3.5,-2.5) rectangle (4.5,-1.5);
  \foreach \r in {0,1,2}{
    \foreach \c in {0,1,2,3,4}{
      \node[draw, minimum size=8mm, inner sep=0] at (\c+1,-\r) {$\pgfmathparse{int(mod(10*\r + 6*\c, 15))}\pgfmathresult$};
    }
  }
  \node[draw=acc, very thick, minimum size=8mm, inner sep=0] at (4,-2) {};
  \node[acc, font=\footnotesize] at (3,-3.4) {8 = 2 (mod 3),\quad 8 = 3 (mod 5)};
\end{tikzpicture}
$$

> **Warning (Pitfalls).**
> 1. **Division is not generally legal.** From $ax \equiv ay \pmod m$ you may
>    _not_ conclude $x \equiv y$. For example $2\cdot 3 \equiv 2\cdot 0 \pmod 6$
>    but $3 \not\equiv 0$. Cancellation needs a _modular inverse_ (next section).
> 2. **Overflow.** Even when each operand fits in a machine word, $a\cdot b$ can
>    overflow before you reduce. Reduce operands first, use a wider type, or
>    multiply with care.
> 3. **Negative remainders.** In many languages `a % m` can be negative; normalize
>    with `((a % m) + m) % m` when you need a representative in $[0,m)$.

## Modular inverse and linear congruences

A **modular inverse** of $a$ modulo $m$ is an integer $a^{-1}$ with
$a\cdot a^{-1} \equiv 1 \pmod m$. It is what lets you "divide" by $a$.

> **Theorem.** $a^{-1} \bmod m$ exists **if and only if** $\gcd(a,m) = 1$ (we
> say $a$ is _coprime_ to $m$), and when it exists it is unique modulo $m$.

> **Proof.** The congruence $ax \equiv 1 \pmod m$ is the Diophantine equation
> $ax + my = 1$, which by the corollary above is solvable iff $\gcd(a,m) \mid 1$,
> i.e. $\gcd(a,m) = 1$. For uniqueness, if $ax \equiv ax' \equiv 1$ then
> $a(x - x') \equiv 0$, and multiplying by either inverse forces $x \equiv x'
> \pmod m$. $\qed$

There are two standard ways to produce the inverse:

1. **Extended Euclid.** Run $\textsc{Extended-Euclid}(a, m)$ to get
   $ax + my = 1$. Reducing mod $m$ kills the $my$ term, leaving
   $ax \equiv 1 \pmod m$, so $x \bmod m$ is the inverse. This works for _any_
   coprime modulus and costs $O(\log m)$.
2. **Fermat's little theorem.** When $m$ is **prime**, every $a \not\equiv 0$ is
   coprime to $m$, and $a^{m-1} \equiv 1 \pmod m$, hence
   $a^{-1} \equiv a^{m-2} \pmod m$. Computed by fast exponentiation in
   $O(\log m)$ multiplications, the subject of the next lesson, on
   [modular exponentiation and primality](/algorithms/mathematical-algorithms/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$.

$$
% caption: $3\cdot 5\equiv 1\pmod 7$, so $3^{-1}\equiv 5$; multiplying by $3$ permutes
%          $\{1,\dots,6\}$
\begin{tikzpicture}[every node/.style={font=\small}, >=stealth, x=10mm, y=10mm]
  \definecolor{acc}{HTML}{2348F2}
  \fill[acc!15] (5,1) circle (4mm);
  \fill[acc!15] (5,-1) circle (4mm);
  \foreach \a in {1,2,3,4,5,6}{
    \node[draw, circle, minimum size=8mm, inner sep=0] (t\a) at (\a,1) {$\a$};
  }
  \foreach \a/\b in {1/3,2/6,3/2,4/5,5/1,6/4}{
    \node[draw, circle, minimum size=8mm, inner sep=0] (b\a) at (\a,-1) {$\b$};
    \draw[->] (t\a) -- (b\a);
  }
  \node[draw=acc, circle, very thick, minimum size=8mm, inner sep=0] at (5,1) {};
  \node[draw=acc, circle, very thick, minimum size=8mm, inner sep=0] at (5,-1) {};
  \node[acc, font=\footnotesize] at (5,-2.3) {3 (5) = 1 (mod 7)};
  \node[font=\footnotesize] at (-0.3,1) {$a$};
  \node[font=\footnotesize] at (-0.6,-1) {$3a\bmod 7$};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Mod-Inverse}(a, m)$ — inverse of $a$ modulo $m$, or "none"
$(g,\ x,\ y) \gets \textsc{Extended-Euclid}(a \bmod m,\ m)$
if $g \ne 1$ then
  return "no inverse"   // not coprime
return $((x \bmod m) + m) \bmod m$   // normalize into $[0, m)$
```

::impl{algo="mod_inverse"}

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

> **Theorem.** $ax \equiv b \pmod m$ is solvable **iff** $g \mid b$. When it is,
> there are **exactly $g$** solutions modulo $m$. A particular solution is
> $x_0 = (b/g)\cdot a'^{-1} \bmod (m/g)$, where $a' = a/g$; the full solution set
> is $x_0 + k\,(m/g)$ for $k = 0, 1, \dots, g-1$.

When $g = 1$ this reduces to "multiply both sides by $a^{-1}$" and yields the
single solution $x \equiv a^{-1}b \pmod m$, the everyday case. The general count
$g$ applies when the modulus and coefficient share a factor.

::impl{algo="linear_congruence"}

**Worked example (a linear congruence with a shared factor).** Solve
$6x \equiv 8 \pmod{14}$. Here $a = 6$, $b = 8$, $m = 14$, and
$g = \gcd(6,14) = 2$. Since $g = 2$ divides $b = 8$, the congruence is solvable,
and the theorem promises **exactly $g = 2$** solutions modulo $14$. Divide the
whole congruence through by $g$: with $a' = 3$, $b' = 4$, $m' = 7$ we solve
$3x \equiv 4 \pmod 7$. The inverse $3^{-1} \equiv 5 \pmod 7$ (from the permutation
figure above), so $x_0 \equiv 5 \cdot 4 \equiv 20 \equiv 6 \pmod 7$. Lifting back
to modulus $14$, the two solutions are $x_0$ and $x_0 + m' = 6$ and $13$. Checking:
$6 \cdot 6 = 36 \equiv 8 \pmod{14}$ and $6 \cdot 13 = 78 \equiv 8 \pmod{14}$, both
correct.

## GCD refinements and where Bézout matters

Euclid's algorithm is the oldest non-trivial algorithm in continuous use, and the
modern refinements of it are worth knowing.

**Binary GCD (Stein's algorithm).** Division is expensive on hardware that lacks a
fast divide, and each Euclid step needs a modulo. In 1967 Josef Stein published a
variant that uses only **subtraction, comparison, and shifts** — no division at
all.[^stein] It rests on three facts: $\gcd(2a, 2b) = 2\gcd(a,b)$ (pull out a
common factor of two), $\gcd(2a, b) = \gcd(a, b)$ when $b$ is odd (a factor of two
in one argument alone is irrelevant to an odd gcd), and $\gcd(a,b) =
\gcd(\lvert a-b\rvert,\, \min(a,b))$ for $a,b$ odd. Stripping factors of two is a
single shift instruction, so binary GCD is often faster in practice than Euclid
despite touching the same $O(\log)$ number of bits. On $\gcd(24, 18)$: pull out one
common $2$ to reach $2\gcd(12,9)$; $12$ is even and $9$ odd, so drop that factor to
$2\gcd(6,9)$, then $2\gcd(3,9)$; both odd now, subtract to $2\gcd(6,3)=2\gcd(3,3)=2
\cdot 3 = 6$.

**Bit complexity, done honestly.** Counting each division as one step gives
$O(\log \min(a,b))$ **operations**, but on numbers of $n = O(\log a)$ bits, one
schoolbook division already costs $O(n^2)$ bit operations, so Euclid is $O(n^3)$
bit operations in the naive accounting. The **half-GCD** algorithm, using
fast multiplication, computes a gcd in $O(n\log^2 n\log\log n)$ bit operations by a
Knuth–Schönhage divide-and-conquer that processes the high-order bits in one
batch,[^knuth-half] the same asymptotic class as multiplication itself. This is
what large-integer libraries (GMP) actually run for big inputs.

**Where Bézout coefficients matter.** The extended algorithm's
coefficients $(x,y)$ serve directly as the modular inverse ($x \bmod m$), the CRT
reconstruction weights, and the private exponent in RSA key generation ($d \equiv
e^{-1} \pmod{\varphi(N)}$ is one extended-Euclid call). Every time a cryptographic
library "inverts modulo the group order," it is running the algorithm on this page.

## Takeaways

- **$\gcd(a,b)$** is computed by **Euclid's algorithm** via
  $\gcd(a,b)=\gcd(b,\,a\bmod b)$, base $\gcd(a,0)=a$; the recurrence is exact
  because $(a,b)$ and $(b,\,a\bmod 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
  $ax+by=\gcd(a,b)$, and $ax+by=c$ is solvable **iff $\gcd(a,b)\mid 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}\bmod m$ exists **iff $\gcd(a,m)=1$**, found by
  extended Euclid, or by **Fermat ($a^{m-2}$)** when $m$ is prime; the linear
  congruence $ax\equiv b\pmod m$ is solvable iff $\gcd(a,m)\mid b$, with exactly
  $\gcd(a,m)$ solutions.

[^clrs-gcd]: **CLRS**, Ch. 31 — Number-Theoretic Algorithms (§31.1–31.2): divisibility, common divisors, and the recursive characterization of the gcd.
[^clrs-euclid]: **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-mod]: **Skiena**, § — Number Theory: residue classes, congruences, and practical modular-arithmetic pitfalls (overflow, negative remainders).
[^stein]: J. Stein, "Computational problems associated with Racah algebra," _Journal of Computational Physics_ **1**(3), 1967 — the binary (shift-and-subtract) GCD; see also **Knuth**, _The Art of Computer Programming_, Vol. 2 §4.5.2.
[^knuth-half]: **Knuth**, _The Art of Computer Programming_, Vol. 2 §4.5.2 (the half-GCD / Schönhage recursion): a gcd in $O(n\log^2 n\log\log n)$ bit operations via fast multiplication.