Euclidean algorithm

The Euclidean algorithm repeatedly replaces $(a,b)$ by $(b,a\mathrm{mod}b)$ and terminates at $\gcd (a,b)$.

The extended Euclidean algorithm also computes integers $x,y$ satisfying $ax+by=\gcd (a,b)$. When $a$ and $b$ are coprime, either coefficient gives the corresponding modular multiplicative inverse.

A linear Diophantine equation in two variables has the form $ax+by=c$ with integer coefficients and seeks integer solutions.

If $a,b$ are nonzero integers, $d=\gcd (a,b)$, and $(x_0,y_0)$ is one solution of the linear Diophantine equation $ax+by=c$, then all solutions areSubtract two solutions and use the fact that $a/d$ and $b/d$ are coprime integers. The linear Diophantine equation solvability criterion says that a particular solution exists exactly when $d$ divides $c$; the extended Euclidean algorithm constructs one. This parametrization separates existence from the complete family of answers.

The equation $ax+by=c$ has an integer solution exactly when $\gcd (a,b)$ divides $c$. Bézout's identity proves sufficiency, while every integer linear combination of $a,b$ is divisible by their greatest common divisor.