Bézout's identity: Worked examples — Maths deep dive

Before anything else, recall the single equation everything on this page serves:

The scenario matrix

Every Bézout problem falls into one of these cells. The examples below are tagged with the cell they cover.

#	Cell (case class)	What is unusual	Covered by
C1	Both positive, $g cd > 1$	the "standard" run	Ex 1
C2	Coprime pair, $g cd = 1$	answer must equal $1$	Ex 2
C3	One number divides the other	Euclid stops in one line	Ex 3
C4	A negative input	signs of coefficients flip	Ex 4
C5	One input is zero	degenerate — no algorithm needed	Ex 5
C6	Modular inverse (why we care)	rephrasing $a x + m y = 1$	Ex 6
C7	Word problem (jugs of water)	translate story → equation	Ex 7
C8	Exam twist: solve $a x + b y = c$ with $c \neq = g cd$	scale + shift a solution	Ex 8

The tools we lean on: the Euclidean algorithm (repeated division to find the GCD), back-substitution (the extended version that also returns $x, y$ ), and the shift rule for generating all solutions. Each is why-justified as it appears.

Example 1 — C1: both positive, GCD bigger than 1

Worked example Find

$x, y$ with $252 x + 198 y = g cd (252, 198)$ .

Forecast: Guess the GCD first. Both are even and both are divisible by $9$ (digit sums $9$ and $18$ )... so $g cd$ is a multiple of $18$ . Is it exactly $18$ ? Predict, then check.

Step 1 — Run the Euclidean algorithm.

252 &= 198\cdot 1 + 54\\ 198 &= 54\cdot 3 + 36\\ 54 &= 36\cdot 1 + 18\\ 36 &= 18\cdot 2 + 0 \end{aligned}$$ *Why this step?* Each line replaces a big pair by a smaller pair with the **same** GCD (subtracting a multiple of one number changes nothing they both share). The last non-zero remainder, $18$, is $\gcd(252,198)$. Forecast confirmed. **Step 2 — Back-substitute to reach $18$.** Start from the line that produced $18$: $$18 = 54 - 36\cdot 1.$$ *Why this step?* We want $18$ written using $252$ and $198$ only. We climb back up, replacing each remainder ($36$, then $54$) by its own earlier expression. Replace $36 = 198 - 54\cdot 3$: $$18 = 54 - (198 - 54\cdot 3) = 4\cdot 54 - 198.$$ Replace $54 = 252 - 198\cdot 1$: $$18 = 4(252 - 198) - 198 = 4\cdot 252 - 5\cdot 198.$$ **Answer:** $x = 4,\; y = -5$. **Verify:** $252(4) + 198(-5) = 1008 - 990 = 18 = \gcd$. ✓ Notice one coefficient is negative — expected, since two positives must partly cancel.

The figure shows what "smallest positive combination" means: mark every value $252 x + 198 y$ on the number line and the nearest one above zero lands exactly on $18$ .

Example 2 — C2: a coprime pair (GCD = 1)

Example 3 — C3: one number divides the other

Example 4 — C4: a negative input

Worked example Find

$x, y$ with $(- 24) x + 33 y = g cd (- 24, 33)$ .

Forecast: The GCD ignores signs — it is a magnitude. So $g cd (- 24, 33) = g cd (24, 33)$ . Both share $3$ . Predict $g cd = 3$ , and expect a sign to flip in the coefficients versus the all-positive version.

Step 1 — Solve the positive version first. Work with $24$ and $33$ :

33 &= 24\cdot 1 + 9\\ 24 &= 9\cdot 2 + 6\\ 9 &= 6\cdot 1 + 3\\ 6 &= 3\cdot 2 + 0 \end{aligned}$$ So $\gcd(24,33)=3$. *Why this step?* Signs don't affect divisibility, so it's cleanest to run Euclid on absolute values, then restore signs at the end. **Step 2 — Back-substitute for $24,33$.** $$3 = 9 - 6.$$ Replace $6 = 24 - 9\cdot 2$: $\;3 = 9 - (24 - 18) = 3\cdot 9 - 24$. Replace $9 = 33 - 24$: $\;3 = 3(33 - 24) - 24 = 3\cdot 33 - 4\cdot 24$. So $24(-4) + 33(3) = 3$. **Step 3 — Restore the negative sign.** We need $(-24)x$, and we have $24\cdot(-4)$. Since $24\cdot(-4) = (-24)\cdot(4)$, flip the sign of that coefficient: $$(-24)(4) + 33(3) = 3.$$ *Why this step?* Moving the minus into the variable $a=-24$ means the coefficient must absorb the opposite sign to keep the product identical. **Answer:** $x = 4,\; y = 3$. **Verify:** $(-24)(4) + 33(3) = -96 + 99 = 3 = \gcd$. ✓

Example 5 — C5: one input is zero (degenerate)

Example 6 — C6: modular inverse (why coprimality matters)

Worked example Find the multiplicative inverse of

$7$ modulo $26$ .

Forecast: An inverse exists iff $g cd (7, 26) = 1$ . $7$ is prime and doesn't divide $26$ , so predict the inverse exists. We are secretly solving $7 x + 26 y = 1$ ; the $x$ is the inverse.

Step 1 — Euclidean algorithm.

26 &= 7\cdot 3 + 5\\ 7 &= 5\cdot 1 + 2\\ 5 &= 2\cdot 2 + 1\\ 2 &= 1\cdot 2 + 0 \end{aligned}$$ GCD $= 1$, so the inverse exists. *Why this step?* [[Modular Arithmetic|Modular]] inverse of $a$ mod $m$ means finding $x$ with $ax \equiv 1 \pmod m$. Bézout gives that $x$ whenever $\gcd(a,m)=1$. **Step 2 — Back-substitute to $1$.** $$1 = 5 - 2\cdot 2.$$ Replace $2 = 7 - 5$: $\;1 = 5 - 2(7-5) = 3\cdot 5 - 2\cdot 7$. Replace $5 = 26 - 7\cdot 3$: $\;1 = 3(26 - 21) - 2\cdot 7 = 3\cdot 26 - 11\cdot 7$. So $7(-11) + 26(3) = 1$. **Step 3 — Read the inverse.** The coefficient of $7$ is $x=-11$. Reduce mod $26$: $-11 + 26 = 15$. *Why this step?* $7x + 26y = 1$ means $7x \equiv 1 \pmod{26}$ (the $26y$ term is $0$ mod $26$). The inverse is $x$ taken in the range $0$ to $25$. **Answer:** $7^{-1} \equiv 15 \pmod{26}$. **Verify:** $7\cdot 15 = 105 = 4\cdot 26 + 1$, so $7\cdot 15 \equiv 1 \pmod{26}$. ✓

Example 7 — C7: word problem (two water jugs)

Worked example You have a

$21$ -litre jug and a $15$ -litre jug and a big tub. By filling and pouring (each full jug adds its size; emptying a jug back subtracts its size), can you measure out exactly $3$ litres? How?

Forecast: "Measure $c$ litres with jugs of size $a$ and $b$ " is solvable iff $g cd (a, b) ∣ c$ . Here $g cd (21, 15) = 3$ and $3 ∣ 3$ , so predict yes.

Step 1 — Translate to an equation. Let $x$ = net times we use the $21$ -jug (pour in $= +$ , empty out $= -$ ), $y$ likewise for the $15$ -jug. We want $21 x + 15 y = 3.$ Why this step? Every fill adds a jug's volume, every empty subtracts it, so the net measured amount is a linear combination — exactly Bézout.

Step 2 — Euclidean algorithm.

21 &= 15\cdot 1 + 6\\ 15 &= 6\cdot 2 + 3\\ 6 &= 3\cdot 2 + 0 \end{aligned}$$ $\gcd = 3$ divides $3$. ✓ **Step 3 — Back-substitute.** $$3 = 15 - 6\cdot 2.$$ Replace $6 = 21 - 15$: $\;3 = 15 - 2(21 - 15) = 3\cdot 15 - 2\cdot 21$. So $21(-2) + 15(3) = 3$. *Why this step?* This tells the physical recipe: use the $21$-jug $2$ times as an **empty** ($-2$) and the $15$-jug $3$ times as a **fill** ($+3$). **Answer:** Fill the $15$-jug **three** times (pour $45$ L into the tub) and empty the $21$-jug **twice** (remove $42$ L), leaving $3$ L. $x=-2,\;y=3$. **Verify:** $21(-2) + 15(3) = -42 + 45 = 3$ litres. ✓ Units: litres in, litres out, litres remaining — consistent.

Example 8 — C8: exam twist, solve $a x + b y = c$ with $c \neq = g cd$

Worked example Solve

$252 x + 198 y = 90$ for integers, and give all solutions.

Forecast: From Example 1, $g cd (252, 198) = 18$ . Is $90$ a multiple of $18$ ? $90 = 18 \cdot 5$ , yes — so predict solutions exist. This connects to linear Diophantine equations.

Step 1 — Check solvability. $a x + b y = c$ has integer solutions iff $g cd ∣ c$ . Here $18 ∣ 90$ . ✓ Why this step? Any combination of $252$ and $198$ is a multiple of their GCD $18$ ; a target not divisible by $18$ is unreachable.

Step 2 — Scale the base Bézout solution. From Ex 1, $252 (4) + 198 (- 5) = 18$ . Multiply the whole equation by $\frac{c}{g cd} = \frac{90}{18} = 5$ : $252 (4 \cdot 5) + 198 (- 5 \cdot 5) = 18 \cdot 5 = 90.$ So a particular solution is $x_{0} = 20, y_{0} = - 25$ . Why this step? Scaling both sides by the same factor keeps the equality and lands us on the desired right-hand side $90$ .

Step 3 — Generate all solutions with the shift rule. With $d = g cd = 18$ : $x = x_{0} + k \cdot \frac{b}{d} = 20 + k \cdot \frac{198}{18} = 20 + 11 k,$ $y = y_{0} - k \cdot \frac{a}{d} = - 25 - k \cdot \frac{252}{18} = - 25 - 14 k, k \in Z .$ Why this step? Adding $\frac{b}{d}$ to $x$ and subtracting $\frac{a}{d}$ from $y$ changes the total by $a \frac{b}{d} - b \frac{a}{d} = 0$ , so every $k$ gives another valid pair.

Answer: $x = 20 + 11 k, y = - 25 - 14 k$ .

Verify: Base $k = 0$ : $252 (20) + 198 (- 25) = 5040 - 4950 = 90$ . ✓ Now $k = 1$ : $x = 31, y = - 39$ , $252 (31) + 198 (- 39) = 7812 - 7722 = 90$ . ✓

The figure plots the solution pairs $(x, y)$ for several $k$ : they land on a straight line of step $(+ 11, - 14)$ — the lattice of all Diophantine solutions.

Recall Which cell am I in? (quick decision table)

Is one input $0$ ? ::: Cell C5 — the non-zero number is the GCD; the other coefficient is free. Does one number divide the other exactly? ::: Cell C3 — Euclid ends in one line; use $x = 0, y = 1$ style. Is $g cd (a, b) = 1$ ? ::: Cell C2/C6 — you can reach $1$ ; the coefficient of $a$ is $a$ 's modular inverse. Is there a negative input? ::: Cell C4 — solve with absolute values, then push the sign into the variable. Right-hand side isn't the GCD? ::: Cell C8 — check $g cd ∣ c$ , scale by $c / g cd$ , then shift by $(b / d, - a / d)$ .