Bézout's identity ($\gcd (a,b)=ax+by$)

For integers $a,b$ not both zero, there are integers $x,y$ such that $ax+by=\gcd (a,b)$. The extended Euclidean algorithm constructs them. For example, $4\cdot 252-5\cdot 198=18$ and $7\cdot 5-2\cdot 17=1$; the second identity also gives the modular inverse of $5$ modulo $17$.

The identity converts a greatest common divisor into a solvability certificate. The linear Diophantine equation $ax+by=c$ is solvable in integers precisely when $\gcd (a,b)$ divides $c$. Every common divisor divides any integer linear combination; conversely, multiplying a Bézout identity by $c/\gcd (a,b)$ constructs a solution when that quotient is integral. The coefficients generally are not unique, as the description of all solutions of a linear Diophantine equation makes explicit.

Bézout coefficients for integers $a,b$ are integers $x,y$ satisfying Bézout's identity $ax+by=\gcd (a,b)$. The extended Euclidean algorithm computes one pair. They need not be unique: both $(x,y)=(7,-2)$ and $(-10,3)$ work for $(a,b)=(5,17)$, since $35-34=1$ and $-50+51=1$.