Bézout's identity: Exercises — Maths deep dive

Before we start, one reminder in plain words. Bézout's identity says: take two whole numbers $a$ and $b$ (not both zero). Their greatest common divisor — the biggest number that divides both — can be written as a recipe $a x + b y$ , where $x$ and $y$ are whole numbers that are allowed to be negative. Negative just means "subtract that many copies". That's the whole game.

The two pictures you will use everywhere

Two visual ideas power every exercise below. Meet them now so the solutions feel like reading a map, not decoding algebra.

Picture A — why back-substitution builds Bézout coefficients. Look at the figure below. The Euclidean Algorithm works by repeated division: divide the bigger number by the smaller, and keep the remainder. One such division reads $(bigger number) = q \cdot (smaller number) + r,$ where $q$ (the quotient) is how many whole copies of the smaller number fit inside the bigger one, and $r$ (the remainder) is what's left over — always smaller than the number you divided by. We label the successive remainders $r_{1}, r_{2}, r_{3}, \dots$ : $r_{1}$ is the leftover from the first division, $r_{2}$ from the second, and so on. Each new remainder is strictly smaller than the previous one, so the trail marches downward and must stop — the last non-zero remainder is the gcd.

Now rearrange any one line to isolate its remainder: $r = (bigger number) - q \cdot (smaller number) .$ This says "this remainder is a combination of the two numbers just above it on the ladder." Back-substitution walks up the trail. At every rung, the gcd is already written as a combination of two numbers on that rung; we swap the lower one for its own combination-recipe from the rung above. Because each recipe only ever uses numbers from higher up, we keep climbing until the only numbers left are the original $a$ and $b$ . That is exactly why the process must terminate in $a x + b y = g cd$ — the ladder has a top.

In the figure, worked for $a = 17, b = 5$ : the teal down-arrow is the Euclidean phase producing the shrinking remainders $r_{1} = 2$ then $r_{2} = 1$ (the gcd); the orange up-arrow is back-substitution. Follow the plum line at the bottom — it shows the single swap $1 = 5 - 2 \cdot 2$ (using the gcd-line) turning into $1 = 7 \cdot 5 - 2 \cdot 17$ once the remainder $2$ is replaced by its recipe $2 = 17 - 5 \cdot 3$ . Watch where the " $2$ " disappears and " $17, 5$ " appear — that is the whole method in one move.

Picture B — why the general solution steps by $b / d$ and $- a / d$ . The solutions of $a x + b y = c$ are the integer points sitting on a single straight line. Slope of that line: $a x + b y = c \Rightarrow y = \frac{c}{b} - \frac{a}{b} x$ , so moving right by $Δ x$ drops you by $\frac{a}{b} Δ x$ . To stay on the line and land on integers again, you need the smallest whole step: move $Δ x = \frac{b}{d}$ across, and you fall $Δ y = - \frac{a}{d}$ down — because $a \cdot \frac{b}{d} + b \cdot (- \frac{a}{d}) = 0$ , the recipe's value doesn't change, yet both coordinates stay integers. That single equal-and-opposite cancellation is the whole reason the step is $(b / d, - a / d)$ . We draw this line explicitly in Exercise 5.2 below.

Level 1 — Recognition

Here you only need to decide things, not compute long chains.

Exercise 1.1

For each pair, state $g cd (a, b)$ , and say whether $a x + b y = 1$ can have integer solutions. (a) $a = 14, b = 9$ (b) $a = 14, b = 21$ (c) $a = 1, b = 1000$

Recall Solution 1.1

The key fact: $a x + b y = 1$ has integer solutions exactly when $g cd (a, b) = 1$ (the numbers are coprime). Why? Because the smallest positive number you can build from $a$ and $b$ is $g cd (a, b)$ — you can never make anything positive smaller than it. So you can only reach $1$ if the gcd already is $1$ .

(a) $g cd (14, 9)$ : $14 = 9 \cdot 1 + 5$ , $9 = 5 \cdot 1 + 4$ , $5 = 4 \cdot 1 + 1$ , $4 = 1 \cdot 4 + 0 \Rightarrow g cd = 1$ . Yes, $14 x + 9 y = 1$ is solvable. (b) $g cd (14, 21) = 7$ (since $21 = 14 \cdot 1 + 7$ , $14 = 7 \cdot 2 + 0$ ). No, cannot equal $1$ — the smallest positive value is $7$ . (c) $g cd (1, 1000) = 1$ . Yes (trivially $1 \cdot 1 + 1000 \cdot 0 = 1$ ).

Exercise 1.2

Which of these are valid Bézout equations (i.e. right-hand side truly equals the gcd)? (a) $12 x + 8 y = 4$ (b) $12 x + 8 y = 2$ (c) $6 x + 10 y = 2$

Recall Solution 1.2

The right-hand side of a Bézout equation must be exactly $g cd (a, b)$ . (a) $g cd (12, 8) = 4$ . RHS $= 4$ . Valid. (b) $g cd (12, 8) = 4 \neq = 2$ . Not a Bézout equation. (It's still a solvable Diophantine equation only if $4 ∣ 2$ , which is false — so it has no solutions at all.) (c) $g cd (6, 10) = 2$ . RHS $= 2$ . Valid.

Level 2 — Application

Now run the Extended Euclidean Algorithm end to end. Keep Picture A in mind: each back-substitution swaps a remainder for its recipe from the rung above, climbing the ladder until only $a$ and $b$ remain.

Exercise 2.1

Find integers $x, y$ with $17 x + 5 y = g cd (17, 5)$ .

Recall Solution 2.1

Forward — Euclidean Algorithm (divide, keep the remainder): $17 = 5 \cdot 3 + 2$ $5 = 2 \cdot 2 + 1$ $2 = 1 \cdot 2 + 0 \Rightarrow g cd = 1$ Back-substitute — start at the equation whose remainder is the gcd ( $1$ ). Why this works (Picture A): the line $1 = 5 - 2 \cdot 2$ already writes the gcd as a combination of $5$ and $2$ . But $2$ is not one of our originals — it is itself a remainder, so it has a recipe one rung up. Swapping it in trades $2$ for $17$ and $5$ . Since every swap only introduces numbers from higher rungs, we must eventually reach the top, where only $17$ and $5$ survive. $1 = 5 - 2 \cdot 2$ Replace $2$ using its recipe $2 = 17 - 5 \cdot 3$ : $1 = 5 - (17 - 5 \cdot 3) \cdot 2 = 5 - 2 \cdot 17 + 6 \cdot 5 = 7 \cdot 5 - 2 \cdot 17$ Only $17$ and $5$ remain — the ladder is climbed. So $17 \cdot (- 2) + 5 \cdot 7 = 1$ . $x = - 2, y = 7$ . Verify: $- 34 + 35 = 1$ . ✓

Exercise 2.2

Find Bézout coefficients for $a = 100, b = 36$ .

Recall Solution 2.2

Forward: $100 = 36 \cdot 2 + 28$ $36 = 28 \cdot 1 + 8$ $28 = 8 \cdot 3 + 4$ $8 = 4 \cdot 2 + 0 \Rightarrow g cd = 4$ Back-substitute from the $4$ -line. At each step (Picture A) the newest remainder is the one not originally $100$ or $36$ , so it is the one we replace by its higher recipe: $4 = 28 - 8 \cdot 3$ Replace $8 = 36 - 28 \cdot 1$ (climb one rung — swap out $8$ ): $4 = 28 - (36 - 28) \cdot 3 = 28 - 3 \cdot 36 + 3 \cdot 28 = 4 \cdot 28 - 3 \cdot 36$ Replace $28 = 100 - 36 \cdot 2$ (top rung reached — swap out $28$ ): $4 = 4 (100 - 36 \cdot 2) - 3 \cdot 36 = 4 \cdot 100 - 8 \cdot 36 - 3 \cdot 36 = 4 \cdot 100 - 11 \cdot 36$ So $x = 4, y = - 11$ . Verify: $400 - 396 = 4$ . ✓

Exercise 2.3

Find Bézout coefficients for $a = 1234, b = 54$ .

Recall Solution 2.3

Forward: $1234 = 54 \cdot 22 + 46$ $54 = 46 \cdot 1 + 8$ $46 = 8 \cdot 5 + 6$ $8 = 6 \cdot 1 + 2$ $6 = 2 \cdot 3 + 0 \Rightarrow g cd = 2$ Back-substitute from the $2$ -line. Why (Picture A): at each rung the equation already expresses $2$ using two remainders; we always replace the smaller, more-recently-created one by its recipe from the rung above, because that is the number still hiding the originals inside it. Each swap peels one layer off; after four swaps only $1234$ and $54$ are left. $2 = 8 - 6 \cdot 1$ $6 = 46 - 8 \cdot 5$ (swap out $6$ ): $2 = 8 - (46 - 8 \cdot 5) = 6 \cdot 8 - 46$ $8 = 54 - 46 \cdot 1$ (swap out $8$ ): $2 = 6 (54 - 46) - 46 = 6 \cdot 54 - 7 \cdot 46$ $46 = 1234 - 54 \cdot 22$ (top rung — swap out $46$ ): $2 = 6 \cdot 54 - 7 (1234 - 54 \cdot 22) = 6 \cdot 54 - 7 \cdot 1234 + 154 \cdot 54$ $2 = 160 \cdot 54 - 7 \cdot 1234$ So $x = - 7, y = 160$ (writing $1234 x + 54 y = 2$ ). Verify: $1234 (- 7) + 54 (160) = - 8638 + 8640 = 2$ . ✓

Exercise 2.4

Find Bézout coefficients for $a = 42, b = 0$ — the zero edge case.

Recall Solution 2.4

With $b = 0$ there is nothing to divide by on the second slot; the Euclidean Algorithm stops immediately and reports $g cd (42, 0) = 42$ (every integer divides $0$ , so the limiting divisor is $42$ itself). Bézout is then trivial: $42 \cdot 1 + 0 \cdot 0 = 42 = g cd (42, 0) .$ So $x = 1, y = 0$ (and $y$ may be any integer, since $0 \cdot y = 0$ always). Verify: $42 \cdot 1 + 0 \cdot 0 = 42$ . ✓

Level 3 — Analysis

Now reason about why and about all the solutions, not just one. Keep Picture B open: solutions are integer dots on one straight line, spaced by $(b / d, - a / d)$ .

Exercise 3.1

Using the seed $17 \cdot (- 2) + 5 \cdot 7 = 1$ from Exercise 2.1, write the general solution and find the solution with the smallest non-negative $x$ .

Recall Solution 3.1

The non-uniqueness rule from the parent note: if $(x_{0}, y_{0})$ works, so does $x = x_{0} + k \cdot \frac{b}{d}, y = y_{0} - k \cdot \frac{a}{d}, d = g cd (a, b) .$ Why (Picture B): replacing $(x_{0}, y_{0})$ by $(x_{0} + \frac{b}{d}, y_{0} - \frac{a}{d})$ changes the value $a x + b y$ by exactly $a \cdot \frac{b}{d} - b \cdot \frac{a}{d} = 0$ — the two shifts are equal and opposite, so you stay on the same line. And $\frac{b}{d}, \frac{a}{d}$ are the smallest whole steps that keep you on integer points, so this generates all integer solutions, evenly spaced. Here $d = 1$ , $a = 17$ , $b = 5$ , $(x_{0}, y_{0}) = (- 2, 7)$ : $x = - 2 + 5 k, y = 7 - 17 k .$ Smallest non-negative $x$ : need $- 2 + 5 k \geq 0 \Rightarrow k \geq \frac{2}{5} \Rightarrow k = 1$ . Then $x = 3, y = 7 - 17 = - 10$ . Verify: $17 \cdot 3 + 5 \cdot (- 10) = 51 - 50 = 1$ . ✓

Exercise 3.2

Explain, using the smallest-positive-combination idea, why $6 x + 4 y = 3$ has no integer solutions — and confirm with the gcd rule.

Recall Solution 3.2

Every value of $6 x + 4 y$ is a multiple of $g cd (6, 4) = 2$ , because $6 = 2 \cdot 3$ and $4 = 2 \cdot 2$ , so $6 x + 4 y = 2 (3 x + 2 y),$ which is always even. But $3$ is odd, so it can never be reached. In parent-note language: the smallest positive combination is $2$ , and every reachable value is a multiple of $2$ . The number $3$ is simply not on that grid. Gcd rule check: solutions exist $⟺ g cd (6, 4) ∣ 3 ⟺ 2 ∣ 3$ , which is false. No solutions. ✓

Level 4 — Synthesis

Combine Bézout with Modular Arithmetic and Linear Diophantine Equations.

Exercise 4.1

Find the multiplicative inverse of $7$ modulo $26$ (i.e. $x$ with $7 x \equiv 1 (mod 26)$ ), and give the answer in the range $0 \leq x < 26$ .

Recall Solution 4.1

An inverse exists because $g cd (7, 26) = 1$ (coprime). Solving $7 x + 26 y = 1$ gives $7 x \equiv 1 (mod 26)$ , because $26 y$ vanishes mod $26$ . Forward: $26 = 7 \cdot 3 + 5$ , $7 = 5 \cdot 1 + 2$ , $5 = 2 \cdot 2 + 1$ , $2 = 1 \cdot 2 + 0 \Rightarrow g cd = 1$ . Back (Picture A): start where the gcd $1$ appears, then keep swapping each remainder for its recipe one rung up until only $7$ and $26$ survive. $1 = 5 - 2 \cdot 2$ $2 = 7 - 5$ (swap out $2$ ): $1 = 5 - 2 (7 - 5) = 3 \cdot 5 - 2 \cdot 7$ $5 = 26 - 7 \cdot 3$ (top rung — swap out $5$ ): $1 = 3 (26 - 7 \cdot 3) - 2 \cdot 7 = 3 \cdot 26 - 11 \cdot 7$ So $7 \cdot (- 11) \equiv 1 (mod 26)$ . Reduce into range: $- 11 + 26 = 15$ . Inverse $= 15$ . Check: $7 \cdot 15 = 105 = 4 \cdot 26 + 1$ . ✓

Exercise 4.2

A machine dispenses only $\$ 9 $an d$ $16 $cr e d i t s (y o u ma y a dd or r e t u r n e i t h er) . S h o w t ha t y o u c ann e t * * e x a c tl y$ $1$**, and give one explicit combination.

Recall Solution 4.2

"Add or return" means coefficients may be negative — precisely a Bézout combination $9 x + 16 y$ . Since $g cd (9, 16) = 1$ , a total of $\$ 1 $i s a c hi e v ab l e . * * F or w a r d : * *$ 16 = 9\cdot 1 + 7 $,$ \ 9 = 7\cdot 1 + 2 $,$ \ 7 = 2\cdot 3 + 1 $,$ \ 2=1\cdot2+0 $. * * B a c k (P i c t u r e A) : * * c l imb f r o m t h e$ 1 $- l in e, s w a pp in g e a c h r e main d er f or i t sr ec i p e u n t i l o n l y$ 9 $an d$ 16 $remain. $$1 = 7 - 2\cdot 3$$$ 2 = 9 - 7 $(s w a p o u t$ 2 $) :$ \quad 1 = 7 - 3(9-7) = 4\cdot 7 - 3\cdot 97 = 16 - 9 $(t o p r u n g — s w a p o u t$ 7 $) :$ \quad 1 = 4(16 - 9) - 3\cdot 9 = 4\cdot 16 - 7\cdot 9 $S o$ 9\cdot(-7) + 16\cdot 4 = 1 $: * * r e t u r n se v e n$ $9 $cr e d i t s, a ddf o u r$ $16 $cr e d i t s . * * * * V er i f y : * *$ -63 + 64 = 1$. ✓

Level 5 — Mastery

Build and prove something.

Exercise 5.1

Prove: if $g cd (a, n) = 1$ and $g cd (b, n) = 1$ , then $g cd (ab, n) = 1$ . Use Bézout twice.

Recall Solution 5.1

Coprimality is equivalent to " $1$ is a Bézout combination". So there exist integers with $a x_{1} + n y_{1} = 1, b x_{2} + n y_{2} = 1.$ Multiply the two equations: $(a x_{1} + n y_{1}) (b x_{2} + n y_{2}) = 1 \cdot 1 = 1.$ Expand the left side and group so one term is a multiple of $ab$ and the rest a multiple of $n$ : $ab (x_{1} x_{2}) + n (a x_{1} y_{2} + b x_{2} y_{1} + n y_{1} y_{2}) = 1.$ Define the integers $X = x_{1} x_{2}, Y = a x_{1} y_{2} + b x_{2} y_{1} + n y_{1} y_{2} .$ Both are integers (sums and products of integers), and we have produced $(ab) X + n Y = 1.$ By the Bézout characterisation of coprimality, the existence of integers $X, Y$ with $(ab) X + nY = 1$ forces $g cd (ab, n) = 1$ . $■$

Exercise 5.2

The equation $12 x + 30 y = 18$ is a Diophantine equation. Decide whether it is solvable; if so, produce the full family of solutions and list the three with smallest $∣ x ∣$ .

Recall Solution 5.2

Solvable? $g cd (12, 30) = 6$ , and $6 ∣ 18$ (indeed $18 = 6 \cdot 3$ ). ✓ Solvable. Seed via Bézout on the gcd: $30 = 12 \cdot 2 + 6$ , so $6 = 30 - 12 \cdot 2 = 12 (- 2) + 30 (1)$ . Scale up by $\frac{18}{6} = 3$ to hit $18$ : $12 (- 6) + 30 (3) = 18 \Rightarrow (x_{0}, y_{0}) = (- 6, 3) .$ Full family (step by $\frac{b}{d} = \frac{30}{6} = 5$ and $\frac{a}{d} = \frac{12}{6} = 2$ ): $x = - 6 + 5 k, y = 3 - 2 k, k \in Z .$ Smallest $∣ x ∣$ : $x = - 6 + 5 k$ . At $k = 1, x = - 1$ ; $k = 2, x = 4$ ; $k = 0, x = - 6$ . The three smallest $∣ x ∣$ values are:

$k = 1 : (x, y) = (- 1, 1)$ — check $- 12 + 30 = 18$ ✓
$k = 2 : (x, y) = (4, - 1)$ — check $48 - 30 = 18$ ✓
$k = 0 : (x, y) = (- 6, 3)$ — check $- 72 + 90 = 18$ ✓

Read the figure below alongside this solution. The solid teal line is $12 x + 30 y = 18$ ; every burnt-orange dot on it is an integer solution. Notice the dots are evenly spaced: from any dot, stepping $Δ x = + 5$ across and $Δ y = - 2$ down lands you exactly on the next dot — this is the $(b / d, - a / d) = (5, - 2)$ step of Picture B, and it is why the family is $x = - 6 + 5 k, y = 3 - 2 k$ . The dashed plum line is the lower gcd line $12 x + 30 y = 6$ ; its square seed dot $(- 2, 1)$ is not on our target line. The dotted arrow shows the " $\times 3$ " scaling that lifts the gcd-seed onto the $= 18$ line — the move you make whenever the right-hand side is a multiple of the gcd rather than the gcd itself.

Recall Quick self-test after finishing

Solvable-check for $a x + b y = c$ ? ::: solutions exist $⟺ g cd (a, b) ∣ c$ . How do you turn a gcd-seed into a $c$ -solution? ::: multiply the seed pair by $c / g cd (a, b)$ . Step sizes in the general solution? ::: $x$ steps by $b / d$ , $y$ steps by $- a / d$ . Why does stepping by $(b / d, - a / d)$ keep the value fixed? ::: because $a \cdot (b / d) + b \cdot (- a / d) = 0$ , so the two changes cancel and you stay on the same line. Why does back-substitution end in $a x + b y = g cd$ ? ::: each swap trades a remainder for numbers from a higher rung, so you must eventually reach the top where only $a$ and $b$ remain. What is $g cd (a, 0)$ ? ::: $∣ a ∣$ , because every integer divides $0$ , so $a$ itself is the limiting divisor. Why does a modular inverse of $a$ exist mod $m$ ? ::: because $g cd (a, m) = 1$ lets you write $a x + m y = 1$ , so $a x \equiv 1 (mod m)$ .