5 votos

Un algoritmo para enteros gaussianos.

Pregunta : Vamos A $i^2=-1$. Si en un par $(a+bi, c+di) (a,b,c,d\in\mathbb Z, a\not\equiv b, c\not\equiv d\ \text{(mod 2)})$ tal que $a+bi$ $c+di$ son primos relativos , entonces podemos decir que la repetición de la siguiente operación conduce a $(1,1)$ en un número finito de pasos?

Supongamos que $a+bi$ $c+di$ son primos relativos si y sólo si $a+bi$ $c+di$ no tienen ningún divisor común a excepción de $\pm 1,\pm i$.

Operación : Si en un par $(a+bi, c+di)$ (podemos suponer que $N(a+bi)\le N(c+di)$ donde $N(a+bi)=a^2+b^2$), el siguiente par se define como $(a+bi, (c+di)+\epsilon (1+i)(a+bi))$ con una elección adecuada de $\epsilon=\pm 1,\pm i$.

Ejemplo : tomando nota de que $3+2i$ $4+i$ son relativamente primos ya que cada uno de ellos es un número primo, sabemos que el par $(3+2i,4+i)$ cumple la condición anterior. Tomando nota de que $N(3+2i)\le N(4+i)$, $$\begin{align} (3+2i,4+i) & \rightarrow (3+2i,-1+2i)\ \ \ \ (\because \ \ (4+i)+(+i)(1+i)(3+2i)=-1+2i)\\ & \rightarrow (2-i, -1+2i)\ \ \ \ (\because \ \ (3+2i)+(+i)(1+i)(-1+2i)=2-i)\\ & \rightarrow (2-i,-i)\ \ \ \ (\because \ \ (-1+2i)+(-i)(1+i)(2-i)=-i)\\ & \rightarrow (1,-i)\ \ \ \ (\because \ \ (2-i)+(-1)(1+i)(-i)=1)\\ & \rightarrow (1,1)\ \ \ \ (\because \ \ (-i)+(+1)(1+i)(+1)=1). \end{align}$$

Motivación : he estado buscando un algoritmo similar para los enteros de Gauss $\mathbb Z[i]$ como Algoritmo de Euclides para racionales enteros $\mathbb Z$. Entonces, he llegado a la operación anterior. Sin embargo, estoy en la dificultad para demostrar o refutar que repetir la operación conduce a $(1,1)$ para cualquier pareja. Alguien puede ayudar?

Edit 1 : Como Gerry Myerson señalado, el algoritmo de Euclides funciona bien en los enteros de Gauss.

Edit 2 : me parece que si podemos probar el siguiente lema, entonces podemos decir que la repetición de la operación conduce a $(1,1)$ en un número finito de pasos. Sin embargo, estoy en la dificultad para demostrar el lema. Alguien puede ayudar?

Lema : Si en un par $(a+bi, c+di) (a,b,c,d\in\mathbb Z, a\not\equiv b, c\not\equiv d\ \text{(mod 2)})$ tal que $a+bi$ $c+di$ son relativamente primos con $N(a+bi)\le N(c+di)$ es dado , entonces podemos obtener $$N(c+di+\epsilon (1+i)(a+bi))\lt N(c+di)$$ con una elección adecuada de $\epsilon=\pm 1,\pm i$.

3voto

Ameer Deen Puntos 2903

Tenemos algunos de los lemas antes de concentrarse en lo que importa. Vamos a probar que la norma es siempre decreciente y es siempre distinto de cero en su situación. Esto implicaría su reclamo si podemos garantizar que el algoritmo nunca se "ahoga", es decir, que la regla de la igualdad de parte. Esto se puede hacer con informaciones adicionales.

Lema. Deje $t=1+i$. Para todos los números complejos $m,n$ es posible encontrar una combinación lineal $\alpha$ $\varepsilon t$ tal que $$N(n-\alpha m)\leqslant N(m).$$

Para demostrar el lema, imaginar el plano complejo, el número de $m$ y el número de $n$, posiblemente muy lejos de $m$. Escribir las combinaciones lineales de los números de $mt, mit, -mt, -mit$. Cubrir el plano complejo con los cuadrados de los lados $|m|\sqrt{2}$. Por el principio del palomar, $n$ es en la mayoría de las $|m|$ desde otro número complejo, digamos, $\alpha m$. Esto implica $N(n-\alpha m)\leqslant N(m)$, como queríamos.


Lema. Si $a$ $b$ son relativamente primos, $N(a-\alpha b)\lt N(b)$.

Supongamos $N(a-\alpha b)=N(b)$. Siguiendo con la idea de que el primer lema, se sigue que $a$ está en el centro de un cuadrado de la cobertura que hemos creado. Ahora, considere la cobertura de todos los gaussiano múltiplos de $b$. Contiene todos los centros y todos los vértices, y, a continuación, $a=kb$, contradicción.


Lema. La norma $N(a-\alpha b)$ es siempre distinto de cero.

Supongo que es cero. Por lo tanto, $a=\alpha b$, por lo que no son primos relativos, la contradicción.


Por lo tanto, hemos probado que la norma está disminuyendo y es siempre distinto de cero. Esto implica que el algoritmo siempre termina en $(1,1)$.

i-Ciencias.com

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.

Powered by:

X