## 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;
int x1 = t;
int y1 = t;
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;
}


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