Bézout's identity: Question bank — Maths deep dive

Before we start, one reminder that everything below leans on. When we write $a x + b y$ we mean: pick two integer "weights" $x$ and $y$ , scale $a$ by $x$ and $b$ by $y$ , and add. The weights may be negative (that's subtraction) or zero. The set of all such totals is what Bézout's proof studies. Keep that picture in mind — most traps here are people forgetting that $x, y$ roam over all integers, positive and negative.

The single most important picture for this whole bank is below: every integer combination $a x + b y$ lands on an evenly-spaced grid of dots, and the spacing of that grid is the GCD. Nothing between the dots is reachable.

Look at the red dots on the number line: they sit exactly $g cd (a, b)$ apart, starting at $0$ . The smallest positive dot is the GCD itself. This one image justifies "every combination is a multiple of the GCD" and "the GCD is the smallest positive combination" at the same time — refer back to it whenever a trap talks about what is or isn't reachable.

True or false — justify

Every integer of the form

a x + b y

(for integers

x, y

) is a multiple of

g cd (a, b)

True. Let

d = g cd (a, b)

; then

d ∣ a

and

d ∣ b

, so write

a = d \cdot p

and

b = d \cdot q

. Then

a x + b y = d (p x + q y)

, a multiple of

d

. Geometrically (see the grid figure) you can only ever land on the red dots spaced

d

apart, never between them.

The equation

a x + b y = 1

has integer solutions for any integers

a, b

False. The reachable dots are spaced

g cd (a, b)

apart, so

1

is only hit when that spacing is exactly

1

, i.e. when

a

and

b

are coprime. If

g cd (a, b) = d > 1

the nearest positive dot to

0

d

, and

1

falls in the gap — unreachable.

a x_{0} + b y_{0} = g cd (a, b)

, then

(x_{0}, y_{0})

is the only pair that works.

False, and here's why it must fail. Suppose

a x_{0} + b y_{0} = d

. Add zero cleverly:

a \cdot \frac{b}{d} + b \cdot (- \frac{a}{d}) = \frac{ab}{d} - \frac{ab}{d} = 0

. So bumping

x_{0}

up by

\frac{b}{d}

while dropping

y_{0}

\frac{a}{d}

changes the total by exactly

0

. Do this

k

times for any integer

k

and you get infinitely many valid pairs

(x_{0} + k \frac{b}{d}, y_{0} - k \frac{a}{d})

. The figure below shows these solutions marching along a straight line.

Bézout's identity guarantees you can write

g cd (a, b)

a x + b y

with both

x

and

y

positive.

False. If

a, b > 0

and both weights were

\geq 0

, the total would be at least

min (a, b)

(or

0

), but the GCD is usually smaller than both — so you must subtract one term, forcing a negative weight. Same-sign inputs almost always give one positive and one negative coefficient.

60 x + 90 y = 30

is solvable, but

60 x + 90 y = 20

is not.

True. The reachable values are exactly the multiples of

g cd (60, 90) = 30

. So

30

(which is

1 \times 30

) sits on a red dot, while

20

lands in the gap between

0

and

30

— off the grid, hence unsolvable.

a x + b y = 5

for some integers

x, y

, then

g cd (a, b) = 5

False. Reaching

5

only tells you

5

is a multiple of

g cd (a, b)

, i.e.

g cd (a, b) ∣ 5

, so the GCD is

1

5

. Bézout says the GCD is the smallest positive combination — not that every combination equals the GCD. Example:

2 \cdot 1 + 3 \cdot 1 = 5

yet

g cd (2, 3) = 1

For coprime

a, m

, the solution

x

a x + m y = 1

gives the modular inverse of

a

mod

m

True. Take

a x + m y = 1

and reduce everything modulo

m

; the term

m y

is a multiple of

m

so it vanishes, leaving

a x \equiv 1 (mod m)

. That is precisely the statement "

x

is the multiplicative inverse of

a

mod

m

Bézout's identity requires running the Extended Euclidean Algorithm to be true.

False. Existence is proved abstractly: the set of positive combinations is non-empty, so by the Well-Ordering Principle it has a least element, and that least element is shown to be the GCD. The algorithm only constructs explicit

x, y

— the truth of the identity does not depend on any computation.

Spot the error

g cd (12, 8) = 4

, and

12 (2) + 8 (- 2) = 24 - 16 = 8

, so the Bézout coefficients are

2

and

- 2

The total is

8

, not the GCD

4

; it equals

2 \times g cd

. A correct pair is

12 (- 1) + 8 (2) = 4

. The error is checking against the wrong right-hand side — Bézout demands the combination equal

g cd

, not a larger multiple.

"Since

S = {a x + b y > 0}

is non-empty and its smallest element is

d

, and

d ∣ a

, we're done —

d

must be the GCD."

Incomplete: showing

d

is a common divisor isn't enough; you must also show it's the greatest. Let

c

be any common divisor, so

a = c m

and

b = c n

for integers

m, n

. Then

d = a x_{0} + b y_{0} = c m x_{0} + c n y_{0} = c (m x_{0} + n y_{0})

, which shows

c ∣ d

. Every common divisor divides

d

, so

d

is the greatest.

a = 0, b = 0

: the smallest positive combination is

g cd (0, 0)

, so Bézout still applies."

Every combination of

0

and

0

0

, so the set of positive combinations is empty — no smallest element exists. Bézout explicitly excludes "both zero";

g cd (0, 0)

is undefined here.

"In the proof,

a = q d + r

with

0 \leq r < d

; if

r > 0

then

r \in S

and

r < d

contradicts minimality, so

r < 0

Wrong conclusion. The Division Algorithm forces

r \geq 0

, so the contradiction rules out

r > 0

, leaving

r = 0

(giving

d ∣ a

r

can never be negative.

"To get all solutions of

a x + b y = d

, shift by multiples of

a

and

b

x_{0} + k b

y_{0} - k a

You must divide by the GCD: the correct shift is

x_{0} + k \frac{b}{d}

y_{0} - k \frac{a}{d}

. Using

b

and

a

directly overshoots and skips valid solutions whenever

d > 1

(see the solution-line figure).

35 (1) + 15 (- 2) = 5

, and

- 2

is negative, so this can't be a valid Bézout pair."

Negative coefficients are perfectly valid — a "combination" allows subtraction.

35 - 30 = 5 = g cd (35, 15)

, so

(1, - 2)

is a genuine Bézout pair.

Why questions

Why is the smallest positive combination the GCD, rather than the largest or some middle value?

The largest is unbounded (scale up forever). The smallest positive one is special because the Division Algorithm forces it to divide both

a

and

b

— anything smaller would be a positive remainder still in the set, contradicting minimality.

Why does Bézout give an "if and only if" test for linear Diophantine solvability?

Every combination is a multiple of

d = g cd (a, b)

(necessity), and multiplying the Bézout relation by

c / d

builds a solution whenever

d ∣ c

(sufficiency) — both directions close the gap.

Why must at least one Bézout coefficient be negative when

a, b > 0

and

g cd (a, b) < min (a, b)

With both coefficients

\geq 0

the total is

\geq min (a, b)

(or zero), but the GCD is strictly smaller, so you can only reach it by subtracting — forcing a negative weight.

Why does the Euclidean Algorithm naturally produce Bézout coefficients when run in reverse?

Each remainder equals a combination of the previous two numbers; back-substituting chains these until the GCD is written purely in terms of the original

a

and

b

— the algorithm literally records the linear combination at every step.

Why is coprimality equivalent to "

a x + b y = 1

is solvable"?

g cd = 1

, Bézout directly gives

a x + b y = 1

. Conversely, any common divisor of

a, b

divides

a x + b y = 1

, forcing it to be

1

— so no common factor above

1

can exist.

Why does the general-solution shift leave

a x + b y

unchanged?

The added terms

a \cdot k \frac{b}{d}

and

- b \cdot k \frac{a}{d}

are equal in magnitude (

k \frac{ab}{d}

) and opposite in sign, so they cancel exactly — the total is untouched for every

k

Edge cases

What are the Bézout coefficients when

b = 0

(and

a > 0

g cd (a, 0) = a

, and

a \cdot 1 + 0 \cdot y = a

works for any

y

— so

x = 1

with any

y

is a solution; the non-uniqueness is especially visible here.

Does Bézout's identity hold for negative inputs like

a = - 12, b = 8

Yes.

g cd

is defined via absolute values (

g cd (- 12, 8) = 4

), and e.g.

(- 12) (1) + 8 (2) = 4

; signs of

a, b

just get absorbed into the choice of coefficients.

a = b

, what does Bézout give?

g cd (a, a) = ∣ a ∣

, reachable as

a \cdot 1 + a \cdot 0 = a

(for

a > 0

). The two "directions" collapse onto one, but the identity still holds trivially.

For coprime

a, b

, is

1

the only positive value smaller than both that's reachable?

1

is the smallest positive reachable value, and since it divides everything, all positive integers become reachable — coprimality makes the whole positive number line accessible as combinations.

Can

g cd (a, b)

ever be reached with

x = y = 0

Only if

g cd (a, b) = 0

, which requires

a = b = 0

— a case Bézout excludes. For valid inputs the GCD is positive, so the zero pair gives

0 \neq = g cd

Recall One-line summary + the picture to carry away

Bézout says $g cd (a, b)$ is the smallest positive thing you can build from $a$ and $b$ with signed integer weights; every combination is a multiple of it, coefficients are non-unique and often negative, and the "both zero" case is the sole exception. The schematic below is the whole idea in one frame: a number line whose reachable dots are spaced $g cd (a, b)$ apart, first positive dot circled as the GCD, gaps between dots forever unreachable.