¿Cómo calcular el GCD de los enteros de Gauss?

Question

Dejemos que $\mathbb Z [i] =\{a+bi: a,b \in \mathbb Z\}$ .

¿Cuál es el gcd de $11+7i$ et $18-i$ en $\mathbb Z [i]$ ?

Answer 1

Un enfoque general excelente es utilizar una versión gaussiana del algoritmo euclidiano. Al final de este artículo se ofrece un cálculo con este método.
Pero con enteros gaussianos "pequeños", otros enfoques pueden funcionar rápidamente.

Por ejemplo, podemos buscar factores comunes utilizando las normas. Obsérvese que $\|11+7i\|=170$ et $\|18-i\|=325$ .

Cualquier divisor común de nuestros números debe dividir al máximo común divisor ordinario de sus normas, por lo que debe dividir $5$ . Sabemos que en los enteros de Gauss, $5$ tiene la factorización primaria $5=(2+i)(2-i)$ . Veamos si $2+i$ divide nuestros dos números.

Calcula: $$\frac{11+7i}{2+i}=\frac{(11+7i)(2-i)}{(2+i)(2-i)}=\frac{29+3i}{5}.$$ Concluimos que $2+i$ no divide $11+7i$ . (De ello se deduce que $2-i$ debe dividir $11+7i$ pero no lo necesitaremos).

Ahora vamos a comprobar si este divisor primo $2-i$ de $11+7i$ divide $18-i$ : $$\frac{18-i}{2-i}=\frac{(18-i)(2+i)}{(2-i)(2+i)}=\frac{37+16i}{5}.$$ Así que $2-i$ no divide $18-i$ . Por lo tanto, nada más que una unidad divide nuestros dos números.

Concluimos que $1$ es el máximo común divisor de $11+7i$ et $18-i$ . (También lo son sus asociados $-1$ et $\pm i$ .)

Comentario: Podríamos haber ahorrado tiempo. Por ejemplo, cualquier divisor común de $11+7i$ et $18-i$ debe dividir cualquier combinación lineal de ellos, como $1\cdot(11+7i)+7\cdot (18-i)$ . Esto es $137$ . Así que cualquier divisor común debe dividir la norma de $11+7i$ que es $170$ y también debe dividir $137$ . Estos números son relativamente primos en el sentido ordinario, por lo que también lo son en el sentido gaussiano. Podríamos haber prescindido de las divisiones por $2+i$ et $2-i$ por completo.

El algoritmo euclidiano: Nos limitamos a examinar nuestro problema particular, que es demasiado pequeño para ilustrar completamente el proceso. La idea es imitar el proceso ordinario de división con resto. Dividir $18-i$ el número con mayor norma, por $11+7i$ . Tras un pequeño cálculo, esto se simplifica a $\dfrac{191-137i}{170}$ . Ahora escoge el entero gaussiano más cercano a esto. Es $1-i$ y es nuestro candidato a "cociente".

Calcular $(18-i)-(11+7i)(1-i)$ : obtenemos $3i$ . Así, $$18-i=(11+7i)(1-i) +3i.$$ Obsérvese que, como en el caso de los enteros ordinarios, el gcd de $18-i$ et $11+7i$ es el mismo que el gcd de $11+7i$ y el "resto" $3i$ . Es obvio que este gcd es $1$ . Pero si decidimos no darnos cuenta, podemos volver a aplicar el procedimiento de división de forma mecánica. Tenemos $\dfrac{11+7i}{3i}=(7-11i)/3$ . El entero gaussiano más cercano es $2-4i$ . Así que $$11+7i=(3i)(2-4i) -1 +i.$$ Así, nuestro gcd es el mismo que el gcd de $3i$ et $-1+i$ . Continuemos. Calcular $3i/(-1+i)$ , encuentra el entero gaussiano más cercano. Hay varios, entre ellos $1-i$ . Obtenemos $3i=(-1+i)(1-i)+i$ . El siguiente resto será $0$ desde $i$ es una unidad. Nuestro cálculo ha dado $i$ como un gcd. No hay que pensar en absoluto.

Una cosa buena del enfoque del Algoritmo Euclidiano es que no tenemos que hacer ninguna factorización (para números enteros grandes, eso es difícil). Los cálculos no parecen muy divertidos, y no lo son, pero es el tipo de cosas que les gustan a los ordenadores.

Answer 2

HINT $\ $ Modular el gcd: $\ 11\: =\: {-}7\ i\ $ et $\ 18\: =\: i\:,\ $ por lo tanto

$$ 11\ =\ (11-18)\ i\ =\ (-7\ i\:-\:i)\ i\ =\ 8\ \ \Rightarrow\ \ 3\: =\: 0\ \ \Rightarrow\ \ i\: =\: 6\cdot 3\: =\: 0\ \ \Rightarrow\ \ 1\: =\: 0$$