Def/Euclidean algorithm

Definition of Euclidean algorithm: Suppose that $a$ and $b$ are elements of a Euclidean domain $R$ (such as $\ZZ$, $\ZZ[i]$, or $\RR[X]$, for example), and suppose that $b \neq 0$. Let $\sigma$ be a Euclidean valuation on $R$; for example,

• If $R = \ZZ$ or $\ZZ[i]$, let $\sigma(r) = \vert r \vert$ for $0 \neq r \in \ZZ$.
• If $R = \RR[X]$, let $\sigma(r) = deg(r)$ for $0 \neq r \in \RR[X]$.

The Euclidean algorithm refers to the recursive process of repeated division with remainder, which proceeds as follows:

1. Let $r_{-2} = a$ and $r_{-1} = b$.
2. Let $k = 0$.
3. Let $q_k$ and $r_k$ be a quotient and remainder obtained by dividing $r_{k-2}$ by $r_{k-1}$. In particular,
   • $r_{k-2} = q_k r_{k-1} + r_k$, and
   • $r_k = 0$ or $r_k$ is "smaller than" $r_{k-1}$. Here, absolute value is used to measure "size" if $a,b \in \ZZ$ or $\ZZ[i]$, or generally a Euclidean valuation is used to measure size.
4. If $r_k = 0$, then stop.
5. Otherwise, increase $k$ by $1$, go back to step 3.

The sequences $(q_k)$ and $(r_k)$ (for $k \geq 0$) are called sequences of quotients and remainders, obtained via the Euclidean algorithm. In fact, the sequences $(q_k)$ and $(r_k)$ are finite sequences, i.e., the Euclidean algorithm eventually terminates.