Euclidean algorithm in a Euclidean domain

Summary

Let $R$ be a Euclidean domain with Euclidean function $\delta$ and let $a, b \in R$. The Euclidean algorithm sets $r_0 = a$ and $r_1 = b$. While $r_k \neq 0$, it divides $r_{k-1}$ by $r_k$ and lets $r_{k+1}$ be the remainder. The values $\delta(r_k)$ decrease strictly, so the algorithm stops with some $r_{n+1} = 0$. The last nonzero remainder $r_n$ is a greatest common divisor of $a$ and $b$, if $b \neq 0$.

Remarks

The algorithm works because the common divisors of $r_{k-1}$ and $r_k$ are the common divisors of $r_k$ and $r_{k+1}$. In $\mathbb{Z}$: $252 = 1 \cdot 198 + 54$, $198 = 3 \cdot 54 + 36$, $54 = 1 \cdot 36 + 18$, $36 = 2 \cdot 18$. So $\gcd(252, 198) = 18$. The extended algorithm also gives the coefficients of Bézout's identity.

Explanations

L1 human

To find the gcd of two numbers, replace the larger one by its remainder modulo the smaller one, and repeat. When the remainder is zero, the last divisor is the gcd. The same steps work in every Euclidean domain, for example for polynomials over a field.