Bézout's identity

In number theory, Bézout's identity, named after Étienne Bézout, is a linear diophantine equation. It states that if a and b are integers with greatest common divisor d, then there exist integers x and y (called Bézout numbers or Bézout coefficients) such that

ax + by = d.

Numbers x and y as above can be determined with the extended Euclidean algorithm, but they are not uniquely determined: $a(x-kb)+b(y+ka)=ax-kba+by+kba=ax+by$ for every a, b, x, y, and k. So, letting k range over the integers and setting $x^{\prime }=x-kb$, $y^{\prime }=y+ka$, we have $ax^{\prime }+by^{\prime }=ax+by$.

For example, the greatest common divisor of 12 and 42 is 6, and we can write

12x + 42y = 6.

with some of the solutions being

(-3)·12 + 1·42 = 6

and also

4·12 + (-1)·42 = 6.

Bézout's identity can also be extended to linear combinations of more than two numbers. For any numbers $a_{1},\ldots ,a_{n}$ with greatest common divisor g there exist integers $x_{1},\ldots ,x_{n}$ such that

$a_{1}x_{1}+\cdots +a_{n}x_{n}=g$

The greatest common divisor of $a_{1},\ldots ,a_{n}$ is in fact the smallest positive integer that can be written as a linear combination of $a_{1},\ldots ,a_{n}$.

Bézout's identity works not only in the ring of integers, but also in any other principal ideal domain (PID). That is, if R is a PID, and a and b are elements of R, and d is a greatest common divisor of a and b, then there are elements x and y in R such that ax + by = d. The reason: the ideal Ra+Rb is principal and indeed is equal to Rd. An integral domain in which Bézout's identity holds is called a Bézout domain.

To confirm: In some credible books, this identity has been attributed to French mathematician Claude Gaspard Bachet de Méziriac.

Proof.

Suppose that $a=dp$ and $b=dq$ where $d=\gcd(a,b)$ and $\gcd(p,q)=1$. Now take the numbers $p,2p,\cdots ,(q-1)p$. It's easy to show that

1. There doesn't exist any $1\leq i\leq q-1$, so that $ip=q{\pmod {q}}\,\!$.
2. There aren't any two numbers like $1\leq i<j\leq q-1$ so that $ip=jp{\pmod {q}}\,\!$.

From these two we conclude that $\{p,2p,\cdots ,(q-1)p\}=\{1,2,\cdots ,q-1\}{\pmod {q}}$.

Therefore, there exists an integer like $1\leq x\leq q-1$ so that $px=1{\pmod {q}}\,\!$. So there exists an integer $y$ so that $px+qy=1$, and by multiplying this equation by $d$ we have $ax+by=d$.

External links

• Online calculator of Bézout's identity.