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?
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$ .
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.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
