Bezouts Identity and the Extended Euclidean Algorithm

The Euclidean Algorithm in Reverse

Recall that the Euclidean algorithm finds $g cd (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$ :

40328611752 = 1 \times 286 + 117, = 2 \times 117 + 52, = 2 \times 52 + 13, = 4 \times 13 + 0, (1) (2) (3)

so $g cd (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$ :

13 = 117 - 2 \times 52 = 117 - 2 \times (286 - 2 \times 117) = 5 \times 117 - 2 \times 286 = 5 \times (403 - 286) - 2 \times 286 = 5 \times 403 - 7 \times 286 (from (3)) (substituting from (2)) (collecting terms) (substituting from (1)) (collecting terms) .

Therefore, we have written $g cd (403, 286)$ in the form $403 x + 286 y$ , specifically with $x = 5$ and $y = - 7$ . An expression of the form $a x + b y$ , where $x, y \in 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

g cd (a, b) = a x + b y .

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 $g cd (283, 193) = 283 x + 193 y$ .
First, run the Euclidean algorithm on $283$ and $193$ :

283193901312 = 1 \times 193 + 90, = 2 \times 90 + 13, = 6 \times 13 + 12, = 1 \times 12 + 1, = 12 \times 1 + 0, (1) (2) (3) (4)

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

1 = 13 - 1 \times 12 = 13 - 1 \times (90 - 6 \times 13) = 7 \times 13 - 1 \times 90 = 7 \times (193 - 2 \times 90) - 1 \times 90 = 7 \times 193 - 15 \times 90 = 7 \times 193 - 15 \times (283 - 1 \times 193) = 22 \times 193 - 15 \times 283 (from (4)) (substituting from (3)) (collecting terms) (substituting from (2)) (collecting terms) (substituting from (1)) (collecting terms) .

Therefore, $g cd (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 $g cd (1001, 91) = 1001 x + 91 y$ .
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 ∣ 1001$ . That's genuinely the entire run, so there is no penultimate line to back-substitute from. When $b ∣ a$ , the gcd is just $b$ itself, and Bézout's identity is immediate:

g cd (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 = a x + b y$ does not mean that $d = g cd (a, b)$ . For instance, $52 = 403 \times (- 2) + 286 \times 3$ , but $g cd (403, 286)$ is certainly not $52$ . However, the following weaker statement is true.

Note

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

g cd (a, b) ∣ d .

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

g ∣ a x + b y, i.e. g ∣ d . ■

Basically, every integer linear combination of $a$ and $b$ is a multiple of $g cd (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 $g cd (a, b) = 1$ if and only if there exist integers $x$ and $y$ such that

a x + b y = 1.

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

Recall that two integers with $g cd (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 Z$ and consider $n$ and $n + 1$ . Notice that

(n + 1) \times 1 + n \times (- 1) = n + 1 - n = 1,

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, $g cd (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 ∣ ab$ , then $p ∣ a$ or $p ∣ b$ .

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

p x + a y = 1.

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

p b x + ab y = b .

Now, $p ∣ p b x$ trivially, and $p ∣ ab y$ since $p ∣ ab$ by assumption; therefore $p$ divides their sum,

p ∣ p b x + ab y, i.e. p ∣ b . ■

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}, 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,

r_{i} = a x_{i} + b y_{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} = g cd (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 $g cd (a, b) = a x + b y$ :

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} = a x_{i} + b y_{i}$ ; so the required $x$ and $y$ are the $x_{i}$ and $y_{i}$ entries in the second-last column, where $r_{i} = g cd (a, b)$ .

A good habit is to always verify the second-last column by actually computing $a x_{i} + b y_{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 $g cd (283, 193) = 283 x + 193 y$ , 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 = g cd (283, 193)$ ):

1 = 283 \times (- 15) + 193 \times 22 = - 4245 + 4246 = 1. ✓

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 $a x + b y = c$ can be solved for other values of $c$ .

Note

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

g cd (a, b) ∣ c .

Proof. If a solution exists, then $c$ is an integer linear combination of $a$ and $b$ , so $g cd (a, b) ∣ c$ by the weaker theorem above. Conversely, if $c = k g cd (a, b)$ for some $k \in Z$ , take a Bézout pair $(x_{0}, y_{0})$ with $a x_{0} + b y_{0} = g cd (a, b)$ and multiply through by $k$ ; then $x = k x_{0}$ , $y = k y_{0}$ is a solution. $■$

Basically, the reachable values of $a x + b y$ 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 $12 x + 20 y = 3$ , or explain why none exist.
Running the Euclidean algorithm on $20$ and $12$ :

20128 = 1 \times 12 + 8, = 1 \times 8 + 4, = 2 \times 4 + 0,

so $g cd (12, 20) = 4$ . Since $4 ∤ 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 $12 x + 20 y = 8$ .
This time $g cd (12, 20) = 4$ and $4 ∣ 8$ , so solutions exist. First find a Bézout pair for the gcd by back-substituting the run above:

4 = 12 - 1 \times 8 = 12 - 1 \times (20 - 1 \times 12) = 2 \times 12 - 1 \times 20 (from the second line) (substituting from the first line) (collecting terms) .

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

8 = 4 \times 12 - 2 \times 20 = 48 - 40 = 8. ✓

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

a (x - \frac{b}{d}) + b (y + \frac{a}{d}) = a x + b y - \frac{ab}{d} + \frac{ab}{d} = a x + b y .

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

(x, y) = (5 - 22, - 7 + 31) = (- 17, 24),

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

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 $(\pm \frac{b}{d}, \mp \frac{a}{d})$ , 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 $a x$ leaves remainder $1$ when divided by $n$ ; i.e. $a x - 1 = nk$ for some $k \in Z$ . Rearranging,

a x + 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 $g cd (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 $7 x$ leaves remainder $1$ when divided by $30$ .
First check existence: run the Euclidean algorithm on $30$ and $7$ ,

3072 = 4 \times 7 + 2, = 3 \times 2 + 1, = 2 \times 1 + 0, (1) (2)

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

1 = 7 - 3 \times 2 = 7 - 3 \times (30 - 4 \times 7) = 13 \times 7 - 3 \times 30 (from (2)) (substituting from (1)) (collecting terms) .

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$ : $g cd (6, 30) = 6 \neq = 1$ , so $6 x + 30 (- k) = 1$ would force $6 ∣ 1$ , which is impossible. This is the standard exam trap; always check the gcd before hunting for an inverse.