TheoremProved

Bézout's identity

Statement

For integers $a,b$ not both zero, there exist integers $x,y$ such that $ax+by=\gcd(a,b)$ . Moreover, $\gcd(a,b)$ is the smallest positive integer expressible in this form.

Why is it true?

Running the Euclidean algorithm backward turns its sequence of divisions into an explicit combination of $a$ and $b$ that equals their greatest common divisor — so the gcd is always 'reachable' by adding and subtracting integer multiples of $a$ and $b$ .

Proof sketch

Let $S=\{ax+by : x,y\in\mathbb{Z}\}\cap\mathbb{Z}_{>0}$ ; it is non-empty (it contains $|a|$ or $|b|$ ), so by the well-ordering principle it has a least element $d=ax_0+by_0$ . Dividing $a$ by $d$ with remainder and using minimality of $d$ shows the remainder must be $0$ , so $d\mid a$ ; similarly $d\mid b$ . Any common divisor of $a,b$ divides $ax_0+by_0=d$ , so $d=\gcd(a,b)$ .

Topics that use this theorem

Greatest common divisor, least common multiple and the Euclidean algorithm

Related theorems

Fundamental theorem of arithmetic Chinese remainder theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

G. H. Hardy, E. M. Wright (2008). An Introduction to the Theory of Numbers · DOI:10.1093/oso/9780199219858.001.0001
Carl B. Boyer, Uta C. Merzbach (2011). A History of Mathematics