#### Example 14.1.1.

For instance, we could

*factor*the prime number thirteen!!!Let’s see another to interpret sums of squares. Suppose first that, as before,

\begin{equation*}
n=a^2+b^2\text{.}
\end{equation*}

Then, if we let the symbol \(i\) stand for a (putative) square root of negative one, so that \(-1=i^2\text{,}\) we could legitimately factor the equation:

\begin{equation*}
n=a^2-(i^2b^2)=(a+bi)(a-bi)
\end{equation*}

For instance, we could *factor* the prime number thirteen!!!

It turns out that there is a beautiful connection between the theory of numbers representable as a sum of two squares and the following beautiful definition.

The Gaussian Integers \(\mathbb{Z}[i]\) may be defined as the set

\begin{equation*}
\mathbb{Z}[i]=\{a+bi\mid a,b\in\mathbb{Z}\}
\end{equation*}

This does assume that we can have such a symbol \(i\) with \(i^2=-1\text{;}\) typically this is considered to thus be a subset of the so-called complex numbers, denoted \(\mathbb{C}\text{.}\)

These are named after our friend Gauss, who explored them a great deal, though others were at least incipiently aware of them.

There are so many stories about Gauss that one can hardly know where to begin. The most-quoted one is his quick solution to summing the numbers from \(1\) to \(100\) as a child; however, some of his most important work was in physics and magnetism. As an adolescent he kept a fascinating notebook of stunning results. He also was one contributor to the beginnings of modern statistics, proved the fundamental theorem of algebra, helped survey a large part of Germany, and in his own way mentored a number of important mathematicians, including Eisenstein (see Section 17.2), Riemann (see Chapter 24) and Germain (see Subsection 11.6.4, and below).

Gauss will come up again in Section 17.4 regarding solving congruences, and when we continue exploring prime numbers in Section 21.2. Annoyingly, he only published some of his many results (notably in number theory); most relevant here is that Gaussian integers is something he actually *did* publish about.

If we bring back our lattice of integer points, we can think of such numbers as being points on the lattice, where the coordinate point \((3,2)\) corresponds to \(3+2i\text{,}\) one of the ‘factors’ of 13. I’ll plot both ‘factors’ below.

There are many amazing questions to ask about this, and wonderful connections to abstract algebra. For example, the factorization

\begin{equation*}
a^2+b^2=(a+bi)(a-bi)
\end{equation*}

requires \(i\text{,}\) a “square root of negative one” over the integers, so we shouldn’t be surprised that writing as a sum of squares has a connection with “square roots modulo \(n\)”. This connection is actually more direct than we have seen, and we will show some of it in the next section.

How can we decide whether the verb “to factor” is legitimate to use in a given number system? In the Gaussian integers, the reason we can is that *prime* numbers can be defined for this new system as well.

Prime numbers in the Gaussian integers, or Gaussian primes, are of three possible forms:

- Given a prime \(p\in \mathbb{Z}\) of the form \(p=4n+3\text{,}\) \(\pm p\in \mathbb{Z}[i]\) is prime.
- Given a prime \(p\in \mathbb{Z}\) of the form \(p=4n+3\text{,}\) \(\pm p\cdot i\in \mathbb{Z}[i]\) is also prime.
- Given a prime \(p\in \mathbb{Z}\)
*not*of the form \(p=4n+3\text{,}\) any factors \(a+bi\) and \(a-bi\) in \(\mathbb{Z}[i]\) corresponding to writing \(p=a^2+b^2\) are prime (recall Theorem 13.5.5).

The last point can be confusing. Since \(a\) and \(b\) could be positive or negative, and may be distinct, it can be useful to think of the primes thus generated as \(\pm a \pm bi,\pm b \pm ai\text{.}\) In Figure 14.1.4 this means that not only \(3\pm 2i\text{,}\) but also \(-3\pm 2i\text{,}\) \(2\pm 3i\text{,}\) and \(-2\pm 3i\) are *all* Gaussian primes. This is related to the notion of associates in ring theory; see also the end of this subsection.

Viewing these Gaussian primes is fun. Many authors have created beatiful graphics^{ 1 }

such as the one in Figure 14.1.6.

You can even order serving napkins with them as the design online (search

`sannydezoete.nl`

for ‘primes’). The internet is amazing.You can keep exploring the beauty of this pattern in the following interact.

The basic reason this even makes sense is that we can use the Euclidean algorithm here. First, let’s use the *same definition of norm* as we used in Definition 13.4.4 for the points, so that \(N(x+iy)=x^2+y^2\text{.}\)

The norm of \(3+2i\) is \(3^2+2^2=13\) while the norm of \(13=13+0i\) is \(169\text{.}\)

The difference is that instead of saying simply that \(a=bq+r\) for \(r< b\text{,}\) we will need to compare the *norms* of \(r\) and \(b\text{.}\) Namely, you can write two Gaussian integers \(a\) and \(b\) as \(a=bq+r\text{,}\) where \(0\leq N(r)<N(b)\text{.}\) Continue this process just as in Euclidean algorithm, and it ends by the Well-Ordering Principle to define \(\gcd(a,b)\text{.}\) In this case \(\pm 1\) and \(\pm i\) are all possible stopping points if \(a\) and \(b\) don’t share a factor.

Further, if \(g\) and \(h\) are “relatively prime” Gaussian integers (\(\gcd(g,h)=\pm 1\) or \(\pm i\)), then there are other such integers \(x\) and \(y\) such that \(gx+hy=1\text{.}\) So we have a Bezout identity as well to play with.

Computing with Gaussian integers this way is possible in Sage.

Crucially, I am skipping whether we actually have unique factorization in \(\mathbb{Z}[i]\text{.}\) This is true, and is used below in Fact 14.1.8, but properly belongs in an abstract algebra course.

The Gaussian integers allow a quite different approach to the fact primes of the form \(4n+1\) can be written as a sum of squares. We *could* use complex numbers instead of geometry. Unfortunately, it requires us to take an algebraic fact on faith instead of the fact we proved using geometry; there are no shortcuts. Still, it’s worth looking at.

If \(p\equiv 1\text{ (mod }4)\) is prime, then \(p\) can be written as a sum of two squares. (This is Theorem 13.4.5.)

We already know, from the proof of Lemma 13.3.3 that

\begin{equation*}
f = \left(\frac{p-1}{2}\right)!
\end{equation*}

is a square root of \(-1\) modulo \(p\text{.}\) But now, instead of doing geometry, let’s look at what that means.

By definition of

\begin{equation*}
f^2\equiv -1\text{ (mod }p)
\end{equation*}

we know that \(p\mid f^2+1\text{.}\) Since \(f^2+1\) is \(f^2-i^2\text{,}\) let’s factor:

\begin{equation*}
f^2+1=(f+i)(f-i)\text{.}
\end{equation*}

Clearly \(p=p+0i\) does not divide either \(f+i\) or \(f-i\) evenly in \(\mathbb{Z}[i]\text{,}\) but it does divide their product. So (crucially!), *if we assume the Fundamental Theorem of Arithmetic still holds for Gaussian integers*, then \(p\) factors in \(\mathbb{Z}[i]\) and has a prime divisor of the form \(a+bi\) (in the sense of Subsection 14.1.2) dividing \(f+i\) or \(f-i\text{.}\)

Given that \(a+bi\mid p\text{,}\) it’s not hard to show that then \(a-bi\) also must divide \(p\text{.}\) We’ll skip this (but see the discussion after Fact 14.1.5 for ideas).

To finish up, combine these facts to see that

\begin{equation*}
(a+bi)(a-bi)\mid p^2\Rightarrow a^2+b^2 \mid p^2
\end{equation*}

\begin{equation*}
a^2+b^2=p\text{.}
\end{equation*}

To emphasize that the assumption about Theorem 6.3.2 really matters, see Exercise 6.6.30.

As a final note to the complex point of view, one may note that there is a way to view Pythagorean triples as Gaussian integers as well. In this case one notes that if \(a^2+b^2=c^2\text{,}\) then \(a+bi\) could represent the triple in question, and moreover one can use Fact 13.1.7 to combine two such triples.

Most remarkably, a variant of this operation applied to *primitive* triples can be used to put a *group multiplication* on that set! See [E.7.29] for more details, such as the multiplication involved and the structure of the group, which an inquiring reader may wish to relate to Remark 3.4.8 and similar facts. (See also Exercise 15.7.21.)