= Solution
{c}
The <euclidean algorithm> computes the <greatest common divisor> of two <integers> by repeated <division with remainder>. Start with $r_0=|A|$, $r_1=|B|$, interchanging them if necessary, and repeatedly write
$$
r_{j-1}=q_jr_j+r_{j+1},\qquad 0\le r_{j+1}<r_j,
$$
until a zero remainder occurs. The positive remainders strictly decrease, so the process terminates. At each step the common <divisors> of $r_{j-1},r_j$ are exactly the common <divisors> of $r_j,r_{j+1}$, because $r_{j+1}=r_{j-1}-q_jr_j$. Hence
$$
\boxed{\gcd(A,B)=\text{the last nonzero remainder}.}
$$
If one input is zero, the answer is the <absolute value> of the other; the usual convention sets $\gcd(0,0)=0$. Back-substitution also expresses the <greatest common divisor> as an <integer linear combination> of the inputs, as in <Bézout's identity>.
Back to article page
