8 Gaussian integers
Having investigated the arithmetic of \(\mathbb{Z}\) quite thoroughly, we’re now going to look at how factorisation, primes, etc work out in some other algebraic structures – in particular, some subrings of the complex numbers which behave a bit like \(\mathbb{Z}.\)
8.1 Definitions
Definition 8.1
For any \(\alpha \in \mathbb{C},\) we let \(\mathbb{Z}[\alpha]\) denote the subgroup of \((\mathbb{C}, +)\) generated by the powers \(\{1, \alpha, \alpha^2, \dots \}.\)
This is clearly a subring of \(\mathbb{C},\) not just an additive subgroup, and in fact it’s the smallest subring containing \(\alpha.\) It is always an integral domain (since it’s a subring of \(\mathbb{C},\) which is a field and hence an integral domain, and any subring of an integral domain is an integral domain.)
Definition 8.2
The ring of Gaussian integers is the ring \(\mathbb{Z}[i],\) where \(i = \sqrt{-1}\) as usual.
Since \(i^2 = -1,\) any element of \(\mathbb{Z}[i]\) can be written uniquely as \(a + b i\) for some \(a, b \in \mathbb{Z}\); so \(\mathbb{Z}[i]\) is isomorphic to \(\mathbb{Z}^2\) as an additive group. We can visualise it as a “square lattice” inside the complex plane:
Definition 8.3
If \(x = a + b i \in \mathbb{Z}[i],\) we define \(N(x) = |x|^2 = a^2 + b^2.\)
Note that \(N(x) \in \mathbb{N},\) and \(N(xy) = N(x) N(y).\) Moreover, we have \(N(x) = x \bar{x},\) where \(\bar{x}\) is the complex conjugate of \(x\) (which is in \(\mathbb{Z}[i]\) if \(x\) is).
Let’s use this to compute the units in \(\mathbb{Z}[i].\) If \(x\) is invertible in \(\mathbb{Z}[i],\) then \(N(x)\) is invertible in \(\mathbb{N}\); so it must be 1. Conversely, if \(N(x) = 1,\) then \(x\) is invertible, since its inverse is \(\bar{x}.\) So the units are exactly the \(x\) with \(N(x) = 1.\)
However, for integers \(a, b\) we have \(a^2 + b^2 > 1\) unless \((a, b) = (\pm 1, 0)\) or \((0, \pm 1).\) So we’ve shown that:
Proposition 8.4
The set \(\mathbb{Z}[i]^\times\) of invertible Gaussian integers consists precisely of \(\{1, -1, i, -i\}.\)
So we have more invertible elements than we do in \(\mathbb{Z}\) (where the only units are \(\pm 1\)). This means we need to take care of them when making divisibility statements. So we’ll introduce the following notation:
Definition 8.5
We say \(\alpha, \beta \in \mathbb{Z}[i]\) are associates if \(\alpha = u \beta\) for a unit \(u.\)
Clearly this is an equivalence relation; moreover, \(\alpha\) and \(\beta\) are associates iff \(\alpha \mid \beta\) and \(\beta \mid \alpha.\)
8.2 Euclidean division
Proposition 8.6
Let \(\alpha, \beta \in \mathbb{Z}[i]\) with \(\alpha \ne 0.\) Then there exist \(\kappa, \rho \in \mathbb{Z}[i]\) such that
\(\beta = \kappa \alpha + \rho,\)
\(0 \leqslant N(\rho) < N(\alpha).\)
Proof. Let \(q = \beta / \alpha \in \mathbb{C}.\) Clearly \(q = u + v i\) with \(u, v \in \mathbb{Q}\); but \(u\) and \(v\) won’t necessarily be in \(\mathbb{Z}.\)
We shall define \(\kappa = x + y i \in \mathbb{Z}[i]\) by rounding \(u,\) \(v\) to the nearest integer, so that \(|x - u| \leqslant\tfrac{1}{2}\) and \(|y - v| \leqslant\tfrac{1}{2}.\) Then we compute that \[\rho = \beta - \kappa \alpha = \alpha \left( (u + vi) - (x + yi) \right).\] Since the norm on \(\mathbb{C}\) is multiplicative, we have \[N(\rho) = N(\alpha) \cdot \left( (u - x) ^ 2 + (v - y) ^ 2 \right) .\] But both \(|u - x|\) and \(| v - y|\) are \(\leqslant\tfrac{1}{2},\) so \((u - x) ^ 2 + (v - y) ^ 2 \leqslant(\tfrac{1}{2})^2 + (\tfrac{1}{2})^2 = \tfrac{1}{4} + \tfrac{1}{4} = \tfrac{1}{2}.\) So we’ve shown that \[N(\rho) \leqslant\frac{1}{2} N(\alpha) < N(\alpha).\]
Example 8.7
For \(\beta = 11 + 8i\) and \(\alpha = 2 + 3 i,\) we compute \[\frac{\beta}{\alpha} = \frac{(11 + 8i)(2 - 3i)}{(2 + 3i)(2 - 3i)} = \frac{46}{13} + \frac{-17}{13}i.\] Rounding \(\tfrac{46}{13}\) and \(\tfrac{-17}{13}\) to the nearest integers we obtain \(\kappa = u + vi = 4 - i,\) and hence \[\rho = \beta - \kappa \alpha = (11 +8i) - (2 + 3i) \cdot (4 - i) = -2i.\]
Remark 8.8
Note that, unlike in the case of \(\mathbb{Z},\) we haven’t claimed any uniqueness for \(\kappa\) and \(\rho.\) Can you find a different pair \((\kappa, \rho)\) which also works, for the same \((\alpha, \beta)\) as above?
Proposition 8.6 is precisely the statement that \(\mathbb{Z}[i]\) is a Euclidean ring (Algebra, Chapter 9). This is exactly what we need to make the Euclidean algorithm work in \(\mathbb{Z}[i]\): for any two elements \(\alpha, \beta\) there exists an (explicitly computable) element \(\gcd(\alpha, \beta),\) well-defined up to multiplication by units, such that we have \[\forall x \in \mathbb{Z}[i], \qquad x \mid \gcd(\alpha, \beta) \iff x \mid \alpha \text{ and } x \mid \beta.\] Moreover, \(\gcd(\alpha, \beta)\) can always be written as \(r \alpha + s \beta\) for \(r, s \in \mathbb{Z}[i].\)
Remark 8.9
Note that in general there are four equally valid possibilities for the GCD – it is only well-defined up multiplication by \(\{ \pm 1, \pm i\}\) and there’s no obvious “best” choice among these four options.
Example 8.10
From the calculation above, \(\gcd(11 + 8i, 2 + 3i) = \gcd(2 + 3i, -2i).\) We also have \[(2 + 3i) = (-1 + i) \cdot (-2i) + i,\] so \[\gcd(2 + 3i, -2i) = \gcd(-2i, i).\] Since \(i\) is a unit, this shows that \(11 + 8i\) and \(2 + 3i\) are coprime in \(\mathbb{Z}[i].\)
Corollary 8.11
Let \(\alpha \in \mathbb{Z}[i].\) Then the following are equivalent:
\(\alpha\) is an indecomposable element: that is, if \(\beta \mid \alpha,\) then either \(\beta\) is a unit or it is an associate of \(\alpha.\)
\(\alpha\) is a prime element: that is, if \(\rho, \sigma \in \mathbb{Z}[i]\) and \(\alpha \mid \rho\sigma,\) then \(\alpha \mid \rho\) or \(\alpha \mid \sigma.\)
Proof. Cf. Algebra, Prop 9.21. Since \(\mathbb{Z}[i]\) is Euclidean, it is a PID; and in a PID, prime elements and indecomposable elements coincide. Alternatively, we can repeat exactly the same argument as for \(\mathbb{Z},\) using Euler’s Lemma 1.20.
Remark 8.12
Recall that you saw in Algebra that in the similar-looking ring \(\mathbb{Z}[\sqrt{-5}],\) the element 3 is indecomposable but not prime, since it divides \((1 - \sqrt{-5})(1 + \sqrt{-5})\) but doesn’t divide either factor. So this is something rather special about \(\mathbb{Z}[\sqrt{-1}].\)
Corollary 8.13
(Fundamental Theorem of Arithmetic for \(\mathbb{Z}[i]\)). Any non-zero \(\alpha \in \mathbb{Z}[i]\) can be written as a product of prime elements. Moreover, if \[\alpha = \pi_1 \pi_2 \dots \pi_r = \mu_1 \mu_2 \dots \mu_s\] are two factorisations of \(\alpha\) as products of prime elements, then \(r = s,\) and we can re-order the factors so that \(\mu_i\) is an associate of \(\pi_i\) for \(i = 1, \dots, r.\)
Exactly as before, we can also gather together the factors and write \[\alpha = u \cdot \prod_i \pi_i^{e_i},\] with \(u\) a unit, \(e_i \in \mathbb{N}_+,\) and \(\pi_i\) primes which are pairwise non-associate.
8.3 Gaussian primes
We’ll now classify all the primes in \(\mathbb{Z}[i].\) We start with the following easy remark:
Proposition 8.14
Suppose \(\alpha \in \mathbb{Z}[i]\) is a prime element. Then there is a unique prime integer \(p \in \mathbb{P}\) such that \(\alpha\) divides \(p.\) (We say \(\alpha\) lies above the prime integer \(p.\))
Proof. Consider the norm \(N(\alpha),\) which is a non-zero integer. Since \(\alpha \bar{\alpha} = N(\alpha),\) we have \(\alpha \mid N(\alpha).\) From the factorisation theory of \(\mathbb{Z},\) we can write \(N(\alpha)\) as a product of prime integers; but since \(\alpha\) is prime, it must divide one of these factors. This shows that \(\alpha\) must divide some \(p \in \mathbb{P}.\) But if \(\alpha\) divides two distinct elements \(p, q \in \mathbb{P},\) then it must divide \(m p + n q\) for all \(m, n \in \mathbb{Z}\); so it must divide 1, which is a contradiction since \(\alpha\) is not a unit.
So we can study all Gaussian primes by asking, for each \(p \in \mathbb{P},\) which Gaussian primes lie above it.
Proposition 8.15
Given \(p \in \mathbb{P},\) exactly one of the following two possibilities occurs:
\(p\) factors as \(\alpha \bar\alpha,\) for some prime \(\alpha \in \mathbb{Z}[i]\) with \(N(\alpha) = p.\) Then the primes above \(p\) are the associates of \(\alpha\) and \(\bar\alpha.\)
\(p\) is itself a prime element of \(\mathbb{Z}[i]\) (so the only primes above \(p\) are \(\pm p\) and \(\pm i p\)).
Moreover, the first case occurs if and only if there exist integers \((x, y)\) with \(p = x^2 + y^2.\)
Proof. First let us assume that \((x, y)\) exists with \(p = x^2 + y^2.\) Then \(\alpha = x + yi \in \mathbb{Z}[i]\) satisfies \(N(\alpha) = p.\) Since \(N(\alpha) = \alpha \bar{\alpha},\) we have \(\alpha \mid p\); and \(\alpha\) must be indecomposable, and hence prime, since if \(\alpha\) factors as a product \(\beta \gamma\) then we must have \(N(\beta)N(\gamma) = N(\alpha) = p,\) so one of \(\beta\) and \(\gamma\) has norm 1 and is thus a unit. Since \(N(\bar\alpha) = N(\alpha)\) we see that \(\bar{\alpha}\) is also prime. Moreover, any prime above \(p\) must divide \(\alpha \bar\alpha\); so it divides one of \(\alpha\) and \(\bar\alpha,\) and must therefore be an associate of it, since they are both prime.
Conversely, if no such \((x, y)\) exists, then \(p\) is indecomposable, since any nontrivial factor \(\beta\) of \(p\) would have to satisfy \(N(\beta) = p.\)
We’d like to know which \(p \in \mathbb{P}\) remain prime, and which do not. Clearly \(p = 2\) factors as \((1 + i)(1 - i),\) so we can restrict to odd \(p.\) It turns out that the answer depends only on \(p \bmod 4.\) One direction is easy:
Proposition 8.16
Let \(p \in \mathbb{P}.\) If \(p = 3 \bmod 4,\) then \(p\) is a Gaussian prime.
Proof. The only squares mod 4 are \(0\) and \(1,\) so if \(p = 3 \bmod 4,\) the equation \(x^2 + y^2 = p\) has no solutions mod 4 and hence no solutions in \(\mathbb{Z}.\)
It turns out that the converse is also true, but this is a much deeper theorem:
Theorem 8.17 • Fermat
Let \(p \in \mathbb{P}\) with \(p = 1 \bmod 4.\) Then \(p\) is not a Gaussian prime. Equivalently, \(p\) is the sum of two integer squares.
Proof. Consider the equation \(X^2 + 1 = 0 \bmod p.\) This has a solution, since \(p \ne 3 \bmod 4.\) Choose \(t \in \mathbb{Z}\) such that \(t^2 + 1 = 0 \bmod p\); and let \(\alpha = \gcd(t - i, p).\)
Clearly \(\alpha \mid p,\) but \(\alpha\) is not an associate of \(p,\) since \(p \nmid t - i.\) Thus \(N(\alpha) = 1\) or \(p\); and it suffices to prove that \(N(\alpha) \ne 1,\) i.e. that \(t - i\) and \(p\) aren’t coprime in \(\mathbb{Z}[i].\)
Consider the map \[\lambda : \mathbb{Z}[i] \to \mathbb{F}_p, \qquad a + bi \mapsto a + t b \bmod p.\] This is obviously compatible with addition; we claim it’s also compatible with multiplication. This can be checked explicitly: if \(u = a + bi,\) \(v = c + di,\) then \[\lambda(uv) = \lambda( (ac - bd) + (ad + bc) i) = (ac - bd) + t (ad + bc) \bmod p,\] while \[\lambda(u) \lambda(v) = (a + tb)(c + td) = (ac + t^2 bd) + t (ad + bc) \bmod p,\] and since \(t^2 = -1 \bmod p\) these are the same.
Clearly \(\lambda\) kills both \(p\) and \(t - i.\) So if these elements were coprime, there would be \(u, v\) with \(u p + v (t - i) = 1,\) and we’d have \(1 = \lambda(up + v(t - i)) = 0 + 0 = 0 \bmod p,\) which is a contradiction. So \(p\) and \(t - i\) can’t be coprime.
Remark 8.18
Fermat announced that he had proved the theorem in a letter dated Christmas Day 1640, but he never revealed his method of proof (sound familiar?). Just like Quadratic Reciprocity, this theorem now has many different proofs; these include a famous “one-sentence proof” due to Don Zagier (link).
Exercise 8.19
Show that if \(p = 1 \bmod 4\) and \(\alpha \in \mathbb{Z}[i]\) satisfies \(N(\alpha) = p,\) then \(\bar\alpha\) is not an associate of \(\alpha.\) (Hint: if \(\alpha\) divides \(t - i,\) for some \(t \in \mathbb{Z}\) as above, then \(\bar\alpha\) divides \(t + i.\))
8.4 Euclidean rings
Recall the following construction from Algebra:
Definition 8.20
Let \(R\) be an integral domain. A Euclidean function on \(R\) is a map \[\delta : R \setminus \{0\} \to \mathbb{N}\] such that for every \(a, b \in R\) with \(b \ne 0,\) we can find \(q, r \in R\) with \(a = b q + r\) such that either \(r = 0,\) or \(\delta(r) < \delta(b).\)
We know that \(\mathbb{Z}, k[X]\) for \(k\) a field, and \(\mathbb{Z}[i]\) are examples of Euclidean domains. One can check similarly that \(\mathbb{Z}[\sqrt{-2}]\) (i.e. the subring of \(\mathbb{C}\) consisting of numbers of the form \(a + b \sqrt{-2},\) with \(a, b \in \mathbb{Z}\)), is a Euclidean domain, with the Euclidean function again given by \(N(x) = x \bar{x},\) so \(N(a + b\sqrt{-2}) = a^2 + 2b^2.\)
Exercise 8.21
Prove that \(N\) is a Euclidean function on \(\mathbb{Z}[\sqrt{-2}].\) (You will need the fact that if \(|p|, |q| \leqslant\tfrac{1}{2}\) then \(p ^2 + 2 q^2 \leqslant\tfrac{3}{4} < 1.\))
It follows that factorisation in \(\mathbb{Z}[\sqrt{-2}]\) works in just the same elegant way as before; the ring is a PID and a UFD, and and we can characterise exactly which primes remain prime in \(\mathbb{Z}[\sqrt{-2}]\) in terms of congruences mod 8.
Exercise 8.22 • hard!
Show that an odd prime \(p\) has the form \(x^2 + 2y^2\) iff \(p = 1, 3 \bmod 8,\) and not if \(p = 5, 7 \bmod 8.\)
[Hint: First show that \(-2\) is a square mod \(p\) iff \(p = 1, 3\bmod 8,\) using the supplementary laws of quadratic reciprocity.]
8.5 The Eisenstein integers
On the other hand, the ring \(\mathbb{Z}[\sqrt{-3}]\) is not Euclidean. It can’t be, because \[(1 - \sqrt{-3}) (1 + \sqrt{-3}) = 4 = 2 \cdot 2\] and 2 does not divide either factor on the right. So 2 is not a prime element; but it is obviously indecomposable since \(a^2 + 3b^2 = 2\) has no solutions. So \(\mathbb{Z}[\sqrt{-3}]\) is not a PID, and hence not Euclidean either. However, we can fix this by embedding \(\mathbb{Z}[\sqrt{-3}]\) inside a slightly larger ring:
Definition 8.23
The Eisenstein integers is the subring \(\mathbb{Z}[\omega] \subset \mathbb{C},\) where \(\omega = \frac{-1 + \sqrt{-3}}{2}.\)
This clearly contains \(\mathbb{Z}[\sqrt{-3}]\) (since \(\sqrt{-3} = 2\omega + 1\)), but it is slightly larger, since \(\omega \notin \mathbb{Z}[\sqrt{-3}].\)
One can check that \(\mathbb{Z}[\omega]\) consists precisely of the linear combinations \(a + b \omega\) with \(a, b \in \mathbb{Z}.\) This is because \(\omega\) satisfies the equation \(\omega^2 = -1 - \omega,\) and we can use this (and induction on \(n\)) to show that \(\omega^n\) is a \(\mathbb{Z}\)-linear combination of \(1\) and \(\omega\) for all \(n \in \mathbb{N}.\)
Exercise 8.24
Show that the abelian-group quotient \(\mathbb{Z}[\omega] / \mathbb{Z}[\sqrt{-3}]\) has order 2.
From Wikipedia, with thanks to Wikipedia contributor gunther.
Exercise 8.25
Find all the units of \(\mathbb{Z}[\omega].\) (Hint: There are 6 of them.)
From Figure 8.3, it’s easy to convince yourself that for every \(x \in \mathbb{C},\) there exists \(y \in \mathbb{Z}[\omega]\) with \(|x - y| < 1.\) (In fact we can do a little better: we’re never more than \(\tfrac{1}{\sqrt{3}} \cong 0.58\) away from an element of \(\mathbb{Z}[\omega].\)) This suffices to show that \(\mathbb{Z}[\omega]\) is Euclidean, with \(N(x) = x\bar{x}\) as the Euclidean function, just as before. So \(\mathbb{Z}[\omega]\) is a PID and a UFD; and we can deduce the following:
Proposition 8.26
Let \(p \in \mathbb{P}.\) Then \(p = N(\alpha)\) for some \(\alpha \in \mathbb{Z}[\omega]\) if and only if \(p = 1 \bmod 3.\)
Exercise 8.27
Can you show that, despite \(\mathbb{Z}[\sqrt{-3}]\) not being a PID, nonetheless every prime that is \(1 \bmod 3\) has the form \(x^2 + 3 y ^2\)? (Hint: Show that if \(\alpha \in \mathbb{Z}[\omega]\) then at least one of its associates lies in the subring \(\mathbb{Z}[\sqrt{-3}].\))
8.6 Another non-Euclidean ring
Now consider \(\mathbb{Z}[\sqrt{-5}].\) Again, this is not a UFD, because \[6 = 2 \cdot 3 = (1 + \sqrt{-5}) (1 - \sqrt{-5})\] are two distinct factorisations of the same element.
It turns out that this failure is in some sense much worse than with \(\mathbb{Z}[\sqrt{-3}].\) This is for two reasons:
One can show that the non-uniqueness of factorisation in \(\mathbb{Z}[\sqrt{-3}]\) is “local at the prime 2”. Let’s say \(a + b \sqrt{-3}\) is good if \(a + b\) is odd; one checks that the product of good elements is good (exercise). It turns out that good indecomposable elements are prime, and good elements have unique prime factorisations. So we can restore uniqueness of factorisation by imposing congruences modulo 2. In contrast, the failure in \(\mathbb{Z}[\sqrt{-5}]\) is “global”; we can’t get rid of it by imposing congruences to any fixed modulus.
In \(\mathbb{Z}[\sqrt{-3}]\) we were able to restore unique factorisation by going up to the “finitely larger” ring \(\mathbb{Z}[\omega].\) In \(\mathbb{Z}[\sqrt{-5}]\) this doesn’t work: there aren’t any rings finitely larger than \(\mathbb{Z}[\sqrt{-5}].\) More precisely, if \(R\) is a ring with \(\mathbb{Z}[\sqrt{-5}] \subseteq R \subseteq \mathbb{C},\) then \(R\) is either equal to \(\mathbb{Z}[\sqrt{-5}],\) or much bigger (the index \([R : \mathbb{Z}[\sqrt{-5}]]\) is infinite).
(These two explanations are related by the fact that \(2 = [\mathbb{Z}[\omega] : \mathbb{Z}[\sqrt{-3}]],\) so \(\mathbb{Z}[\sqrt{-3}]\) is “a factor of 2 away from a UFD”.)