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

This page is the ground floor. Before we touch the proof in Bézout's Identity, we build every single symbol and idea the parent note quietly assumes — from the meaning of "divides" to what a "linear combination" looks like on a number line. Nothing is used before it is drawn.

0. The number line — our one true picture

Every idea below lives on a number line: a straight ruler stretching left (negative) and right (positive), with $0$ in the middle and evenly-spaced tick marks at the integers.

Keep this picture in your head. Almost everything in number theory is a statement about where the ticks land when you jump around this line.

1. The integers: the symbol $Z$

The picture: every tick mark on the number line above.

Why the topic needs it: Bézout's Identity is about combining $a$ and $b$ using whole-number multipliers. No fractions, no decimals. The symbol $\in$ means "is a member of", so " $x \in Z$ " reads aloud as " $x$ is an integer". When the parent writes $x, y \in Z$ it is promising: the coefficients are whole numbers. That restriction is the entire game — without it, $a x + b y$ could equal anything.

Recall What does

$x \in Z$ mean? $x$ is a whole number (positive, negative, or zero).

See Coprime Integers and Greatest Common Divisor for where these live.

2. "Divides": the symbol $∣$

This is the single most important idea in the whole topic, and it is nothing but a picture of even jumps.

The picture: start at $0$ , and take jumps of length $d$ . If you land exactly on $n$ , then $d ∣ n$ . If you overshoot or undershoot, it does not divide.

In the figure, jumps of $3$ land exactly on $12$ , so $3 ∣ 12$ (read: "three divides twelve"). But jumps of $5$ skip over $12$ (landing on $10$ , then $15$ ), so $5 ∤ 12$ (the slash means "does not divide").

Recall Is

$4 ∣ 10$ true or false, and why? False — jumps of $4$ from $0$ land on $8$ then $12$ , skipping $10$ . There is a remainder of $2$ .

3. Multiples and the Division Algorithm

Section 2 asked "does it land exactly?". The Division Algorithm answers the follow-up: "if not, by how much did we miss?"

The picture: take the biggest number of whole $d$ -jumps that still fits inside $a$ ; that count is $q$ . The little leftover gap before you reach $a$ is $r$ .

Why the topic needs it — and why THIS tool: The parent's proof (Step 4) writes $a = q d + r$ and then argues $r$ must be $0$ . That whole argument only works because the Division Algorithm guarantees $r$ exists, is unique, and is trapped in the range $0 \leq r < d$ . That trapped range is the trigger for the Well-Ordering contradiction later. No other tool pins the remainder down so tightly, which is exactly why it is chosen here.

Notice: $d ∣ a$ (Section 2) is just the special case where $r = 0$ .

Recall In

$47 = q \cdot 6 + r$ , what are $q$ and $r$ ? $q = 7$ , $r = 5$ , because $7 \cdot 6 = 42$ and $47 - 42 = 5$ (and $0 \leq 5 < 6$ ).

This is the engine of the Euclidean Algorithm.

4. Greatest Common Divisor: $g cd (a, b)$

The picture: draw the jump-sizes that land exactly on $a$ , and the jump-sizes that land exactly on $b$ . The biggest size that works for both is the GCD.

For $a = 12$ , $b = 8$ : divisors of $12$ are ${1, 2, 3, 4, 6, 12}$ , divisors of $8$ are ${1, 2, 4, 8}$ . The shared ones are ${1, 2, 4}$ , and the greatest is $4$ . So $g cd (12, 8) = 4$ .

Why the topic needs it: $g cd (a, b)$ is the number that appears on the right-hand side of Bézout: $a x + b y = g cd (a, b)$ . The entire identity is a claim about this specific number.

Full detail lives in Greatest Common Divisor.

5. Coprime: when $g cd = 1$

The picture: the shared-jump-size diagram from Section 4, but the biggest overlapping jump is the tiny step of size $1$ — the two numbers share no larger structure.

Why the topic needs it: many textbooks state Bézout as $a x + b y = 1$ , which is the coprime case. The parent warns (Mistake 1) not to think this is the only case. Coprimality is also the doorway to modular inverses. See Coprime Integers.

Recall Are

$9$ and $14$ coprime? Yes — divisors of $9$ are ${1, 3, 9}$ , of $14$ are ${1, 2, 7, 14}$ ; only $1$ is shared, so $g cd (9, 14) = 1$ .

6. Linear combination: the star of the show

Now we assemble the phrase "linear combination of $a$ and $b$ " — the object Bézout is entirely about.

The picture: $a x$ means "take $x$ jumps of length $a$ " ( $x$ can be negative — that means jump left). Then $b y$ adds " $y$ jumps of length $b$ ". The final landing spot is the value $a x + b y$ .

The figure shows $a = 6$ , $b = 4$ . Choosing $x = 1, y = - 1$ gives $6 \cdot 1 + 4 \cdot (- 1) = 2$ : one jump right of $6$ , one jump left of $4$ . We land on $2$ , which is $g cd (6, 4)$ ! That landing spot is Bézout's Identity in action.

Recall Write

$2$ as a linear combination of $6$ and $4$ . $6 (1) + 4 (- 1) = 2$ (many other answers exist too, e.g. $6 (- 1) + 4 (2) = 2$ ).

7. The set-builder ${\cdot : \cdot}$ and Well-Ordering

The parent's proof opens with $S = {a x + b y : x, y \in Z, a x + b y > 0}$ . Two pieces of notation to unpack.

The picture: of the infinitely many landing spots from Section 6, keep only the ones strictly to the right of zero. $S$ is that set of positive landing spots.

The picture: among positive landing spots, there are no positive numbers below $1$ , so you cannot "descend forever". Some spot must be the leftmost. That leftmost spot is what the parent calls $d$ — and the proof shows $d = g cd (a, b)$ .

Why the topic needs it: Well-Ordering is what lets the proof say "let $d$ be the smallest element of $S$ ". Without it, "smallest" might not exist. This is the logical hinge of the whole derivation.

Recall Why must

$S$ have a smallest element? Because $S$ is a non-empty set of positive integers, and the Well-Ordering Principle guarantees any such set has a least member.

8. How it all connects

Read top to bottom: the integers give us "divides"; "divides" gives the Division Algorithm and the GCD; linear combinations form the set $S$ ; Well-Ordering picks its smallest element; and all these streams meet at Bézout's Identity. From there the road continues to the Extended Euclidean Algorithm, Linear Diophantine Equations, and Modular Arithmetic.

Equipment checklist

Cover the right-hand side and see if you can answer each before revealing.

The symbol

Z

means

the set of all integers

{\dots, - 2, - 1, 0, 1, 2, \dots}

\in

means

"is a member of" — so

x \in Z

says

x

is an integer.

d ∣ n

means

d

divides

n

exactly:

n = d k

for some integer

k

, no remainder.

d ∤ n

means

d

does not divide

n

(there is a nonzero remainder).

The Division Algorithm guarantees

unique

q, r

with

a = q d + r

and

0 \leq r < d

g cd (a, b)

the largest integer that divides both

a

and

b

"Coprime" means

g cd (a, b) = 1

; the only common divisor is

1

An integer linear combination of

a, b

any number

a x + b y

with

x, y \in Z

Coefficients

x, y

may be negative because

a negative coefficient just means jumping in the opposite direction on the number line.

The set

S = {a x + b y : x, y \in Z, a x + b y > 0}

all positive numbers reachable as a linear combination of

a

and

b

The Well-Ordering Principle says

every non-empty set of positive integers has a smallest element.

The one core idea of Bézout's Identity is

the smallest positive linear combination of

a

and

b

equals

g cd (a, b)

, giving

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

Once every reveal feels obvious, you are ready for the full proof in Bézout's Identity.