Skip to main content

Section 6.3 Factorization of Gauss integers

Example 6.3 showed that the ring of Gaussian integers
\begin{equation*} \mathbb Z[i] = \{a + bi : a, b \in \mathbb Z\} \end{equation*}
is a Euclidean domain. By Corollary 6.13, it is therefore a unique factorization domain, so any Gaussian integer can be factored into irreducible Gaussian integers from a distinguished set, which is unique up to reordering. In this section, we look at the factorization of Gaussian integers in more detail.
We will first describe the distinguished irreducibles we will use for Gaussian integers. The units in the ring of Gaussian integers are \(\pm 1\) and \(\pm i\text{.}\) Multiplication by these units corresponds to rotation by \(0\text{,}\) \(90\text{,}\) \(180\text{,}\) or \(270\) degrees in the complex plane. To choose one representative from each class of associates, we choose one right angle wedge. More precisely, our distinguished irreducibles will be the irreducible elements \(a + bi \in \mathbb Z[i]\) such that \(a \geq b\) and \(a \gt -b\text{.}\)
Our main tool will be to compare how factorization of Gaussian integers compares with factorization of integers.

Proof.
Suppose that we factor \(p\) as \(p = u \alpha_1 \cdots \alpha_n\text{,}\) where \(u\) is a unit and \(\alpha_1, \ldots, \alpha_n\) are distinuished irredicubles. By taking the valuation of both sides, we have:
\begin{equation*} \nu(p) = p^2 = \nu(u) \nu(\alpha_1) \cdots \nu(\alpha_n), \end{equation*}
where \(\nu(u) = 1\) and \(\nu(\alpha_1), \ldots, \nu(\alpha_n)\) are positive integers. Since the Gaussian integers \(\alpha_1, \ldots, \alpha_n\) are irreducible, they are not units, so \(\nu(\alpha_i) \neq 1\) for all \(i\text{.}\) Therefore, by the unique factorization of integers, either \(n=1\) and so \(p = \alpha_1\) is irreducible or \(n=2\) and \(\nu(\alpha_1) = \nu(\alpha_2) = p\text{.}\) In the latter case, \(p = \nu(\alpha) = \alpha_1 \overline \alpha_1\text{,}\) which is the second case from the statement.

Proof.
Let \(p\) be a prime integer with \(p \equiv 3 \pmod 4\text{.}\) Suppose, for contradiction that \(p\) is not irreducible. Then by Lemma 6.16, \(p = \alpha \overline \alpha\text{.}\) If we write \(\alpha = a + bi\text{,}\) where \(a,b \in \mathbb Z\text{,}\) then \(p = \alpha \overline \alpha = a^2 + b^2\text{.}\) Then, both \(a^2\) and \(b^2\) are congruent to either \(0\) or \(1\) modulo \(4\text{,}\) so \(a^2 + b^2\) is congruent to either \(0\text{,}\) \(1\text{,}\) or \(2\text{.}\) But, \(p \equiv 3 \pmod 4\text{,}\) which is a contradiction, so that means that \(p\) must be irreducible.

Proof.
Write \(p = 4k+1\text{.}\) By Fermat’s Little Theorem 3.7, every element of \(\mathbb Z_{p}\) is a zero of the polynomial \(x^p - x\text{,}\) which can be factored as \(x^p - x = x(x^{2k} - 1)(x^{2k}+1)\text{.}\) There are \(p=4k+1\) elements in \(\mathbb Z_{p}\) and only \(2k+1\) of them can be zeros of the degree \(2k+1\) polynomial \(x(x^{2k}-1)\) and so there exists a \(b \in \mathbb Z_p\) which is a zero of \(x^{2k}+1\text{.}\) Therefore, \(b^{2k}+1 = 0\text{.}\) Let \(a = b^k\) and then \(a^2 = b^{2k} = -1\text{,}\) so any representative of \(a\) in \(\mathbb Z\) satisfies \(a^2 \equiv -1 \pmod p\text{.}\)

Example 6.19.

If \(p = 29\text{,}\) then \(p \equiv 1 \pmod 4\) because \(29 = 4 \cdot 7 + 1\text{,}\) so there exsists a square root of \(-1\) in \(\mathbb Z_p\) by Lemma 6.18. We could try squaring all integers from 1 to 28 and computing the remainder modulo 29. However, as in the proof, we could try to find \(b\) such that \(b^{2 \cdot 7} = b^{14} \neq 1\text{.}\) As it happens, \(2\) works:
\begin{equation*} 2^{14} = 16384 \equiv 28 \pmod {29}\text{.} \end{equation*}
Then,
\begin{equation*} a = 2^7 \equiv 12 \pmod {29} \end{equation*}
is a square root of \(-1\text{.}\)

Proof.
First suppose that \(p=2\text{.}\) Then \(2 = (1+i)(1-i)\text{,}\) and \(\alpha=1+i\) is an irreducible Gaussian integer because \(\nu(1+i) = 2\text{,}\) which is prime integer.
Second suppose that \(p = 4k + 1\) with \(k\) an integer. By Lemma 6.18, there exists an integer \(a\) such that \(a^2 \equiv -1 \pmod p\text{.}\) Let \(\beta\) be the Gaussian integer \(a + i\) and then
\begin{equation*} \beta \overline \beta = (a + i) (a - i) = a^2 + 1 = pm, \end{equation*}
for some integer \(m\text{.}\) If \(p\) were irreducible, then \(p\) would divide either \(\beta\) or \(\overline \beta\text{,}\) which it doesn’t since they both have 1 in their imaginary part. Therefore, \(p\) is not irreducible, so by Lemma 6.16, \(p = \alpha \overline \alpha\) for some distinguished irreducible \(\alpha\) in the ring of Gaussian integers. (In fact, \(\alpha\) is a greatest common divisor of \(\beta\) and \(p\text{.}\))

Example 6.21.

We continue Example 6.19 with \(p = 29\text{.}\) From that example, we know that \(12^2 \equiv -1 \pmod{29}\) and so:
\begin{equation*} (12+i) (12-i) = 12^2 + 1 = 145 = 29 \cdot 5\text{.} \end{equation*}
Since the Gaussian integers are a unique factorization domain, the factorization of \(145\) must have an irreducible dividing both \(29\) and \(12+i\text{.}\) It is not so easy to find the greatest common divisor of \(29\) and \(12+i\) directly, but we can work the other direction, using the sum of squares \(29 = 5^2 + 2^2 = (5+2i)(5-2i)\) and check that \(5-2i\) divides \(12+i\text{.}\) In fact, a factorization of \(145\) into irreducible Gaussian integers is
\begin{equation*} 145 = (5 - 2i)(5+2i)(2+i)(2-i)\text{,} \end{equation*}
where the factorization into irreducible integers \(29 \cdot 5\) is formed by grouping the first two and last two, and \(12+i = (5-2i)(2+i)\text{,}\) \(12-i = (5+2i)(2-i)\text{.}\)

Proof.
Suppose that \(\alpha\) is distinguished irreducible. Then factor its valuation \(\nu(\alpha)\) into prime integers:
\begin{equation*} \nu(\alpha) = \alpha \overline \alpha = p_1 \cdots p_n \end{equation*}
Since \(\alpha\) is an irreducible Gaussian integer, by Euclid’s Lemma, \(\alpha\) divides one of the integers \(p_1, \ldots, p_n\) (in the ring of Gaussian integers). Suppose that \(\alpha\) divides \(p_i\text{.}\) Then, its complex conjugate \(\overline \alpha\) divides \(\overline p_i = p_i\text{,}\) so the integer \(\nu(\alpha) = \alpha \overline \alpha\) divides \(p_i^2\text{.}\)
There are two possibilities. Either \(\nu(\alpha) = p_i\text{,}\) which is the first possibility from the statement or \(\nu(\alpha) = p_i^2\text{.}\) In the latter case, unique factorization means that \(\alpha\) equals \(p_i\text{,}\) which is the second possibility from the statement. Therefore, any irreducible element in \(\mathbb Z[i]\) falls into one of these two categories.

Proof.
First, suppose that \(n=p_1 \cdots p_k q_1^2 \cdots q_l^2\text{,}\) where \(p_i\) is either \(2\) or congruent to \(1\) modulo \(4\text{.}\) By Theorem 6.20, each \(p_i\) factors into Gaussian integers \(\alpha_i \overline \alpha_i\text{.}\) Then, we can rearrange:
\begin{align*} n \amp= p_1 \cdots p_k q_1^2 \cdots q_l^2\\ \amp= \alpha_1 \overline \alpha_1 \cdots \alpha_k \overline \alpha_k q_1 ^2 \cdots q_l^2\\ \amp= (\alpha_1 \cdots \alpha_k q_1 \cdots q_l)\overline{(\alpha_1 \cdots \alpha_k q_1 \cdots q_l)} = \beta \overline \beta \end{align*}
where \(\beta = \alpha_1 \cdots \alpha_k q_1 \cdots q_l\text{.}\) If we write \(\beta = a+ bi\text{,}\) then \(\beta \overline \beta = a^2 + b^2 = n\) and so \(n\) can be written as the sum of two squares.
Second, suppose that \(n = a^2 + b^2\) where \(a\) and \(b\) are integers. Then \(n = \beta \overline \beta\) where \(\beta = a + bi\text{.}\) We can factor \(\beta\) into distinguished irreducibles in the Gaussian integers. By Lemma 6.22, each of these distinguished irreducibles is either a Gaussian integer with prime valuation or a prime integer. So, we write \(\beta = u \alpha_1 \cdots \alpha_k q_1 \ldots q_l\text{,}\) where \(u\) is a unit, \(q_i\) is a prime integer, and \(\nu(\alpha_i) = p_i\) is a prime integer with \(p_i = 2\) or \(p_i \equiv 1 \pmod 4\text{.}\) But then,
\begin{equation*} n = \beta \overline \beta = \nu(\beta) = \nu(u) \nu(\alpha_1) \cdots \nu(\alpha_k) \nu(q_1) \cdots \nu(q_l) = p_1 \cdots p_k q_1^2 \cdots q_l^2, \end{equation*}
which is the claimed form of \(n\text{.}\)

Example 6.24.

The integer \(1001 = 7 \cdot 11 \cdot 13\) is not a sum of two squares because the primes \(7\) and \(11\) are both congruent to \(3 \pmod 4\) and each only appear once in the prime factorization.

Example 6.25.

The integer \(1010 = 2 \cdot 5 \cdot 101\) is a sum of squares because all of its prime factors are either \(2\) or congruent to \(1 \pmod 4\text{.}\) We can also use the proof of Theorem 6.23 to find the two squares. First, we write each of the prime factors as a sum of two squares:
\begin{align*} 2 &= 1^2 + 1^2\\ 5 &= 2^2 + 1^2\\ 101 &= 10^2 + 1^2\text{.} \end{align*}
Second, we then factor \(1010\) into irreducible Gaussian integers:
\begin{equation*} 1010 = 2 \cdot 5 \cdot 101 = (1+i)(1-i)(2+i)(2-i)(10+i)(10-i)\text{.} \end{equation*}
To get a Gaussian integer with valuation \(1010\text{,}\) we take one of each of the complex conjugate pairs, so:
\begin{equation*} (1+i)(2+i)(10+i) = 7 + 31i\text{.} \end{equation*}
Then you can verify that \(7^2+31^2 = 1010\text{.}\)
In fact, we can find another expression of \(1010\) as a sum of two squares by making a different choice of factors from each pair, such as:
\begin{align*} (1+i)(2+i)(10-i) &= 13 + 29i & 13^2 + 29^2 &= 1010\\ (1+i)(2-i)(10+i) &= 29 + 13i & 29^2 + 13^2 &= 1010\\ (1+i)(2-i)(10-i) &= 31 + 7i & 31^2 + 7^2 &= 1010\\ (1-i)(2+i)(10+i) &= 31 - 7i & 31^2 + (-7)^2 &= 1010\\ (1-i)(2+i)(10-i) &= 29 - 13i & 29^2 + (-13)^2 &=1010\\ (1-i)(2-i)(10+i) &= 13 -29i & 13^2 + (-29)^2 &=1010\\ (1-i)(2-i)(10-i) &= 7 - 31i & 7^2 + (-31)^2 &=1010\text{.} \end{align*}
Some of these expressions as a sum of squares just differ by reversing the order of the two numbers or negating inside of the square, so there are only two essentially different ways of writing \(1010\) as the sum of two squares. Is there any way we could have known there were only two sums and found them without doing all the multiplications?
Yes, because taking the complex conjugate of all the factors just results in the complex complex conjugate of the product, which translates to negating inside the sum of squares. Second, changing \(1+i\) to \(1-i\) is the same as multiplying by \(-i\text{,}\) which just interchanges two numbers and negates one of them. Between these two operations, each essentially equivalent sum of squares appears 4 times and so the 8 different products yield only 2 essentially different sums of squares. By the second part of the proof of Theorem 6.23, every expression of \(1010\) as a sum of two squares comes from a factorization into Gaussian irreducibles, and so these are the only ways to write \(1010\) as a sum of squares.
PrevTopNext