Example 14.1.1.
For instance, we could factor the prime number thirteen!!!
Section 14.1 A Complex Situation
Subsection 14.1.1 A new interpretation
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*}
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.
Definition 14.1.2. Gaussian integers.
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{.}\)
Historical remark 14.1.3. Carl Friedrich Gauss.
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.
Subsection 14.1.2 Revisiting the norm
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.
Fact 14.1.5.
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 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{.}\)
Example 14.1.7.
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.
Subsection 14.1.3 A different approach to sums of squares
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.
Fact 14.1.8.
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.)
Proof.
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*}
and the factor \(a^2+b^2\) is not equal to one, since \(a+bi\) was a proper divisor of \(p\text{.}\) Since \(p\) is an integer prime, the only possibility is
\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.
Remark 14.1.9.
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.)
You can even order serving napkins with them as the design online (search
sannydezoete.nl for ‘primes’). The internet is amazing.
