Factorización de enteros gaussianos

  1. Alpertron
  2. Programas
  3. Factorización de enteros gaussianos
Acciones
Funciones

Esta aplicación Web factoriza enteros gaussianos como un producto de primos gaussianos.

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

La factorizació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 gaussianos

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

El producto de la norma de dos enteros gaussianos 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 gaussianos, 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 gaussiano 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 gaussiano, 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 m − ni son divisores del número gaussiano 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:

  • par2 + par2 = múltiplo de 4
  • par2 + impar2 = múltiplo de 4 más 1
  • impar2 + par2 = múltiplo de 4 más 1
  • impar2 + impar2 = múltiplo de 4 más 2

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 gaussiano 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 gaussiano, podemos dividir el número original por 11 y hallamos el cociente 40 − 5i.

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

Para el factor 13 deberemos dividir el resultado del paso anterior 3 − 2i por 3 + 2i o por 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 gaussiano 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:

  • + para suma.
  • - para resta.
  • * para multiplicación.
  • / para división entera.
  • % para módulo (resto de la división).
  • ^ para exponenciación (el exponente debe ser real y mayor o igual que cero).
  • Ans: obtiene la última respuesta.
  • n!: factorial (n debe ser real y mayor o igual que cero).
  • n!! ... !: factorial múltiple (n debe ser real y mayor o igual que cero). Es el producto de n por n − k por n − 2k ... (todos los números son mayores que cero) donde k es la cantidad de signos de exclamación. Ejemplo: 7!! = 7 × 5 × 3 × 1 = 105.
  • p#: primorial (producto de todos los primos menores o iguales que p).
  • F(n): número de Fibonacci Fn.
  • L(n): número de Lucas Ln = Fn-1 + Fn+1.
  • P(n): particiones irrestrictas (cantidad de descomposiciones de n en sumas de numeros enteros sin tener en cuenta el orden).
  • Re(n): parte real de n.
  • Im(n): parte imaginaria de n.
  • Norm(n): norma de n, equivale a Re(n)2 + Im(n)2.
  • Gcd(m,n, ...): máximo común divisor de estos números enteros gausianos. Ejemplo: GCD(1+i, 2) = 1+i.
  • Lcm(m,n, ...): mínimo común múltiplo de estos números enteros gausianos. Ejemplo: LCM(1+i, 2, 4) = 4.
  • Modinv(m,n): inverso del valor m módulo n, sólo válido si gcd(m,n)=1.
  • Modpow(m,n,r): calcula mn módulo r (n debe ser real).
  • Random(m,n): número gausiano aleatorio cuyos valores real e imaginario se encuentra entre los valores real e imaginario de m y n respectivamente.
  • isPrime(n): Verifica si el entero gausiano es primo probable. En este caso retorna −1, en caso contrario, cero.

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 gaussianos 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 8 de junio de 2023.