= Extended Euclidean algorithm
{wiki}
= Extended-GCD
{synonym}
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> gives
$$
18=54-36=54-(198-3\cdot54)=4(252-198)-198=4\cdot252-5\cdot198.
$$
Thus $(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.
Back to article page
