Bezouts Identity and the Extended Euclidean Algorithm

The Euclidean Algorithm in Reverse#

Recall that the Euclidean algorithm finds $\gcd(a,b)$ by repeatedly applying the division theorem until the remainder hits $0$ ; the last non-zero remainder is the gcd. Running it on $403$ and $286$ :

\begin{align*} 403 &= 1 \times 286 + 117, && (1)\\ 286 &= 2 \times 117 + 52, && (2)\\ 117 &= 2 \times 52 + 13, && (3)\\ 52 &= 4 \times 13 + 0, \end{align*}

so $\gcd(403,286) = 13$ .

Notice how each line lets us rewrite its remainder in terms of the two numbers sitting above it; i.e. line $(3)$ says $13 = 117 - 2 \times 52$ . If we start at the penultimate line and keep substituting upwards, we can eventually write the gcd using only $403$ and $286$ :

\begin{align*} 13 &= 117 - 2 \times 52 && \text{(from } (3))\\ &= 117 - 2 \times (286 - 2 \times 117) && \text{(substituting from } (2))\\ &= 5 \times 117 - 2 \times 286 && \text{(collecting terms)}\\ &= 5 \times (403 - 286) - 2 \times 286 && \text{(substituting from } (1))\\ &= 5 \times 403 - 7 \times 286 && \text{(collecting terms)}. \end{align*}

Therefore, we have written $\gcd(403,286)$ in the form $403x + 286y$ , specifically with $x = 5$ and $y = -7$ . An expression of the form $ax+by$ , where $x,y \in \mathbb{Z}$ , is called an integer linear combination of $a$ and $b$ ; basically, what we just showed is that the gcd of two numbers can be built out of the numbers themselves.

When collecting terms, never evaluate the products (do not turn $5 \times 117$ into $585$ ); every line must stay as a combination of two of the remainders, otherwise you lose the structure you are trying to find. The whole point is to keep $403$ and $286$ visible so the final coefficients can be read straight off.

Bézout's Identity#

The back-substitution method clearly works for any pair of integers, not just $403$ and $286$ ; this generalisation is the main theorem of this lecture.

Note

Theorem (Bézout's Identity)
Given any integers $a$ and $b$ , there exist integers $x$ and $y$ such that

\boxed{\gcd(a,b) = ax + by.}

Basically, no matter which two integers you pick, their gcd is always reachable as an integer linear combination of them. The proof approach is exactly what we did above: apply the Euclidean algorithm to $a$ and $b$ , then work backwards through the lines, substituting for each remainder until only $a$ and $b$ are left.

It is important to note that the solution pair $(x,y)$ is not unique. We found $13 = 5 \times 403 + (-7) \times 286$ , but it is also true that

13 = (-17) \times 403 + 24 \times 286,

(check: $-6851 + 6864 = 13$ ). We will see how to produce all such solutions in Topic 4, but a preview is given below.

Example. Find integers $x$ and $y$ such that $\gcd(283,193) = 283x + 193y$ .
First, run the Euclidean algorithm on $283$ and $193$ :

\begin{align*} 283 &= 1 \times 193 + 90, && (1)\\ 193 &= 2 \times 90 + 13, && (2)\\ 90 &= 6 \times 13 + 12, && (3)\\ 13 &= 1 \times 12 + 1, && (4)\\ 12 &= 12 \times 1 + 0, \end{align*}

so $\gcd(283,193) = 1$ . Now back-substitute, starting from the penultimate line:

\begin{align*} 1 &= 13 - 1 \times 12 && \text{(from } (4))\\ &= 13 - 1 \times (90 - 6 \times 13) && \text{(substituting from } (3))\\ &= 7 \times 13 - 1 \times 90 && \text{(collecting terms)}\\ &= 7 \times (193 - 2 \times 90) - 1 \times 90 && \text{(substituting from } (2))\\ &= 7 \times 193 - 15 \times 90 && \text{(collecting terms)}\\ &= 7 \times 193 - 15 \times (283 - 1 \times 193) && \text{(substituting from } (1))\\ &= 22 \times 193 - 15 \times 283 && \text{(collecting terms)}. \end{align*}

Therefore, $\gcd(283,193) = 283 \times (-15) + 193 \times 22$ ; i.e. $x = -15$ and $y = 22$ . (Quick sanity check: $4246 - 4245 = 1$ .)

Example. Find integers $x$ and $y$ such that $\gcd(1001, 91) = 1001x + 91y$ .
This one is an edge case; running the Euclidean algorithm,

1001 = 11 \times 91 + 0,

the remainder is already $0$ on the very first line, since $91 \mid 1001$ . That's genuinely the entire run, so there is no penultimate line to back-substitute from. When $b \mid a$ , the gcd is just $b$ itself, and Bézout's identity is immediate:

\gcd(1001,91) = 91 = 1001 \times 0 + 91 \times 1.

Therefore, $(x,y) = (0,1)$ . Don't go hunting for substitutions that don't exist.

Bézout in Reverse#

It is important to remember that Bézout's identity cannot be used in reverse; being able to write $d = ax + by$ does not mean that $d = \gcd(a,b)$ . For instance, $52 = 403 \times (-2) + 286 \times 3$ , but $\gcd(403,286)$ is certainly not $52$ . However, the following weaker statement is true.

Note

Theorem
Given $d = ax + by$ for some integers $a,b,x,y$ , we have that

\gcd(a,b) \mid d.

Proof. Let $g = \gcd(a,b)$ . Then $g \mid a$ and $g \mid b$ , so by Lemma 1.3 from Divisibility and Primes, $g$ divides any integer linear combination of $a$ and $b$ ;

g \mid ax + by, \quad \text{i.e. } g \mid d. \quad \blacksquare

Basically, every integer linear combination of $a$ and $b$ is a multiple of $\gcd(a,b)$ ; the gcd is the smallest positive number you can build this way, and everything else you can build is a multiple of it. That is why $52$ showed up above: $52$ is a multiple of $13$ .

Combining Bézout's identity with this weaker converse gives us a very useful test for coprimality.

Note

Corollary
Integers $a$ and $b$ satisfy $\gcd(a,b)=1$ if and only if there exist integers $x$ and $y$ such that

ax + by = 1.

Proof. If $\gcd(a,b) = 1$ , then Bézout's identity directly provides such $x$ and $y$ . Conversely, if $ax+by=1$ then by the previous theorem $\gcd(a,b) \mid 1$ ; since the gcd is positive, $\gcd(a,b) = 1$ . $\blacksquare$

Recall that two integers with $\gcd(a,b)=1$ are called coprime (or relatively prime). The power of this corollary is the backwards direction: if you can exhibit any combination equal to $1$ , you get the gcd for free, with no Euclidean algorithm needed.

Example. Show that any two consecutive integers are coprime.
Let $n \in \mathbb{Z}$ and consider $n$ and $n+1$ . Notice that

\begin{align*} (n+1) \times 1 + n \times (-1) &= n + 1 - n \\ &= 1, \end{align*}

so we have written $1$ as an integer linear combination of $n+1$ and $n$ (with $x = 1$ and $y = -1$ ). Therefore, by the corollary, $\gcd(n, n+1) = 1$ for every integer $n$ ; consecutive integers are always coprime.

Using Bézout's Identity in Proofs#

Recall the following theorem from Lecture 1.1, which we stated without proof; we now have the machinery to prove it.

Note

Theorem (Euclid's Lemma)
Suppose that $a$ and $b$ are integers and $p$ is a prime integer. If $p \mid ab$ , then $p \mid a$ or $p \mid b$ .

Proof. Suppose that $p \mid ab$ . If $p \mid a$ , we are done; so suppose instead that $p \nmid a$ . Since $p$ is prime, its only divisors are $\pm 1$ and $\pm p$ , and because $p \nmid a$ , the only common divisors of $p$ and $a$ are $\pm 1$ ; hence $\gcd(p,a) = 1$ . By Bézout's identity, there exist integers $x$ and $y$ such that

px + ay = 1.

Multiplying both sides by $b$ (to force an $ab$ term to appear),

\begin{align*} pbx + aby &= b. \end{align*}

Now, $p \mid pbx$ trivially, and $p \mid aby$ since $p \mid ab$ by assumption; therefore $p$ divides their sum,

p \mid pbx + aby, \quad \text{i.e. } p \mid b. \quad \blacksquare

This "multiply the Bézout equation by whatever you need" trick is worth remembering; it appears constantly in number theory proofs.

The Extended Euclidean Algorithm#

Back-substitution works, but it is slow and easy to fumble when there are many lines; the extended Euclidean algorithm packages the exact same computation into a table.

Consider again the Euclidean algorithm for $403$ and $286$ . Notice that we only ever care about the quotient and the remainder in each line. Writing $q_i$ for the quotient and $r_i$ for the remainder found in line $i$ , and seeding the remainder row with the original numbers $403$ and $286$ , the whole algorithm compresses to:

$q_i$			$1$	$2$	$2$	$4$
$r_i$	$403$	$286$	$117$	$52$	$13$	$0$

Each remainder is obtained from the two before it via

r_i = r_{i-2} - q_i \times r_{i-1};

i.e. divide the remainder two spots to the left by the one directly to the left, record the quotient $q_i$ up top, and the remainder $r_i$ below it.

The extended Euclidean algorithm (EEA) performs exactly these steps, except it introduces two new rows for $x_i$ and $y_i$ , seeded with $(1,0)$ and $(0,1)$ respectively, which obey the same recursion as the remainders:

x_i = x_{i-2} - q_i x_{i-1}, \qquad y_i = y_{i-2} - q_i y_{i-1}.

In words: each new entry is the entry two spaces to its left, minus the $q_i$ above it times the entry directly to its left. Applying this to $403$ and $286$ , we start with the unfilled table

$q_i$
$r_i$	$403$	$286$
$x_i$	$1$	$0$
$y_i$	$0$	$1$

and filling it out column by column gives:

$q_i$			$1$	$2$	$2$	$4$
$r_i$	$403$	$286$	$117$	$52$	$13$	$0$
$x_i$	$1$	$0$	$1$	$-2$	$5$	$-22$
$y_i$	$0$	$1$	$-1$	$3$	$-7$	$31$

The magic of this table is that in every column,

\boxed{r_i = ax_i + by_i.}

You can check this on any column you like; e.g. the $r_i = 52$ column gives $403 \times (-2) + 286 \times 3 = -806 + 858 = 52$ . In particular, the second-last column (the one where $r_i = \gcd(a,b)$ ) tells us that $13 = 5 \times 403 - 7 \times 286$ , exactly matching the back-substitution answer from earlier.

Note

Algorithm (Extended Euclidean Algorithm)
Given integers $a$ and $b$ , to find integers $x$ and $y$ such that $\gcd(a,b) = ax+by$ :

Start with the unfilled table: seed the $r_i$ row with $a$ and $b$ , the $x_i$ row with $1, 0$ and the $y_i$ row with $0, 1$ .
Fill the top two rows by applying the Euclidean algorithm to $a$ and $b$ as usual, recording each quotient $q_i$ and remainder $r_i$ (with practice this can be done directly in the table).
Fill the bottom two rows using the recursive formulae $x_i = x_{i-2} - q_i x_{i-1}$ and $y_i = y_{i-2} - q_i y_{i-1}$ .
In every column, $r_i = ax_i + by_i$ ; so the required $x$ and $y$ are the $x_i$ and $y_i$ entries in the second-last column, where $r_i = \gcd(a,b)$ .

A good habit is to always verify the second-last column by actually computing $ax_i + by_i$ before writing down your final answer; it is a two-second check that catches almost every arithmetic slip in the table.

Example. Find integers $x$ and $y$ such that $\gcd(283,193) = 283x + 193y$ , using the EEA.
We already know the quotients from the earlier run ( $1, 2, 6, 1, 12$ ), so we fill out the table:

$q_i$			$1$	$2$	$6$	$1$	$12$
$r_i$	$283$	$193$	$90$	$13$	$12$	$1$	$0$
$x_i$	$1$	$0$	$1$	$-2$	$13$	$-15$	$193$
$y_i$	$0$	$1$	$-1$	$3$	$-19$	$22$	$-283$

For instance, the $x_i$ entry under $q_i = 6$ is $1 - 6\times(-2) = 13$ , and the $y_i$ entry below it is $-1 - 6 \times 3 = -19$ . Reading off the second-last column (where $r_i = 1 = \gcd(283,193)$ ):

\begin{align*} 1 &= 283 \times (-15) + 193 \times 22 \\ &= -4245 + 4246 \\ &= 1. \ \checkmark \end{align*}

Therefore, $x = -15$ and $y = 22$ , agreeing with the back-substitution method.

Notice how both methods are computing the same thing; for two or three division steps, back-substitution is perfectly fine, but once the Euclidean algorithm takes four or more lines (like this one), the table is faster and far less error-prone, since you never have to expand brackets.

Solving ax + by = c in General#

Bézout's identity only directly produces combinations equal to the gcd; a natural exam-style question is whether $ax + by = c$ can be solved for other values of $c$ .

Note

Theorem
Given integers $a, b, c$ , the equation $ax + by = c$ has integer solutions $x, y$ if and only if

\gcd(a,b) \mid c.

Proof. If a solution exists, then $c$ is an integer linear combination of $a$ and $b$ , so $\gcd(a,b) \mid c$ by the weaker theorem above. Conversely, if $c = k \gcd(a,b)$ for some $k \in \mathbb{Z}$ , take a Bézout pair $(x_0, y_0)$ with $ax_0 + by_0 = \gcd(a,b)$ and multiply through by $k$ ; then $x = kx_0$ , $y = ky_0$ is a solution. $\blacksquare$

Basically, the reachable values of $ax+by$ are precisely the multiples of the gcd; nothing more, nothing less. So the decision process for these questions is: compute the gcd first, then check divisibility.

Example. Find integers $x$ and $y$ such that $12x + 20y = 3$ , or explain why none exist.
Running the Euclidean algorithm on $20$ and $12$ :

\begin{align*} 20 &= 1 \times 12 + 8, \\ 12 &= 1 \times 8 + 4, \\ 8 &= 2 \times 4 + 0, \end{align*}

so $\gcd(12,20) = 4$ . Since $4 \nmid 3$ , no integer solutions exist; every integer linear combination of $12$ and $20$ is a multiple of $4$ , and $3$ is not. Do not waste time back-substituting when the divisibility check already fails.

Example. Find integers $x$ and $y$ such that $12x + 20y = 8$ .
This time $\gcd(12,20) = 4$ and $4 \mid 8$ , so solutions exist. First find a Bézout pair for the gcd by back-substituting the run above:

\begin{align*} 4 &= 12 - 1 \times 8 && \text{(from the second line)}\\ &= 12 - 1 \times (20 - 1 \times 12) && \text{(substituting from the first line)}\\ &= 2 \times 12 - 1 \times 20 && \text{(collecting terms)}. \end{align*}

Since $8 = 2 \times 4$ , multiply the whole identity through by $2$ :

\begin{align*} 8 &= 4 \times 12 - 2 \times 20 \\ &= 48 - 40 \\ &= 8. \ \checkmark \end{align*}

Therefore, $(x,y) = (4,-2)$ is a solution. The general strategy: solve for the gcd first, then scale.

Generating More Solutions#

We noted earlier that Bézout pairs are not unique; here is how to manufacture new solutions from an old one.

Example. Given that $\gcd(403,286) = 13 = 5 \times 403 - 7 \times 286$ , find a second pair $(x,y)$ with $403x + 286y = 13$ .
The trick is that we can shift $x$ by $-\frac{b}{d}$ and $y$ by $\frac{a}{d}$ (where $d = \gcd(a,b)$ ) without changing the value, because the two changes cancel exactly:

\begin{align*} a\left(x - \tfrac{b}{d}\right) + b\left(y + \tfrac{a}{d}\right) &= ax + by - \tfrac{ab}{d} + \tfrac{ab}{d} \\ &= ax + by. \end{align*}

Here $\frac{b}{d} = \frac{286}{13} = 22$ and $\frac{a}{d} = \frac{403}{13} = 31$ , so from $(5,-7)$ we get

\begin{align*} (x, y) &= (5 - 22, -7 + 31) \\ &= (-17, 24), \end{align*}

and indeed $403 \times (-17) + 286 \times 24 = -6851 + 6864 = 13$ . $\checkmark$

Therefore, $(-17, 24)$ is a second solution, and repeating the shift in either direction generates infinitely many. Notice how the last column of the EEA table for $403$ and $286$ was $(x_i, y_i) = (-22, 31)$ ; that "useless" column under $r_i = 0$ is exactly the shift $\left(\pm\frac{b}{d}, \mp\frac{a}{d}\right)$ , so the table hands you the recipe for new solutions for free.

A Preview of Modular Inverses#

Here is a look ahead at why the coprime criterion matters so much; this idea will carry most of the modular arithmetic later in the course.

An inverse of $a$ modulo $n$ is an integer $x$ such that $ax$ leaves remainder $1$ when divided by $n$ ; i.e. $ax - 1 = nk$ for some $k \in \mathbb{Z}$ . Rearranging,

ax + n(-k) = 1,

which is precisely a statement that $1$ is an integer linear combination of $a$ and $n$ . By the coprime criterion, such $x$ and $k$ exist if and only if $\gcd(a,n) = 1$ ; and when the inverse exists, the extended Euclidean algorithm is exactly the tool that finds it.

Example. Find an integer $x$ such that $7x$ leaves remainder $1$ when divided by $30$ .
First check existence: run the Euclidean algorithm on $30$ and $7$ ,

\begin{align*} 30 &= 4 \times 7 + 2, && (1)\\ 7 &= 3 \times 2 + 1, && (2)\\ 2 &= 2 \times 1 + 0, \end{align*}

so $\gcd(30,7) = 1$ and an inverse exists. Now back-substitute:

\begin{align*} 1 &= 7 - 3 \times 2 && \text{(from } (2))\\ &= 7 - 3 \times (30 - 4 \times 7) && \text{(substituting from } (1))\\ &= 13 \times 7 - 3 \times 30 && \text{(collecting terms)}. \end{align*}

So $7 \times 13 = 1 + 3 \times 30$ ; i.e. $7 \times 13 = 91$ leaves remainder $1$ when divided by $30$ . Therefore, the inverse of $7$ modulo $30$ is $x = 13$ .

By contrast, $6$ has no inverse modulo $30$ : $\gcd(6,30) = 6 \neq 1$ , so $6x + 30(-k) = 1$ would force $6 \mid 1$ , which is impossible. This is the standard exam trap; always check the gcd before hunting for an inverse.