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

$$$$\label{bezout} ax + by = d$$$$

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

$$$$\label{iteration} bx_1 + (a \% b)y_1 = gcd(a, b)$$$$

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$$ $$\label{linear-diophantine-equation} ax + by = c$$ $$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)}$$ $$\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$$ $$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$