# Euclidean Domain and algorithm questions

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?

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.