Bézout's Identity/Proof 1
Jump to navigation
Jump to search
Theorem
Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Let $\gcd \set {a, b}$ be the greatest common divisor of $a$ and $b$.
Then:
- $\exists x, y \in \Z: a x + b y = \gcd \set {a, b}$
That is, $\gcd \set {a, b}$ is an integer combination (or linear combination) of $a$ and $b$.
Furthermore, $\gcd \set {a, b}$ is the smallest positive integer combination of $a$ and $b$.
Proof
Work the Euclidean Division Algorithm backwards.
$\blacksquare$
Source of Name
This entry was named for Étienne Bézout.
Sources
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): $\S 12.3$: Highest common factors and Euclid's algorithm