Motivation§

One of the simplest Diophantine equations is of the form $ax + by = c$. The extended Euclidean algorithm can solve for the greatest common divisor (GCD) between two numbers. The algorithm happens to also solve the Diophantine equation of the form $ax + by = \gcd(x, y)$, where the coefficients $a$ and $b$ are the Bézout coefficients.

When working in a modular group, Bézout coefficients are useful in a computing the modular inverse of a number, i.e. given $a$ find $b$ such that $ab \equiv_n 1$.

Greatest Common Divisor§

Greatest Common Divisor

The greatest common divisor (GCD) is the greatest divisor shared between two numbers.

We often write $(a, b)$ to denote the GCD between $a$ and $b$, rather than writing $\gcd(a, b)$.

Properties of the GCD:

  1. $(a, b) = (b, a)$.
  2. $(0, b) = b$, zero is divisible by any number.
  3. $(n\cdot a, n\cdot b) = n\cdot (a, b)$.
  4. $(2a, b) = (a, b)$ if $b$ is odd.
  5. $(a, b) = (\vert a - b\vert, \min(a, b))$ if $u, v$ odd.

These properties are extremely useful in an implementation called “binary GCD”. For example, in a C++ fixed-precision integer setting using GCC, we can use __builtin_ctz() to compute case (3) extremely quickly in the case that $n = 2^k$ using bit operations.

Euclidean Algorithm§

Theorem 3.1

If $(b, c) = g$, then there exists integers $x_0, y_0$ satisfying the linear Diophantine equation:

$$ bx_0 + cy_0 = (b, c). $$

Let $A = {bx + cy, x, y \in \mathbb{Z}}$. Choose $x_0, y_0$ such that $l = bx_0 + cy_0$ is the least positive integer in $A$. Now we want to show that $l = g$.

  1. Seeking a contradiction, assume $l \nmid b$. Then the division algorithm gives that $b = lq + r$ for some integers $q, r$ where $0 \lt r \lt l$.

    Then, $r = b - lq = b - q(bx_0 + cy_0) = b(1 - qx_0) + c(-qy_0)$. This results in $r \in A$ and $0 \lt r \lt l$, contradiction. The same argument applied on $c$ shows that $l \vert c$.

  2. Let $g = (b, c)$, then there exists integers $B, C$ such that $gB = b$ and $gC = c$. So $l = bx_0 + cy_0 = g(Bx_0 + Cy_0)$, so $g \vert l$. Then $g \leq l$, $l \vert b$ and $l \vert c$. Therefore, $l$ is the greatest common divisor.

Euclidean Algorithm

Given integers $b, c$ not both equal to zero, the Euclidean algorithm is defined as

$$ \begin{array}{l c l} b = cq_1 + r_1 & \quad & r_1 \in (0\dots c)\\ c = r_1q_2 + r_2 & & r_2 \in (0\dots r_1)\\ r_1 = r_2q_3 + r_3 & & r_3 \in (0\dots r_1)\\ & \vdots &\\ r_{j - 2} = r_{j-1}q_j + r_j &&r_j \in (0\dots r_{j-1})\\ r_{j - 1} = r_jq_{j + 1} & & \text{stop when } r_{j + 1} = 0. \end{array} $$

Then, the value $r_j = (b, c)$.

Bézout Coefficients§

The extended Euclidean algorithm can be used to find Bézout coefficients, i.e. in a given $a, b$ we can find coefficients $s, t$ for the linear Diophantine equation satisfying

$$ s\cdot a + t\cdot b = (a, b). $$

Extended Euclidean Algorithm

Following the same steps as in the regular Euclidean algorithm, we can find a solution to $bx_0 + cy_0=(b,c)$ by rewriting each $r_i$ in terms of $b$ and $c$.

$$ \begin{align*} r_1 &= b - cq_1\\\\ r_2 &= c - r_1q_2\\\\ &= c - (b - cq_1)q_2\\\\ &\mkern.5em\vdots\\\\ r_j &= c\underbrace{(q\_1\cdot q\_2\cdot \dots)}\_{y\_0} + b\underbrace{(q\_2 \cdot \dots)}\_{x\_0} \end{align*} $$

The values $x_0$ and $y_0$ are our Bézout coefficients.

Modular Inverse§

Modular Inverse

Given $a \in \mathbb{Z}_n$ and $(a, n) = 1$, we say that $b$ is the modular inverse of $a$ mod $n$ iff

$$ a\cdot b \equiv_n 1. $$

We also write $b = a^{-1}$. Keep in mind that we are in $\mathbb{Z}_n$, therefore $a^{-1}$ must also be an integer.

If we want to find the modular inverse of $a$ modulo $n$, we can use the extended Euclidean algorithm on $(a, n)$. Then, the Bézout coefficient corresponding to $a$ is congruent to the modular inverse of $a$.