Bézout's Identity: Integers and Polynomials over a Field

On this page

Interactive

Bézout coefficients travel alongside the remainders

ExtendAutoReset

Extended Euclidean table for a = 30, b = 18

q	r	x	y	a·x + b·y

Press Extend to compute the next remainder and its coefficients.

a·x + b·y = gcd(a, b)

A greatest common divisor is more than a number that divides two inputs: it is itself an integer linear combination of them. This fact is useful, for example, when constructing modular inverses. For $a=30$ and $b=18$, the Euclidean algorithm gives $30-18=12$, $18-12=6$, and $12-2\cdot6=0$, so

$6=18-12=2\cdot18-30.$

The identity below explains why such coefficients always exist, including when the inputs are negative.

Bézout’s identity for integers

Let $a,b\in\mathbb Z$ be not both zero and put $g=\gcd(|a|,|b|)>0$. Then there are integers $x,y$ such that

$ax+by=g.$

Moreover, the integer linear combinations of $a,b$ are exactly the multiples of $g$:

$\{ax+by:x,y\in\mathbb Z\}=g\mathbb Z.$

Proof by the least positive combination

Consider

$S=\{ax+by:x,y\in\mathbb Z,\ ax+by>0\}.$

This set is nonempty: since at least one input is nonzero, its absolute value is a positive combination (choose its coefficient to be $1$ or $-1$ as needed, and the other coefficient $0$). By well-ordering, $S$ has a least element $m=ax_0+by_0>0$.

Divide $a$ by $m$: $a=qm+r$ with $0\le r<m$. Since $m=ax_0+by_0$,

$r=a-qm=a(1-qx_0)+b(-qy_0),$

so $r$ is also an integer linear combination. If $r>0$, it would be in $S$ and smaller than $m$, a contradiction. Hence $r=0$, so $m\mid a$. Applying the same argument to $b$ gives $m\mid b$.

Every common divisor of $a,b$ divides every linear combination, including $m$. Thus $m$ is a positive common divisor divisible by every common divisor: it is $g$. Its defining expression proves $ax_0+by_0=g$.

Since $g$ divides both inputs, it divides every $ax+by$. Conversely, multiplying $ax_0+by_0=g$ by any integer $n$ shows $ng=a(nx_0)+b(ny_0)$. Therefore the combinations are precisely $g\mathbb Z$.

Polynomial version—over a field

This is a separate statement with a different coefficient domain. Let $K$ be a field, and let $f,g\in K[x]$ not both be zero. Let $I=(f,g)\subseteq K[x]$ be the ideal they generate; if $d$ is their monic greatest common divisor, then

$$\begin{aligned} uf+vg &= d\quad\text{for some }u,v\in K[x],\\ I=dK[x]. \end{aligned}$$

To see this, take the nonzero elements of $I=\{uf+vg:u,v\in K[x]\}$, choose one of least degree, and scale it to be monic; call it $d$. Polynomial division over $K$ gives $f=qd+r$, where $r=0$ or $\deg r<\deg d$. As $d\in I$, also $r=f-qd\in I$; minimality forces $r=0$, so $d\mid f$. The same argument gives $d\mid g$. Every common divisor of $f,g$ divides every element of $I$, including $d$, so $d$ is their monic gcd. Because $d\in I$, it has a representation $uf+vg=d$. All combinations are divisible by $d$, and multiplying this representation by any polynomial shows every multiple of $d$ is a combination. Hence $I=dK[x]$. This proof uses division with remainder over a field; it does not assert the result for arbitrary coefficient rings.

Source and attribution

The polynomial extension was prompted by Tistory ID 25, published on 2022-04-03 by 0archlinux0 / MINJUN PARK and marked CC BY 4.0. That source states the polynomial analogue but does not prove it there; the field-based proof above is supplied separately.