Bezout's identity and the extended Euclidean algorithm

When you reach for it

The The Euclidean algorithm and coprime numbers finds \gcd(527, 403) = 31 in three divisions. Every common divisor of 527 and 403 divides every combination 527x + 403y with x, y \in \mathbb{Z} (Proving statements about divisibility), so every such combination is a multiple of 31. A sharper question is whether 31 itself is one of them. It is: 31 = 4 \cdot 403 - 3 \cdot 527 (Example 1), and the multipliers come from the same divisions, read backward.

Reach for this move when a proof needs the greatest common divisor written as a combination: to show two integers are coprime by producing 1, to prove Euclid’s lemma (a prime dividing a product divides a factor), and to solve an equation ax + by = c in integers, such as finding how many \$7 and \$11 items cost exactly \$100. The lesson runs over two days. Day 1 finds the combination and proves it always exists (Bezout’s identity). Day 2 uses it: Euclid’s lemma and equations ax + by = c.

The procedure

Day 1: running the divisions backward

An integer combination (or linear combination) of a and b is a number ax + by with x, y \in \mathbb{Z}; the integers x, y are its coefficients. Run the Euclidean algorithm on a and b > 0:

and then r_{n-1} = r_n q_{n+1}, with r_n = \gcd(a, b). Back substitution solves each line for its remainder, r_k = r_{k-2} - q_k r_{k-1} (with r_{-1} = a, r_0 = b), and works upward. The last line writes r_n as a combination of r_{n-2} and r_{n-1}. Replace r_{n-1} by its own expression in r_{n-3} and r_{n-2}, collect terms, and the result is a combination of r_{n-3} and r_{n-2}. Each substitution moves one line up, and at the top only a and b are left. Every step is the distributive property and collecting like terms, so the final equation is true because each one before it was.

Day 1: the table form

Back substitution needs every division written down first, then a second pass. The table form carries the coefficients forward in one pass. Keep a row (r, x, y) with the promise r = ax + by. The first two rows keep it trivially:

Each new remainder is r_k = r_{k-2} - q_k r_{k-1}, so form each new row as (the row two up) minus q_k times (the row just above), entry by entry. If r_{k-2} = ax' + by' and r_{k-1} = ax'' + by'', subtracting q_k times the second equation from the first gives

so the new row keeps the promise too. The row whose r is the last nonzero remainder holds the coefficients of \gcd(a, b).

Day 1: Bezout’s identity

Both methods stop after finitely many steps and always end at a combination, so the algorithm already proves that one exists. A second proof, by the well-ordering principle of Strong induction and well-ordering (every nonempty set of positive integers has a least member), shows more: the gcd is the least positive combination.

Bezout’s identity. Let a, b \in \mathbb{Z}, not both zero. Then \gcd(a, b) is the least positive integer of the form ax + by with x, y \in \mathbb{Z}.

Proof. Let S be the set of positive integers of the form ax + by. It is not empty, because a \cdot a + b \cdot b = a^2 + b^2 > 0. By the well-ordering principle S has a least member d = ax_0 + by_0.

First, d \mid a. By The division algorithm, a = dq + r with 0 \le r < d. Then

an integer combination of a and b. If r > 0, then r \in S and r < d, contradicting the choice of d. So r = 0 and d \mid a. The same argument with b in place of a gives d \mid b. So d is a positive common divisor, and d \le \gcd(a, b).

Second, g = \gcd(a, b) divides a and b, so it divides the combination ax_0 + by_0 = d. Since d > 0, the size bound of Divisibility as a relation gives g \le d. Hence d = g. \square

Two consequences are used constantly.

Combinations are the multiples of the gcd. The integers of the form ax + by are exactly the multiples of g = \gcd(a, b). Every combination is a multiple, since g \mid a and g \mid b. Conversely, if g = ax_0 + by_0, then kg = a(kx_0) + b(ky_0) for every integer k.

Coprime means 1 is a combination. \gcd(a, b) = 1 exactly when ax + by = 1 for some integers x, y. If the gcd is 1, Bezout’s identity writes it so. If 1 = ax + by, then 1 is a multiple of the gcd, so the gcd is 1.

The same argument gives a fact proved by other means in the Euclidean algorithm lesson: if c \mid a and c \mid b, then c divides ax_0 + by_0 = \gcd(a, b).

Day 2: Euclid’s lemma

Lemma (coprime factor). If a \mid bc and \gcd(a, b) = 1, then a \mid c.

Proof. Since \gcd(a, b) = 1, there are integers x, y with ax + by = 1. Multiply by c:

Now a \mid a(cx), and a \mid bc by hypothesis, so a \mid (bc)y. A divisor of two integers divides their sum, so a \mid c. \square

Euclid’s lemma. If p is prime and p \mid ab, then p \mid a or p \mid b.

Proof. If p \mid a we are done. Otherwise \gcd(p, a) is a positive divisor of p, so it is 1 or p; it is not p, since p \nmid a. So \gcd(p, a) = 1, and the coprime factor lemma with p \mid ab gives p \mid b. \square

This closes two gaps left open earlier. Proving statements about divisibility stated Euclid’s lemma without proof; the proof above supplies it. Every number has exactly one prime factorization assumed it as the prime divisor property; Exercise 19 extends it to any number of factors, which is exactly that property, so the uniqueness of prime factorization now rests on proved ground.

Day 2: linear equations in integers

An equation ax + by = c to be solved with x, y \in \mathbb{Z} is a linear Diophantine equation.

Theorem. Let a, b be nonzero integers and d = \gcd(a, b). The equation ax + by = c has an integer solution exactly when d \mid c. If (x_0, y_0) is one solution, the solutions are exactly

Proof. The first sentence is “combinations are the multiples of the gcd”. Each pair in the list is a solution, since \displaystyle a \cdot \frac{b}{d}t - b \cdot \frac{a}{d}t = 0. Conversely, let (x, y) be any solution. Subtracting ax_0 + by_0 = c from ax + by = c gives a(x - x_0) = b(y_0 - y), and dividing by d,

By Example 4, \displaystyle \gcd(\frac{a}{d}, \frac{b}{d}) = 1. So \displaystyle \frac{b}{d} divides \displaystyle \frac{a}{d}(x - x_0) and is coprime to \displaystyle \frac{a}{d}, and the coprime factor lemma gives \displaystyle x - x_0 = \frac{b}{d}t for some integer t. Substituting, \displaystyle \frac{a}{d} \cdot \frac{b}{d}t = \frac{b}{d}(y_0 - y), and cancelling \displaystyle \frac{b}{d} \ne 0 gives \displaystyle y = y_0 - \frac{a}{d}t. \square

To find (x_0, y_0): write d = ax' + by' by the algorithm and multiply by \displaystyle \frac{c}{d}.

Worked examples

Examples 1 to 4 belong to Day 1, Examples 5 to 7 to Day 2.

Boundaries

• Not both zero. \gcd(0, 0) is undefined, so Bezout’s identity needs a, b not both zero. The theorem on ax + by = c is stated for a, b both nonzero; if, say, a = 0, the equation is by = c in one unknown, with x free.
• The coefficients are not unique. One combination gives infinitely many: \displaystyle x + \frac{b}{d}t, \displaystyle y - \frac{a}{d}t. The algorithm returns one particular pair.
• Integers, not counts. Bezout’s identity promises integer coefficients, usually one negative. Whether ax + by = c has a solution with x, y \ge 0 is a different question: 7x + 11y = 59 has integer solutions but none with both nonnegative, as trying y = 0, 1, \dots, 5 shows.
• Euclid’s lemma needs a prime. 10 \mid 4 \cdot 15, yet 10 \nmid 4 and 10 \nmid 15. The coprime factor lemma needs \gcd(a, b) = 1: 4 \mid 2 \cdot 6 but 4 \nmid 6.
• Least positive, not least. The combinations include 0 and negative numbers. The gcd is the least positive one.

Where this goes next

The equation ax + ny = 1 is the heart of modular inverses: an integer a has an inverse modulo n exactly when \gcd(a, n) = 1, and the table form computes it. The same combinations of coprime moduli build the solutions in the The Chinese remainder theorem. Euclid’s lemma is what makes prime factorization unique (Every number has exactly one prime factorization, fundamental-theorem-of-arithmetic), and it is the step behind irrationality proofs such as “p \mid n^2 forces p \mid n” (Exercise 17).

Exercises

Day 1: finding combinations

1. Use back substitution to write \gcd(589, 437) as an integer combination of 589 and 437.
2. Use the table form to find \gcd(1147, 899) and integers x, y with 1147x + 899y = \gcd(1147, 899).
3. Write 1 as an integer combination of 43 and 30.
4. Find \gcd(-168, 120) and integers x, y with -168x + 120y = \gcd(-168, 120).
5. Which of 18, 20 and 105 can be written as 35x + 50y with x, y \in \mathbb{Z}? Write each one that can.
6. Find the least positive value of 126x + 90y over all integers x, y, and a pair that gives it.

Day 1: reasoning

7. Prove that 11n + 6 and 2n + 1 are coprime for every integer n by writing 1 as a combination of them.
8. Prove that \gcd(ka, kb) = k \gcd(a, b) for every positive integer k and integers a, b not both zero.
9. Prove that if d > 0 is a common divisor of a and b and d = ax + by for some integers x, y, then d = \gcd(a, b).
10. Prove that if \gcd(a, b) = 1 and \gcd(a, c) = 1, then \gcd(a, bc) = 1.
11. Find integers x, y, z with 10x + 14y + 35z = 1. Explain why no combination of just two of 10, 14, 35 equals 1.

Day 2: equations in integers

12. Using Exercise 1, find every integer solution of 589x + 437y = 19, and the solution with x negative and as close to 0 as possible.
13. Find every integer solution of 12x + 21y = 75.
14. Show that 14x + 35y = 50 has no integer solution.
15. A club spends exactly \$200 on caps at \$9 and scarves at \$13. Find every way to do it.
16. Find every integer n with 35 \mid 14n.

Day 2: reasoning and proof

17. Let p be prime. Prove that if p \mid n^2, then p \mid n, and then that p^2 \mid n^2.
18. Find positive integers a, b with 12 \mid ab, 12 \nmid a and 12 \nmid b. Which hypothesis of Euclid’s lemma fails?
19. Prove by induction on n \ge 1: if a prime p divides a_1 a_2 \cdots a_n, then p divides some a_i.
20. Let a, b be coprime positive integers and c any integer. Prove that ax + by = c has a solution with 0 \le x < b.
21. Show that 31 is not 5x + 9y with x, y \ge 0 integers, that each of 32, 33, 34, 35, 36 is, and conclude that every integer c \ge 32 is.
22. Prove that if \gcd(a, b) = 1, then \gcd(a + b, ab) = 1.