Question

State and prove the Euclidean algorithm for finding the gcd of two elements of a Euclidean domain.

Short answer

Euclidean algorithm for finding the gcd of two elements of a Euclidean domain is proved.

Step-by-step solution

Statement of Euclidean algorithm for finding the gcd of two elements of a Euclidean domain

If D is a Euclidean domain and the degree function has arranged set that satisfies the well-ordered axiom, then each sequence of divisions with reminders eventually stops:

$\begin{array}{l}\mathbf{a}\mathbf{=}\mathbf{b}{\mathbf{q}}_{\mathbf{1}}\mathbf{+}{\mathbf{r}}_{\mathbf{1}}\\ \mathbf{b}\mathbf{=}{\mathbf{r}}_{\mathbf{1}}{\mathbf{q}}_{\mathbf{2}}\mathbf{+}{\mathbf{r}}_{\mathbf{2}}\\ {\mathbf{r}}_{\mathbf{1}}\mathbf{=}{\mathbf{r}}_{\mathbf{1}}{\mathbf{q}}_{\mathbf{2}}\mathbf{+}{\mathbf{r}}_{\mathbf{3}}\\ \mathbf{.}\\ \mathbf{.}\\ {\mathbf{r}}_{\mathbf{k}}\mathbf{=}{\mathbf{r}}_{\mathbf{k}\mathbf{+}\mathbf{1}}{\mathbf{q}}_{\mathbf{k}\mathbf{+}\mathbf{2}}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{\text{STOP}}\end{array}$

And the last reminder ${\mathit{r}}_{\mathbf{k}\mathbf{+}\mathbf{1}}$is a common divisor of the greatest degree.

Proof of Euclidean algorithm for finding the gcd of two elements of a Euclidean domain

First, we prove that each of the sequence of divisions with reminders eventually stops. Given one of them, consider the set of all degrees of all the reminders:

$S=\{\mathrm{deg}\left(r_1\right),\mathrm{deg}\left(r_2\right),\mathrm{deg}\left(r_3\right),\mathrm{...}\}$

Since $\mathrm{deg}\left(r_1\right)>\mathrm{deg}\left(r_2\right)>\mathrm{deg}\left(r_3\right)>\mathrm{....},$the well-ordered axiom says there is the smallest element of $S$, which is the degree of the last reminder!

To see that $r_{k+1}$is a common divisor of $a$and localid="1654667697307" $b$, we work our way back up Euclid’s algorithm, starting with the last line. Namely:

$r_k=r_{k+1}{q}_{k+2}$

Shows that$r_{k+1}$divides localid="1654667780402" $r_k$

Now,

$\begin{array}{c}{r}_{k-1}=r_k{q}_{k+1}+r_{k+1}\\ =\left(r_{k+1}{q}_{k+2}\right)q_{k+1}+r_{k+1}\\ =r_{k+1}(q_{k+2}{q}_{k+1}+1)\end{array}$

Which shows that $r_{k+1}$divides $r_{k-1}$.

Here we see $r_{k+1}$ that divides all the remainders, and it divides localid="1654668313660" $a$and localid="1654668318572" $b$as well, so that $r_{k+1}$is a common divisor of $a$and $b$.

To prove that $r_{k+1}$has the greatest degree among all the common divisors, we use Euclid’s algorithm.

The first equation:

$a=b{q}_1+r$

Can be written as

$r_1=a+(-q_1)b$

Here,$r_1$ is a linear combination of localid="1654668103944" $a$and localid="1654668114168" $b$

Now,

$r_2=b+(-q_2)r_1=b+(-q_2)(a+(-q_1)b)=(-q_2)a+(1+q_1{q}_2)b$

So, $r_2$is a linear combination of $a$and $b$.

Continue in this manner, we get

$r_{k+1}=ua+vb$

For some pair of elements $u,v\in D$

Now, if localid="1654668376842" $d$is any common divisor of localid="1654668413098" $a$and localid="1654668403766" $b$, then

$a=dq$and $b=dq\text{'}$So,

$r_{k+1}=udq+vdq\text{'}=d(uq+vq\text{'})$

So,$d$divides $r_{k+1}$

Also, $\mathrm{deg}\left(p\right)+\mathrm{deg}(uq+vq\text{'})=\mathrm{deg}\left(r_{k+1}\right)$

So $\mathrm{deg}\left(d\right)\le \mathrm{deg}\left(r_{k+1}\right)$.

Thus, $r_{k+1}$has the possible greatest degree of any common divisor of$a$and $b$.

Hence$d$is the greatest common divisor oflocalid="1654668637146" $a$and$b$.