How to Factor Integers Over the Gaussian Primes


Gaussian Factorization Calculator

Enter a positive integer with at most 15 digits:

 

In elementary school we learn how to factor integers into smaller integers until we reach numbers that are indivisible, a process known as prime factorization. Integers that cannot be factored into smaller integers are known as primes. For example, the prime factorization of 30 is 2·3·5, since 2, 3, and 5 are prime.

However, if we expand the space of factorization to include Gaussian integers, complex numbers a + bi where a and b are integers, then we can often decompose integers even further. For instance, 5 is a prime number among the integers, but it can be factored into (2+i)(2-i) over the Gaussian integers. The indivisible numbers among the Gaussian integers are known as Gaussian primes. 2+i and 2-i are Gaussian primes.

Factorization over Gaussian primes is unique up to multiplication by units, of which there are four: 1, -1, i, -i. This means that there are several alternative, but essentially equivalent factorizations of numbers. For example, 5 can be expressed as either

(2+i)(2-i), (-2-i)(-2+i), (-1-2i)(-1+2i), or (1+2i)(1-2i).

This is analogous to the fact that 77 can be expressed as either (7)(11) or (-7)(-11) in the integers; 1 and -1 are the two units among the integers

You can use the calculator at left to factor any integer into Gaussian primes. If you want to factor Gaussian integers into Gaussian primes, use this calculator instead.

How to Find the Gaussian Prime Factorization of an Integer

The first step is to decompose the integers into its prime integer factors. For example, if we want to find the Gaussian prime factorization of 127908, we first break the number down into

127908 = 2·2·3·3·11·17·19

The next step is to separate the prime factors into two groups: those of the form 4k + 3, and those not of the form 4k + 3. In other words, identify which prime integers are equivalent to 3 modulo 4.

For example, if we group the prime factors of 127908, we obtain the two sets {3, 3, 11, 19} and {2, 2, 17}

Now, take the integers in the second group, those that are not of the form 4k + 3. For each integer n in this set, you can find two smaller integers a and b such that a² + b² = n. Observe:

2 = 1² + 1² and 17 = 1² + 4².

This means that n can be factored as (a + bi)(a - bi) over the Gaussian primes. (Or equivalently as (b + ai)(b - ai); it is a matter of preference.)

For integers in the first set, those of the form 4k +3, there is no further factorization. They cannot be expressed as the sum of two squares, thus cannot be factored as (a + bi)(a - bi).

Therefore, the Gaussian factorization of 127908 is

127908 = (1+i)(1-i)(1+i)(1-i)(3)(3)(11)(1+4i)(1-4i)(19)

You can also use the Gaussian Prime Calculator above.


© Had2Know 2010