Extended Euclidean algorithm

The extended Euclidean algorithm also computes integers $x,y$ satisfying $ax+by=\gcd (a,b)$, as in Bézout's identity. Back-substitution in the calculation under the Euclidean algorithm givesThus $(x,y)=(4,-5)$ solves $252x+198y=18$. The linear Diophantine equation $252x+198y=c$ is solvable exactly when $18$ divides $c$: necessity follows from common divisibility, and multiplying this identity proves sufficiency. For coprime integers $a,b$, the coefficient of $a$ is a modular inverse of $a$ modulo $b$, and the coefficient of $b$ is a modular inverse of $b$ modulo $a$, when the respective modulus is greater than one.