Unit 9: Gaussian integers

Primes in the plane

Which whole numbers can be written as a sum of two squares? \(5 = 1^2 + 2^2\) and \(13 = 2^2 + 3^2\) can, but 3, 7 and 21 can't. Fermat stated the answer in 1640, and the cleanest proof uses a ring: the Gaussian integers, where sums of two squares factor as \(a^2 + b^2 = (a + bi)(a - bi)\). Everything from Units 6 to 8 comes together here.

1234567891011
In this unit
  1. A ring you can draw
  2. Sums of two squares are norms
  3. The Gaussian primes
  4. Fermat's two-squares theorem
  5. Finding the squares with Euclid
  6. Counting the ways
  7. Pythagorean triples
  8. Practice set
  9. Summary and glossary

A ring you can draw

The Gaussian integers are the complex numbers with whole-number coordinates:

\[ \mathbb{Z}[i] = \{a + bi : a, b \in \mathbb{Z}\}. \]

They form a square grid of points in the plane, and they're closed under addition and multiplication, so they form a ring. Gauss introduced them in 1832 to study fourth powers modulo primes. Here's what we know about them from earlier units:

That last fact is the engine of this unit.

Sums of two squares are norms

A number \(n\) is a sum of two squares exactly when \(n = a^2 + b^2 = N(a + bi)\): when \(n\) is the norm of some Gaussian integer. Geometrically, when the circle of radius \(\sqrt n\) passes through a grid point.

Lattice points on two circlesA square grid of points centred at 0 with two circles. The small purple circle of radius root 5 passes through 8 grid points: plus or minus 1 plus or minus 2i and plus or minus 2 plus or minus i. The larger pink circle of radius 5 passes through 12 grid points: plus or minus 5, plus or minus 5i, and the eight points plus or minus 3 plus or minus 4i and plus or minus 4 plus or minus 3i.2 + i4 + 3i
Grid points on circles. The circle of radius \(\sqrt5\) hits 8 grid points, because \(5 = 1^2 + 2^2\) (with all sign and order choices). The circle of radius 5 hits 12: \(25 = 0^2 + 5^2 = 3^2 + 4^2\). The circle of radius \(\sqrt3\) would hit none.

Because norms multiply, products of sums of two squares are sums of two squares. Multiplying out \(N(\alpha)N(\beta) = N(\alpha\beta)\) gives an identity known since Diophantus:

\( (a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2 \) For example \(5 \times 13 = 65\): \((2 + i)(3 + 2i) = 4 + 7i\), so \(65 = 4^2 + 7^2\). Using \(3 - 2i\) instead gives \(8 - i\), so also \(65 = 8^2 + 1^2\).

So the key question is: which primes are sums of two squares? Every other answer follows by multiplying.

The Gaussian primes

Since \(\mathbb{Z}[i]\) has unique factorisation, every Gaussian integer factors into Gaussian primes. What do they look like? Here are all of them near the origin:

The Gaussian primes near the originDots at every Gaussian prime a + bi with a and b between minus 16 and 16. The pattern has the symmetry of a square: it looks the same after rotating by 90 degrees or reflecting in either axis or diagonal. Primes on the axes, such as 3, 7, 11 and their multiples by i, are pink; the four associates of 1 + i next to the origin are amber; all other dots, such as 2 + i and 3 + 2i, are purple.
The Gaussian primes with \(|a|, |b| \le 16\). The picture has the symmetry of a square: multiplying by \(i\) rotates it, and complex conjugation reflects it. Amber: \(1 + i\) and its associates. Pink: ordinary primes \(3, 7, 11\) on the axes. Purple: everything else, such as \(2 + i\) and \(3 + 2i\), whose norms are ordinary primes.

Notice what's missing from the axes: 2, 5, 13 and 17 are not Gaussian primes. They factor: \(2 = -i(1 + i)^2\), \(5 = (2 + i)(2 - i)\), \(13 = (3 + 2i)(3 - 2i)\), \(17 = (4 + i)(4 - i)\). Meanwhile 3, 7, 11 stay prime. The rule:

Theorem: the Gaussian primes

Up to multiplying by units, every Gaussian prime is one of the following:

  1. \(1 + i\), of norm 2. (\(2 = -i(1 + i)^2\): 2 ramifies.)
  2. \(a + bi\) and \(a - bi\) where \(a^2 + b^2 = p\) is an ordinary prime with \(p \equiv 1 \pmod 4\). (\(p\) splits into two.)
  3. An ordinary prime \(p \equiv 3 \pmod 4\). (\(p\) stays inert.)

These three behaviours are exactly the ones in the curve \(x^2 + 1 = 0\) over each prime in Unit 7's map of \(\operatorname{Spec} \mathbb{Z}[x]\): touching at 2, two separate points at \(p \equiv 1\), one fused point at \(p \equiv 3\). That's no coincidence: \(\mathbb{Z}[i]/(p) \cong (\mathbb{Z}/p)[x]/(x^2 + 1)\), and \(p\) splits in \(\mathbb{Z}[i]\) exactly when \(x^2 + 1\) factors mod \(p\).

Fermat's two-squares theorem

Theorem: Fermat (1640), first proved by Euler (1747)

An odd prime \(p\) is a sum of two squares if and only if \(p \equiv 1 \pmod 4\).

One direction is quick. Squares are \(\equiv 0\) or \(1 \pmod 4\), so a sum of two squares is \(\equiv 0, 1\) or \(2\), never 3. The other direction is where ring theory shines. The proof has three steps.

Show proof

Step 1: \(-1\) is a square mod \(p\). Let \(x = \left(\tfrac{p-1}{2}\right)!\). Pair each factor \(k\) of \((p-1)!\) with \(p - k \equiv -k\):

\[ (p - 1)! = \prod_{k=1}^{(p-1)/2} k\,(p - k) \equiv \prod_{k=1}^{(p-1)/2} (-k^2) = (-1)^{(p-1)/2}\, x^2. \]

Since \(p \equiv 1 \pmod 4\), \((p - 1)/2\) is even, so \((p - 1)! \equiv x^2\). By Wilson's theorem (Unit 4), \((p - 1)! \equiv -1\). So \(x^2 \equiv -1 \pmod p\).

Step 2: \(p\) is not a Gaussian prime. \(p\) divides \(x^2 + 1 = (x + i)(x - i)\). But \(p\) divides neither factor, since \(\tfrac{x}{p} \pm \tfrac{1}{p}i\) is not a Gaussian integer. So \(p\) fails Euclid's lemma: it isn't prime in \(\mathbb{Z}[i]\).

Step 3: so \(p\) is a sum of two squares. \(\mathbb{Z}[i]\) is a UFD, so prime and irreducible mean the same thing. Hence \(p\) is reducible: \(p = \alpha\beta\) with neither a unit. Taking norms, \(p^2 = N(\alpha)N(\beta)\) with both norms bigger than 1, so \(N(\alpha) = p\). Writing \(\alpha = a + bi\): \(p = a^2 + b^2\). ∎

Look at what each unit contributed: Wilson's theorem from polynomials over \(\mathbb{Z}/p\) (Unit 4), the meaning of "prime" from Unit 7, and unique factorisation from the Euclidean property (Unit 8). Step 3 is the decisive one, and it is exactly where \(\mathbb{Z}[\sqrt{-5}]\) would fail.

Combining with the multiplication rule gives the complete answer:

\(n\) is a sum of two squares \(\iff\) every prime \(\equiv 3 \pmod 4\) appears in \(n\) to an even power \(45 = 3^2 \cdot 5 = 6^2 + 3^2\) works. \(21 = 3 \cdot 7\) doesn't. \(2026 = 2 \cdot 1013\), and \(1013 \equiv 1 \pmod 4\) is prime, so \(2026 = 45^2 + 1^2\).

Finding the squares with Euclid

The proof is constructive. To write \(p = 13\) as a sum of two squares:

  1. Find \(x\) with \(x^2 \equiv -1 \pmod{13}\). Wilson's recipe gives \(6! = 720 \equiv 5\), and indeed \(5^2 = 25 \equiv -1\).
  2. Then 13 and \(5 + i\) share the Gaussian prime factor we want. Find it with Euclid's algorithm in \(\mathbb{Z}[i]\).
DivideQuotient (rounded)Remainder
\(13 \div (5 + i) = 2.5 - 0.5i\)\(2\)\(13 - 2(5 + i) = 3 - 2i\)
\((5 + i) \div (3 - 2i) = 1 + i\)\(1 + i\)\(0\)

The last non-zero remainder is the gcd: \(3 - 2i\). Its norm is \(3^2 + 2^2 = 13\). Done: \(13 = 3^2 + 2^2\). For a prime with hundreds of digits, this is fast, while searching through all possible squares would take longer than the age of the universe.

Counting the ways

Unique factorisation tells us not just whether \(n\) is a sum of two squares, but in how many ways. Let \(r_2(n)\) count the grid points on the circle of radius \(\sqrt n\), that is, the pairs \((a, b)\) of integers, signs and order included, with \(a^2 + b^2 = n\).

Theorem: Jacobi's two-squares formula

\[ r_2(n) = 4\,\big(d_1(n) - d_3(n)\big), \]

where \(d_1(n)\) and \(d_3(n)\) count the divisors of \(n\) that are \(\equiv 1\) and \(\equiv 3 \pmod 4\).

Check with the figure: the divisors of 5 are 1 and 5, both \(\equiv 1\), so \(r_2(5) = 4 \cdot 2 = 8\). The divisors of 25 are 1, 5, 25, so \(r_2(25) = 12\). The divisors of 3 are 1 and 3, so \(r_2(3) = 4(1 - 1) = 0\). The formula comes from counting the ways to distribute the Gaussian prime factors of \(n\) between \(\alpha\) and \(\bar\alpha\) in \(n = \alpha\bar\alpha\).

Going deeper: how a ring computes \(\pi\)

Count all grid points inside a circle of radius \(\sqrt N\). There are about \(\pi N\) of them (the area). But the count is also \(1 + r_2(1) + r_2(2) + \dots + r_2(N)\). Use Jacobi's formula and count, for each odd \(d\), how many multiples of \(d\) are at most \(N\): roughly \(N/d\). The \(d \equiv 1\) terms add and the \(d \equiv 3\) terms subtract, giving about

\[ 4N\left(1 - \tfrac13 + \tfrac15 - \tfrac17 + \tfrac19 - \cdots\right). \]

Comparing with \(\pi N\) and dividing by \(N\):

\[ \frac{\pi}{4} = 1 - \frac13 + \frac15 - \frac17 + \cdots, \]

the Leibniz series, derived from the arithmetic of \(\mathbb{Z}[i]\).

Pythagorean triples

A Pythagorean triple is a solution of \(x^2 + y^2 = z^2\) in positive integers, like \(3, 4, 5\). In Gaussian terms, \(N(x + yi) = z^2\) is a perfect square. Squaring any Gaussian integer produces one:

\[ (a + bi)^2 = (a^2 - b^2) + 2ab\,i, \qquad N\big((a + bi)^2\big) = (a^2 + b^2)^2. \]
\(\alpha\)\(\alpha^2\)Triple
\(2 + i\)\(3 + 4i\)\(3^2 + 4^2 = 5^2\)
\(3 + 2i\)\(5 + 12i\)\(5^2 + 12^2 = 13^2\)
\(4 + i\)\(15 + 8i\)\(8^2 + 15^2 = 17^2\)
\(4 + 3i\)\(7 + 24i\)\(7^2 + 24^2 = 25^2\)

Unique factorisation proves that this gives every primitive triple (one with no common factor). If \(x + yi\) has norm \(z^2\) and \(x, y\) share no factor, then \(x + yi\) and \(x - yi\) share no Gaussian prime, and since their product \(z^2\) is a square, each must itself be a square, up to a unit. That's the same reasoning as "if coprime numbers multiply to a square, each is a square", now in \(\mathbb{Z}[i]\).

Practice set

Mixed questions covering the whole unit. Try each one before opening the answer.

1. Factor 10 into Gaussian primes.

Show answer

\(10 = 2 \cdot 5 = -i(1 + i)^2 \cdot (2 + i)(2 - i)\).

2. Is 21 a sum of two squares? Is 49? Is 98?

Show answer

21: no, 3 and 7 appear to odd powers. 49: yes, \(7^2 + 0^2\) (7 appears to an even power). 98: yes, \(98 = 2 \cdot 7^2 = 7^2 + 7^2\).

3. Find \(x\) with \(x^2 \equiv -1 \pmod{17}\), and use it to write 17 as a sum of two squares.

Show answer

\(4^2 = 16 \equiv -1\). Then \(\gcd(17, 4 + i)\) in \(\mathbb{Z}[i]\): \(17 / (4 + i) = 17(4 - i)/17 = 4 - i\) exactly, so \(4 + i\) itself divides 17, and \(17 = 4^2 + 1^2\).

4. Show that \(1 + i\) divides \(a + bi\) exactly when \(a\) and \(b\) are both even or both odd.

Show answer

\(\frac{a + bi}{1 + i} = \frac{(a + bi)(1 - i)}{2} = \frac{(a + b) + (b - a)i}{2}\). This is a Gaussian integer exactly when \(a + b\) and \(b - a\) are even, which is when \(a \equiv b \pmod 2\). On the grid, the multiples of \(1 + i\) form a checkerboard.

5. Square \(5 + 2i\) to find a Pythagorean triple.

Show answer

\((5 + 2i)^2 = 25 + 20i - 4 = 21 + 20i\). So \(20^2 + 21^2 = 29^2\) (\(400 + 441 = 841\)).

6. How many elements does \(\mathbb{Z}[i]/(3)\) have? Is it a field? What about \(\mathbb{Z}[i]/(5)\)?

Show answer

Both have \(N(p) = p^2\) elements: 9 and 25. Since 3 is a Gaussian prime and \(\mathbb{Z}[i]\) is a PID, \((3)\) is maximal, so \(\mathbb{Z}[i]/(3)\) is a field with 9 elements. But \(5 = (2 + i)(2 - i)\), so \(\mathbb{Z}[i]/(5)\) has zero divisors; in fact it is \(\cong \mathbb{Z}/5 \times \mathbb{Z}/5\).

Summary and glossary

  1. \(\mathbb{Z}[i]\) is a Euclidean domain, so it has unique factorisation.
  2. \(n\) is a sum of two squares exactly when it's a norm \(N(\alpha)\). Norms multiply.
  3. Gaussian primes: \(1 + i\); the two factors \(a \pm bi\) of each prime \(p \equiv 1 \pmod 4\); and primes \(p \equiv 3 \pmod 4\).
  4. Fermat: an odd prime is a sum of two squares iff \(p \equiv 1 \pmod 4\). The proof: \(-1\) is a square mod \(p\), so \(p\) isn't a Gaussian prime, so it factors.
  5. Euclid's algorithm in \(\mathbb{Z}[i]\) finds the squares; Jacobi's formula counts them.
  6. Squaring Gaussian integers produces every primitive Pythagorean triple.
Gaussian integers
\(\mathbb{Z}[i] = \{a + bi : a, b \in \mathbb{Z}\}\).
Gaussian prime
A prime element of \(\mathbb{Z}[i]\).
Split
A prime of \(\mathbb{Z}\) that factors into two distinct primes.
Inert
A prime of \(\mathbb{Z}\) that stays prime.
Ramified
A prime that becomes a square of a prime, up to a unit (only 2 here).
\(r_2(n)\)
The number of ways to write \(n = a^2 + b^2\).
Primitive triple
A Pythagorean triple with no common factor.
Powered by Webloyt | Report abuse