Number TheoryDifficulty 35-851 tagged problems

Bezout Identity

Bezout Identity is the habit of expressing gcds as integer linear combinations to prove existence and solve congruences. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\gcd(a, b) = ax + by \quad \text{for some integers } x, y$$

The gcd of two integers can always be written as an integer combination of them, and it is the smallest positive value such a combination can take.

Why It Works

1
Let $d$ be the smallest positive integer of the form $ax + by$ with $x, y \in \mathbb{Z}$.
2
Dividing $a$ by $d$ gives $a = qd + r$ with $0 \le r < d$; then $r = a - qd = a(1 - qx) + b(-qy)$ is also a combination of $a$ and $b$.
3
Since $r < d$ and $d$ is the smallest positive such combination, $r = 0$, so $d \mid a$; similarly $d \mid b$.
4
Any common divisor of $a$ and $b$ divides $ax + by = d$, so $d = \gcd(a,b)$. The coefficients $x, y$ come from running the Euclidean algorithm backward.

Worked Examples

Example 1

Express $\gcd(17, 5)$ as $17x + 5y$ for integers $x, y$.

1
Euclidean steps: $17 = 3 \cdot 5 + 2$ and $5 = 2 \cdot 2 + 1$, so $\gcd = 1$.
2
Back-substitute the last step: $1 = 5 - 2 \cdot 2$.
3
Replace $2 = 17 - 3 \cdot 5$: $1 = 5 - 2(17 - 3 \cdot 5) = 5 - 2 \cdot 17 + 6 \cdot 5 = 7 \cdot 5 - 2 \cdot 17$.
4
So $17(-2) + 5(7) = -34 + 35 = 1$, giving $x = -2$, $y = 7$.

Answer:

$1 = 17(-2) + 5(7)$

Warm-up

Express $\gcd(40, 24)$ as $40x + 24y$ for integers $x, y$.

1
Euclidean steps: $40 = 1 \cdot 24 + 16$, $24 = 1 \cdot 16 + 8$, $16 = 2 \cdot 8 + 0$, so $\gcd = 8$.
2
Back-substitute: $8 = 24 - 1 \cdot 16$.
3
Replace $16 = 40 - 24$: $8 = 24 - (40 - 24) = 2 \cdot 24 - 40$.
4
So $40(-1) + 24(2) = -40 + 48 = 8 = \gcd(40, 24)$.

Answer:

$8 = 40(-1) + 24(2)$

Contest level

Find the largest integer that CANNOT be written as $7a + 11b$ for nonnegative integers $a, b$ (the Chicken McNugget / Frobenius number for $7$ and $11$).

1
Since $\gcd(7, 11) = 1$, Bézout guarantees integer (possibly negative) solutions to $7a + 11b = n$ for every $n$; the question is when nonnegative solutions exist.
2
For coprime $m, n$, the Frobenius (Chicken McNugget) number — the largest integer not expressible as a nonnegative combination — is $mn - m - n$. Here that is $77 - 18 = 59$.
3
Check $59$ is not representable: $59 = 7a + 11b$ needs $11b \le 59$, so $b \in \{0,1,2,3,4,5\}$; the residues $59 - 11b = 59, 48, 37, 26, 15, 4$ are none divisible by $7$ ($59\equiv 3, 48\equiv 6, 37\equiv 2, 26\equiv 5, 15\equiv 1, 4\equiv 4 \pmod 7$).
4
Check $60$ is representable: $60 = 7 \cdot 7 + 11 \cdot 1 = 49 + 11$. And every $n \ge 60$ is representable by the Frobenius theorem.

Answer:

$59$ is the largest non-representable integer (Frobenius number $= 7 \cdot 11 - 7 - 11$).

Olympiad / Challenge

Prove that $\gcd(a, b) = 1$ if and only if there exist integers $x, y$ with $ax + by = 1$.

1
($\Rightarrow$) If $\gcd(a,b) = 1$, Bézout's identity (the gcd is the least positive value of $ax + by$, shown via the division algorithm) gives integers with $ax + by = 1$.
2
($\Leftarrow$) Suppose $ax + by = 1$ for some integers. Let $d = \gcd(a, b)$, so $d \mid a$ and $d \mid b$.
3
Then $d$ divides the linear combination $ax + by = 1$, so $d \mid 1$, forcing $d = 1$.
4
Both directions hold, establishing the equivalence — the algebraic characterization of coprimality that underlies modular inverses and CRT.

Answer:

$\gcd(a,b) = 1 \iff \exists\, x, y \in \mathbb{Z}$ with $ax + by = 1$.

Going Deeper

Generalization: Bézout extends to several integers — $\gcd(a_1, \dots, a_k)$ is the least positive value of $a_1 x_1 + \cdots + a_k x_k$ — and is the source of the fact that $\gcd(a,b) = 1 \iff ax+by=1$, which characterizes when modular inverses and the Chinese Remainder Theorem apply.
Where it appears: computing modular inverses (solve $ax + ny = 1$, then $x \equiv a^{-1} \pmod n$), constructing CRT solutions, proving coprimality, and the existence half of solving linear Diophantine equations $ax + by = c$.
Pitfall: the coefficients $x, y$ are NOT unique — you can add $(b/g, -a/g) \cdot t$ to any solution. Beginners also overreach: $ax + by = c$ is solvable iff $\gcd(a,b) \mid c$, so $ax+by=1$ requires $\gcd(a,b) = 1$ exactly; if the gcd is $g > 1$ the smallest positive combination is $g$, not $1$.

Spot the Signal

Look for problems where the key step is expressing gcds as integer linear combinations to prove existence and solve congruences.
You can describe the hard part as expressing gcds as integer linear combinations to prove existence and solve congruences, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for bezout identity, then rewrite the givens around it.
Name the relation that makes Bezout Identity legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Bezout Identity just because the surface looks familiar; verify the required condition first.
Applying Bezout Identity because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let bezout identity reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is expressing gcds as integer linear combinations to prove existence and solve congruences.