{c}
{title2=$\gcd(a,b)=ax+by$}
{wiki}

= Bezout identity
{c}
{synonym}

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\cdot252-5\cdot198=18$ and $7\cdot5-2\cdot17=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's identity (source code)