Factorización de enteros gausianos

Los enteros gausianos son números complejos que tienen la forma a + bi, donde a y b son números enteros en la recta real.

Este applet es capaz de factorizar un entero gausiano como un producto de primos gausianos. Esta descomposición es única, si no consideramos el orden de los factores y los primos asociados. Estos conjuntos de primos asociados se obtienen multiplicando un primo por una potencia de i (por eso cada número primo tiene tres asociados). Para eliminar este problema, tomamos el primo tal que a >= |b|.

Cómo factorizar enteros gausianos

Un comcepto importante necesario para la factorización de enteros gausianos es la norma. Ésta se define como: N(a+bi) = a2 + b2.

El producto de la norma de dos enteros gausianos es igual a la norma del producto de estos números como se muestra a continuación:

N(a+bi) N(c+di) = (a2 + b2) (c2 + d2) = (ac)2 + (bd)2 + (ad)2 + (bc)2 = (ac)2 - 2abcd + (bd)2 + (ad)2 + 2abcd + (bc)2 = (ac-bd)2 + (ad+bc)2 = N((ac-bd)+(ad+bc)i) = N(a(c+di) + b(-d+ci)) = N(a(c+di) + bi(c+di)) = N((a+bi) (c+di))

En la penúltima expresión nos valemos de la propiedad i2 = -1.

Esto significa que como primer paso para factorizar números gausianos, debemos hallar los factores primos de su norma, así obtenemos las normas de los factores del número original.

El segundo paso consiste en obtener los factores a partir de las normas halladas.

Existen tres casos:

  1. El factor primo p de la norma es 2: en este caso los factores primos del entero gausiano pueden ser 1+i o 1-i (hay que probar cuál divide al número).
  2. El factor primo p de la norma es múltiplo de 4 más 3: este valor no se puede expresar como suma de dos cuadrados, así que p no es una norma, pero p2 sí lo es. Como p2 = p2 + 02, y no existe una norma prima que divida p2, el número p + 0i es un primo gausiano, y deberemos descartar el factor repetido p.
  3. El factor primo p de la norma es múltiplo de 4 más 1: este número se puede expresar como suma de dos cuadrados utilizando los métodos explicados en la página de suma de cuadrados. Si p = m2 + n2, entonces deberemos verificar si m + ni o mni son divisores del número gausiano original.

¿Por qué un número que es múltiplo de 4 más 3 no puede expresarse como suma de cuadrados? Esto se debe a que el cuadrado de un número par es múltiplo de 4 y el cuadrado de un número impar es múltiplo de 4 más 1. De esta manera obtenemos:

Así que bajo ninguna circunstancia una suma de dos cuadrados puede ser múltiplo de 4 más 3.

Por supuesto el primer paso es mucho más complicado que el segundo. Esto es porque no conocemos métodos eficientes de factorización de números enteros.

Ejemplo: factorizar el entero gausiano 440 − 55i

La norma es 4402 + 552 = 196625 = 5 × 5 × 5 × 11 × 11 × 13

Tanto 5 como 13 son múltiplos de 4 más 1 mientras que 11 es múltiplo de 4 más 3. Podemos valernos de 5 = 22 + 12 y 13 = 32 + 22

Como 11 es un primo gausiano, podemos dividir el número original por 11 y hallamos el cociente 44 − 5i.

Para los tres factores de la norma iguales a 5, deberemos dividir el resultado del paso anterior 44 − 5i por 2−i o 2+i. Obtenemos: 44 − 5i = (2+i)2 × (2-i) × (3 − 2i)

Para el factor 13 deberemos dividir el resultado del paso antrerior 3 − 2i por 3 + 2i ó 3 − 2i. Por supuesto solo 3 − 2i divide a 3 − 2i.

La factorización completa es: 440 − 55i = 11 × (2 + i)2 × (2 − i) × (3 − 2i).

Expresiones

Para ingresar la parte imaginaria de un entero gausiano podrá utilizar el símbolo i, como por ejemplo en 3+4i.

Además puede entrar expresiones que usen los siguientes operadores, funciones y paréntesis:

Puedes usar el prefijo 0x para números hexadecimales, por ejemplo 0x38 es igual a 56.

Código fuente

Puedes bajar el código fuente del programa actual y del viejo applet de factorización de enteros gausianos desde GitHub. El código fuente está escrito en lenguaje C, por lo que es necesario Emscripten para generar Javascript.

Escrito por Dario Alpern. Actualizado el 24 de febrero de 2017.