Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
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.
