= Solution
The <Euclidean algorithm> repeatedly replaces $(r_{i-1},r_i)$ by $(r_i,r_{i-1}-q_i r_i)$, where the new remainder lies between $0$ and $r_i-1$. Common divisors are unchanged by this subtraction, and decreasing positive remainders ensure termination. The last nonzero remainder is the <greatest common divisor>.
The <extended Euclidean algorithm> also tracks coefficients $r_i=u_i a+v_i b$, beginning with coefficient pairs $(1,0)$ and $(0,1)$ and applying the same subtraction to the pairs. This invariant produces <Bézout coefficients> for the last nonzero remainder. Here the divisions are
$$
580=2\cdot252+76,\qquad
252=3\cdot76+24,\qquad
76=3\cdot24+4,\qquad
24=6\cdot4.
$$
Back substitution gives
$$
4=76-3\cdot24=10\cdot76-3\cdot252=10\cdot580-23\cdot252.
$$
Thus \b[$\gcd(580,252)=4$], with \b[$m=10$ and $n=-23$] in <Bézout's identity>.
Back to article page
