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

See divisibility for more details.

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

See Modular Arithmetic for more info.

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