Bezout's identity

For non-zero integers \(a\) and \(b\), let \(d\) be the greatest common divisor \(d = gcd(a, b)\). Then there exists integers \(x\) and \(y\) such that

\[ \begin{equation} \label{bezout} ax + by = d \end{equation} \]

If \(a\) and \(b\) are relatively prime then \(gcd(a, b) = 1\) and by Bezout's Identity there are integers \(x\) and \(y\) such that

\[ ax + by = 1 \]

Example: \(3x + 8y = 1\), one solution is \(x = 3\) and \(y = -1\)

Extended Euclidean Algorithm

By reversing the steps of the Euclidean algorithm it's possible to find these integers \(x\) and \(y\), by repeated applications of the euclidean division algorithm we have

\[ \begin{align*} a &= b q_1 + r_1 \\ b &= r_1 q_2 + r_2 \\ & \; \vdots \\ r_{n-3} &= r_{n - 2} q_{n - 1} + r_{n - 1} \\ r_{n-2} &= r_{n - 1} q_{n} + r_{n} \\ r_{n-1} &= r_n q_{n + 1} \end{align*} \]

Where \(r_n = gcd(a, b)\), rewriting \(r_n\) in terms of the previous \(r_i\)

\[ r_n = r_{n - 2} - r_{n - 1} q_n \]

Substituting for \(r_{n - 1}\) from the previous equation

\[ \begin{align*} r_n &= r_{n - 2} - (r_{n - 3} - r_{n - 2} q_{n - 1}) q_n \\ r_n &= r_{n - 2} (1 + q_n q_{n - 1}) - r_{n - 3} q_n \\ r_n &= r_{n - 2}m + r_{n - 3}n \\ \end{align*} \]

Where \(m = 1 + q_n q_{n - 1}\) and \(n = -q_n\), this process is repeated until \(r_n = ax + by\) where \(x\) and \(y\) are integers

Since \(ax + by = gcd(a, b)\) it's also true that

\[ \begin{equation}\label{iteration} bx_1 + (a \% b)y_1 = gcd(a, b) \end{equation} \]

Where \((x_1, y_1)\) are solutions to the new tuple \((b, a \% b)\), converting the value of \(a \% b\)

\[ a \% b = a - \left \lfloor \frac{a}{b} \right \rfloor \cdot b \]

Substituting this value in \eqref{iteration}

\[ \begin{align*} b \cdot x_1 + \Big(a - \left \lfloor \frac{a}{b} \right \rfloor \cdot b \Big) \cdot y_1 &= gcd(a, b) \\ b \cdot x_1 + a \cdot y_1 - \left \lfloor \frac{a}{b} \right \rfloor \cdot b \cdot y_1 &= gcd(a, b) \\ a \cdot y_1 + b \Big( x_1 - \left \lfloor \frac{a}{b} \right \rfloor \cdot y_1 \Big) &= gcd(a, b) \end{align*} \]

Comparing to the original expression \eqref{bezout} we obtain the required coefficients \(x\) and \(y\) based on subsequent values found

\[ x = \begin{cases} 1, & \text{when $a \% b = 0$} \\ y_1, & \text{otherwise} \end{cases} \]

\[ y = \begin{cases} 0, & \text{when $a \% b = 0$} \\ x_1 - \left \lfloor \frac{a}{b} \right \rfloor \cdot y_1, & \text{otherwise} \end{cases} \]

Implementation

/**
 * Computes the values `x` and `y` for the equation
 *
 *    ax + by = gcd(a, b)
 *
 * Given that `a` and `b` are positive integers
 *
 * @param {int} a
 * @param {int} b
 * @param {int} x
 * @param {int} y
 * @returns {int} gcd(a, b)
 */
int extended_euclidean(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int x1, y1;
  int gcd = extended_euclidean(b, a % b, x1, y1);
  x = y1;
  y = x1 - a / b * y1;
  return gcd;
}

/**
 * Alternative version using a vector of ints
 * Computes the values x and y for the equation
 *
 *    ax + by = gcd(a, b)
 *
 * @returns {vector<int>} A triplet with the values (gcd(a, b), x, y)
 */
vector<int> extended_euclidean(int a, int b) {
  if (b == 0) {
    // base case:
    // b divides a so a(1) + b(0) = a
    return vector<int> {a, 1, 0};
  }
  vector<int> t = extended_euclidean(b, a % b);
  int gcd = t[0];
  int x1 = t[1];
  int y1 = t[2];
  return vector<int> {gcd, y1, x1 - a / b * y1};
}

Applications

Diophantine equations

Equations with integer variables and coefficients are called Diophantine equations, the simplest non-trivial linear equation has the form

\[ \begin{equation}\label{linear-diophantine-equation} ax + by = c \end{equation} \]

Where \(a, b, c\) are given integers and \(x, y\) are unknown integers

Using the extended Euclidean algorithm it's possible to find \(x\) and \(y\) given that \(c\) is divisible by \(gcd(a, b)\) otherwise the equation has no solutions, this follows the fact that a linear combination of two numbers continue to be divided by their common divisor, starting with \eqref{bezout}

\[ ax_g + by_g = gcd(a, b) \]

multiplying it by \(\tfrac{c}{gcd(a, b)}\)

\[ \begin{equation}\label{diophantine-equation-gcd} a \cdot x_g \cdot \Big( \frac{c}{gcd(a, b)} \Big) + b \cdot y_g \cdot \Big( \frac{c}{gcd(a, b)} \Big) = c \end{equation} \]

then one of the solutions is given by

\[ ax_0 + by_0 = c \]

where

\[ \begin{cases} x_0 = x_g \cdot \big( \frac{c}{gcd(a, b)} \big) \\ y_0 = y_g \cdot \big( \frac{c}{gcd(a, b)} \big) \end{cases} \]

we can find all of the solutions replacing \(x_0\) by \(x_0 + \tfrac{b}{gcd(a, b)}\) and \(y_0\) by \(y_0 - \tfrac{a}{gcd(a, b)}\)

\[ a \cdot \Big( x_0 + \tfrac{b}{gcd(a, b)} \Big) + b \cdot \Big( y_0 - \tfrac{a}{gcd(a, b)} \Big) = ax_0 + \tfrac{ab}{gcd(a, b)} + by_0 - \tfrac{ab}{gcd(a, b)} = ax_0 + by_0 = c \]

This process could be repeated for any number in the form

\[ \begin{cases} x = x_0 + k \cdot \big( \frac{b}{gcd(a, b)} \big) \\ y = y_0 - k \cdot \big( \frac{a}{gcd(a, b)} \big) \end{cases} \]

Where \(k \in \mathbb{Z}\)

/**
 * Computes the integer values `x` and `y` for the equation
 *
 *    ax + by = c
 *
 * if `c` is not divisible by `gcd(a, b)` then there isn't a valid solution,
 * otherwise there's an infinite number of solutions, (`x`, `y`) form one pair
 * of the set of possible solutions
 *
 * @param {int} a
 * @param {int} b
 * @param {int} c
 * @param {int} x
 * @param {int} y
 * @returns {bool} True if the equation has solutions, false otherwise
 */
bool linear_diophantine_solution(int a, int b, int c, int &x, int &y) {
  int gcd = extended_euclidean(abs(a), abs(b), x, y);
  if (c % gcd != 0) {
    // no solutions since c is not divisible by gcd(a, b)
    return false;
  }
  x *= c / gcd;
  y *= c / gcd;
  if (a < 0) { x *= -1; }
  if (b < 0) { y *= -1; }
  return true;
}

Modular multiplicative inverse

Discussed here

Linear congruence equations

A linear congruence is a congruence \(\pmod p\) of the form

\[ ax \equiv b \pmod m \]

By the definition of the congruence relation \(m \mid ax - b\)

\[ ax - b = my \]

Reordering the equation

\[ ax - my = b \]

Which is a linear diophantine equation discussed above, it's solvable only if \(b\) is divisible by \(gcd(a, m)\), additionally \(gcd(a, m)\) tells us the number of distinct solutions in the ring of integers modulo \(m\)


https://brilliant.org/wiki/bezouts-identity/?subtopic=integers&chapter=greatest-common-divisor-lowest-common-divisor#proof http://www.ugrad.cs.ubc.ca/~cs490/Spring05/notes/nt1.pdf