Gaussian integer factorization calculator

This Web application factors Gaussian integers as a product of Gaussian primes.

The Gaussian integers are complex numbers of the form a + bi, where both a and b are integer numbers and i is the square root of -1.

The factorization is unique, if we do not consider the order of the factors and associated primes. Each prime number has three associated prime numbers that are obtained by multiplying by a power of i. This issue disappears by selecting prime numbers a + bi such that a >= |b|.

Factoring Gaussian integers

An important concept needed for Gaussian integer factorization is the norm. This is defined as: N(a+bi) = a² + b².

The product of the norm of two Gaussian integers is equal to the norm of the products of these numbers as can be easily seen as follows:

N(a+bi) N(c+di) = (a² + b²) (c² + d²) = (ac)² + (bd)² + (ad)² + (bc)² = (ac)² - 2abcd + (bd)² + (ad)² + 2abcd + (bc)² = (ac-bd)² + (ad+bc)² = 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))

In the next to last expression we used the fact that i² = -1.

This means that the first step when trying to factor a Gaussian integer is to factor its norm into integer primes, so we get the norm of the factors of the original number.

The second step is to obtain the factors from the norm of the factor.

There are three cases:

1. The prime factor p of the norm is 2: This means that the factor of the Gaussian integer is 1+i or 1-i.
2. The prime factor p of the norm is multiple of 4 plus 3: this value cannot be expressed as a sum of two squares, so p is not a norm, but p² is. Since p² = p² + 0², and there is no prime norm that divides p², the number p + 0i is a Gaussian prime, and the repeated factor p must be discarded.
3. The prime factor p of the norm is multiple of 4 plus 1: this number can be expressed as a sum of two squares, by using the methods explained in the sum of squares page. If p = m² + n², then you can check whether m + ni or m − ni are divisors of the original Gaussian number.

Why does a number which is multiple of 4 plus 3 cannot be expressed as a sum of two squares? This is because the square of an even number is multiple of 4, and the square of an odd number is multiple of 4 plus 1. So we get:

• even² + even² = multiple of 4
• even² + odd² = multiple of 4 plus 1
• odd² + even² = multiple of 4 plus 1
• odd² + odd² = multiple of 4 plus 2

So under no circumstances a sum of two squares can be multiple of 4 plus 3.

Of course the first step is a lot more difficult than the second step. This is because we do not know efficient integer factorization for huge numbers.

Example: factor the Gaussian integer 440 − 55i

The norm is 440² + 55² = 196625 = 5 × 5 × 5 × 11 × 11 × 13

Both 5 and 13 are multiples of 4 plus 1 while 11 is a multiple of 4 plus 3. We can use the fact the 5 = 2² + 1² and 13 = 3² + 2²

Since 11 is a Gaussian prime, we can divide the original number by 11 and get 40 − 5i.

For the three factors of the norm equal to 5, we have to divide the result of the previous step 40 − 5i by 2 − i or 2 + i. So we get: 40 − 5i = (2 + i)² × (2 − i) × (3 − 2i)

For the factor 13 we have to divide the result of the previous step 3 − 2i by 3 + 2i or 3 − 2i. Of course only 3 − 2i divides 3 − 2i.

The complete factorization is: 440 − 55i = 11 × (2 + i)² × (2 − i) × (3 − 2i).

Expressions

In order to enter the imaginary part of a Gaussian integer you can use the symbol i, as in the next example: 3+4i.

You can also enter expressions that use the following operators, functions and parentheses:

• + for addition
• - for subtraction
• * for multiplication
• / for integer division (the dividend must be multiple of the divisor)
• % for modulus (remainder of the integer division)
• ^ for exponentiation (the exponent must be real and greater than or equal to zero).
• Ans: retrieves the last answer.
• n!: factorial (n must be real and greater than or equal to zero).
• n!! ... !: multiple factorial (n must be real and greater than or equal to zero). It is the product of n times n − k times n − 2k ... (all numbers greater than zero) where k is the number of exclamation marks. Example: 7!! = 7 × 5 × 3 × 1 = 105.
• p#: primorial (product of all primes less or equal than p).
• F(n): Fibonacci number F_n
• L(n): Lucas number L_n = F_n-1 + F_n+1
• P(n): Unrestricted Partition Number (number of decompositions of n into sums of integers without regard to order).
• Re(n): Real part of n.
• Im(n): Imaginary part of n.
• Norm(n): Norm of n, it equals Re(n)² + Im(n)².
• Gcd(m,n, ...): Greatest common divisor of these gaussian integers. Example: GCD(1+i, 2) = 1+i.
• Lcm(m,n, ...): Least common multiple of these gaussian integers. Example: LCM(1+i, 2, 4) = 4.
• Modinv(m,n): inverse of m modulo n, only valid when gcd(m,n)=1.
• Modpow(m,n,r): finds mⁿ modulo r (n must be real).
• Random(m,n): Gaussian integer random number whose real and imaginary parts are between the real and imaginary part of m and n respectively.
• isPrime(n): Checks whether the Gaussian integer is probable prime. In this case it returns −1, otherwise, zero.

You can use the prefix 0x for hexadecimal numbers, for example 0x38 is equal to 56.

Source code

You can download the source of the current program and the old sum polynomial factorization applet from GitHub. Notice that the source code is in C language and you need the Emscripten environment in order to generate JavaScript.

Written by Dario Alpern. Last updated 11 March 2023.