Preguntas sobre el dominio euclidiano y el algoritmo

Question

Si $R$ es un dominio euclidiano. Describe un algoritmo para calcular el máximo común divisor de dos elementos distintos de cero $a$ y $b$ de $R$ .

¿Será sólo el algoritmo euclidiano?

Además, ¿por qué el algoritmo termina y vuelve a la respuesta correcta?

Answer 1

Dominio euclidiano

La definición de un dominio euclidiano, $R$ , afirma que tiene una función euclidiana $N:R\setminus\{0\}\rightarrow\mathbb N$ para que el algoritmo termine en un número finito de pasos. Esta función debe satisfacer que para $x\in R$ y $d\in R\setminus\{0\}$ existe $q,r\in R$ tal que $$x=qd+r$$ donde $N(r)<N(d)$ o $r=0$ .

Algoritmo euclidiano

Para ver cómo esto asegura que el algoritmo termine digamos que debemos encontrar $\gcd(a,b)$ para algunos $a,b\in R$ con $N(a)>N(b)$ sólo escribe $$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$$ utilizando las propiedades de la función euclidiana en cada paso para que $$N(b)>N(r_1)>N(r_2)>...>N(r_i)>N(r_{i+1})>...$$ Dado que la secuencia dada anteriormente es estrictamente decreciente en $\mathbb N$ por cada paso del algoritmo acabaremos por quedarnos sin números naturales, por lo que nos veremos obligados a tener $r_n=0$ para algunos $r_n$ después de un máximo de $N(b)$ pasos. Entonces (ya que un dominio euclidiano es también un dominio de factorización única) $\gcd(a,b)=r_{n-1}$ es el "único" máximo común divisor de $a$ y $b$ hasta la multiplicación por una unidad.