Back to the on-screen lesson · Print

Bézout's identity

Euclid's run read backwards: the gcd as an integer combination, and why that second description is the one later proofs use.

Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.

1. What you will learn

By the end of this lesson you will be able to run the extended Euclidean algorithm and produce a pair of Bézout coefficients for any two integers, state Bézout's identity and prove it by the least-positive-combination argument, say why the set of integer combinations of two numbers is exactly the multiples of their gcd, and use the identity to prove a divisibility claim without computing the coefficients.

2. The run you have already done, read upwards

Euclid's algorithm produced a column of divisions, each of the form $r_{i-2} = q_i r_{i-1} + r_i$. Lesson 2 read them downwards, and the last non-zero remainder was the answer.

Rearrange one line and it says something else: $r_i = r_{i-2} - q_i r_{i-1}$. Every remainder is a combination of the two numbers above it. Apply that repeatedly, from the bottom of the column to the top, and the gcd turns into a combination of the two numbers you started with. The run was carrying this information all along; the forward pass simply threw it away.

3. Integer combination, Bézout coefficients, extended algorithm

An integer combination of $a$ and $b$ is a number of the form $ax + by$ with $x$ and $y$ integers — positive, negative or zero. It is not a positive combination and not a rational one; the freedom to subtract is the whole point.

The integers $x, y$ in $ax + by = \gcd(a, b)$ are Bézout coefficients. They are not unique: $(x + b/d, \; y - a/d)$ works too, for $d = \gcd(a, b)$, and so does every shift by that amount.

The extended Euclidean algorithm is the run together with the bookkeeping that produces a pair of coefficients — either by substituting upwards afterwards, or by carrying two extra columns down as you go.

4. The gcd, described a second way

Bézout's identity. For integers $a, b$ not both zero there exist integers $x, y$ with $$ax + by = \gcd(a, b).$$

The proof is the algorithm: the last non-zero remainder is the gcd, and every remainder is an integer combination of the two numbers before it, so by induction down the run the gcd is an integer combination of $a$ and $b$.

There is a second proof worth knowing, because it does not mention the algorithm at all. Let $S$ be the set of positive integer combinations of $a$ and $b$; it is non-empty, so it has a least element $d = ax_0 + by_0$. Divide $a$ by $d$: the remainder $a - dq$ is again a combination and is smaller than $d$, so it is $0$, so $d \mid a$; likewise $d \mid b$. And any common divisor of $a$ and $b$ divides $d$. So $d$ is the gcd.

That argument establishes more than the identity. It shows:

• the set of integer combinations of $a$ and $b$ is exactly the set of multiples of $\gcd(a, b)$;
• every common divisor of $a$ and $b$ divides the gcd, rather than merely being no larger than it;
• $\gcd(a, b) = 1$ if and only if $ax + by = 1$ is solvable — which is the form used in every later proof in this course.

The second bullet is the one people underuse. Greatest in "greatest common divisor" turns out to mean greatest in the divisibility order, not merely in size, and that is a stronger statement.

5. What the identity is for

Bézout's identity is almost never wanted for its numbers. It is wanted for its existence, and the pattern of use is always the same: because the gcd is 1, there are integers $x$ and $y$ with $ax + by = 1$; multiply that by something and see what divides what.

Three things in this course are that argument and nothing else.

Euclid's lemma. If a prime $p$ divides $ab$ but not $a$, then $\gcd(p, a) = 1$, so $px + ay = 1$; multiply by $b$ to get $pbx + aby = b$, and $p$ divides both terms, so $p \mid b$. Unique factorisation rests on this, and this rests on Bézout.

Inverses modulo $n$. $a$ has an inverse modulo $n$ exactly when $ax + ny = 1$ is solvable, which is exactly when $\gcd(a, n) = 1$. The extended algorithm is not one way of computing an inverse; it is the way, and RSA key generation calls it directly.

Linear Diophantine equations. $ax + by = c$ is solvable exactly when $\gcd(a, b) \mid c$, because the combinations are precisely the multiples of the gcd. Scaling a Bézout identity by $c/d$ produces a solution.

The coefficients are also what makes the algorithm fast enough to be useful: computing an inverse modulo a thousand-digit number is a few thousand divisions, and there is no other elementary method.

6. What the identity does not say

The coefficients are not unique. There are infinitely many pairs. Two people can both be right and disagree, and an answer should be checked by multiplying out rather than by comparing with someone else's.

They are not both positive. Unless one number divides the other, one coefficient is negative — necessarily so, since a positive combination of two positive numbers is at least as large as each of them.

$ax + by = c$ is not solvable for every $c$. It is solvable exactly for the multiples of the gcd. The identity gives the gcd; everything else comes from scaling, and $c$ that is not a multiple is out of reach.

Coprime does not mean prime. $\gcd(a, b) = 1$ says the two share no factor; neither one need be prime, and $8$ and $9$ are the standing example.

Bézout does not factorise. It never learns a prime factor of either number. That is why it survives at sizes where factorisation does not, and why a proof that uses it stays constructive.

7. An inverse, which is a Bézout identity in disguise

1. Find $17^{-1}$ modulo $40$. Run Euclid: $40 = 2 \cdot 17 + 6$, $17 = 2 \cdot 6 + 5$, $6 = 1 \cdot 5 + 1$.

   The remainder reached $1$, so the two are coprime and an inverse exists.

2. Back-substitute: $1 = 6 - 5 = 6 - (17 - 2 \cdot 6) = 3 \cdot 6 - 17 = 3(40 - 2 \cdot 17) - 17 = 3 \cdot 40 - 7 \cdot 17$.

   One line per division, in reverse.

3. So $-7 \cdot 17 \equiv 1 \pmod{40}$, and the inverse is $-7 \equiv 33$. Check: $17 \cdot 33 = 561 = 14 \cdot 40 + 1$.

   The coefficient of the modulus is discarded; only the other one matters.

8. A claim proved by existence alone

1. Claim: if $\gcd(a, b) = 1$, then $\gcd(a, bc) = \gcd(a, c)$ for every $c$. Start with $ax + by = 1$.

   The coefficients are never computed.

2. Multiply by $c$: $acx + bcy = c$. Any common divisor of $a$ and $bc$ divides both terms, hence divides $c$ — so it is a common divisor of $a$ and $c$.

   One direction.

3. The other direction is free, since a common divisor of $a$ and $c$ divides $bc$. So the two sets of common divisors agree, and so do their greatest elements.

   Equality of sets, not just of maxima.

9. Your turn: show that if $\gcd(a, b) = 1$, then $\gcd(a + b, ab) = 1$

1. Let $d$ be a common divisor of $a + b$ and $ab$, and let $p$ be a prime dividing $d$. Then $p \mid ab$.

   Work with a prime factor rather than $d$ itself.

2. By Euclid's lemma $p \mid a$ or $p \mid b$; say $p \mid a$. Since $p \mid (a + b)$ too, $p \mid b$.

   Subtract to move the divisibility across.

3. Your turn: work this step out. Its working is at the end of the packet.

   That contradicts $\gcd(a, b) = 1$, so $d$ has no prime factor and $d = 1$.

10. Guided practice

Run the extended Euclidean algorithm on $35$ and $30$. Give the greatest common divisor and the two coefficients of the identity it produces.

11. Guided practice

A Bézout identity for $35$ and $30$ reads $35x + 30y = 5$ with $y = -1$. What is $x$?

Answer:

12. Practice

Check the identity $62 \times (5) + 44 \times (-7) = 2$ by computing the two products.

first product _a, second product _c

13. Practice

Let $x$ and $y$ range over all integers, positive and negative. What is the smallest positive value that $28x + 38y$ takes?

Answer:

14. Practice

Match each greatest common divisor to its value.

15. Somewhere new

Build the proof that if $\gcd(12, b) = 1$ and $12 \mid bc$, then $12 \mid c$.

This task has no paper form; do it on a device.

16. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

17. Test question

Run the extended Euclidean algorithm on $32$ and $30$. Give the greatest common divisor and the two coefficients of the identity it produces.

18. What you can do now

You can write a greatest common divisor as an integer combination of the two numbers and check it, and you can use the existence of such a combination to settle a divisibility question. Say in your own words why every common divisor of two numbers divides their gcd rather than merely being smaller. Next: what the identity says about primes.

Working for the steps left to you

9. Your turn: show that if $\gcd(a, b) = 1$, then $\gcd(a + b, ab) = 1$, step 3