1
$\begingroup$

If $R$ is a Euclidean Domain. Describe an algorithm for computing the greatest common divisor of two non-zero elements $a$ and $b$ of $R$.

Would this just be the Euclidean algorithm?

Also why does the algorithm terminate and return to the correct answer?

$\endgroup$
1
0
$\begingroup$

Euclidean Domain

The definition of a Euclidean Domain, $R$, asserts that you have a Euclidean function $N:R\setminus\{0\}\rightarrow\mathbb N$ so that the algorithm will finish in finitely many steps. This function must satisfy that for $x\in R$ and $d\in R\setminus\{0\}$ there exists $q,r\in R$ such that $$ x=qd+r $$ where either $N(r)<N(d)$ or $r=0$.

Euclidean Algorithm

To see how this ensures the algorithm to terminate let us say we are to find $\gcd(a,b)$ for some $a,b\in R$ with $N(a)>N(b)$ just write $$ a=q_1 b+r_1\\ b=q_2 r_1+r_2\\ r_1=q_3 r_2+r_3\\ \vdots\\ r_{i-2}=q_i r_{i-1}+r_i $$ using the properties of the Euclidean function in each step so that $$ N(b)>N(r_1)>N(r_2)>...>N(r_i)>N(r_{i+1})>... $$ Since the sequence given above is stricly decreasing in $\mathbb N$ by each step in the algorithm we will eventually run out of natural numbers so that we are forced to have $r_n=0$ for some $r_n$ after at most $N(b)$ steps. Then (since a Euclidean Domain is also a Unique Factorization Domain) $\gcd(a,b)=r_{n-1}$ is the 'unique' greatest common divisor of $a$ and $b$ up to multiplication by a unit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.