NTIC A Complex Situation

🔗

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*}$

🔗

Example 14.1.1.

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

xxxxxxxxxx
 
print(3^2+2^2)
print( (3+2*i)*(3-2*i))

🔗

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.

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{.}$

🔗

Remark 14.1.3.

These are named after C.F. 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, and he will come up again when we continue exploring prime numbers in Section 21.2; perhaps most relevant to our work is that he actually published about Gaussian integers!

🔗

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{,}$ the 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).

🔗

Viewing these Gaussian primes is fun. Many authors have created beatiful graphics¹You can even order serving napkins with them as the design online. The internet is amazing. such as the one in Figure 14.1.6.

Figure 14.1.6. Plot of Gaussian primes with coordinates less than 10 in absolute value

🔗

You can keep exploring the beauty of this pattern in the following interact.

xxxxxxxxxx
 
@interact
def _(viewsize=10):
    lattice_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]]
    plot_lattice_pts = points(lattice_pts,rgbcolor=(0,0,0),pointsize=2)
    GG.<I> = GaussianIntegers()
    Gaussian_primes = [ x for x in lattice_pts if GG(x[0]+x[1]*I).is_prime() ]
    plot_Gaussian_primes = sum([polygon([(G[0]+1/2,G[1]+1/2), (G[0]+1/2,G[1]-1/2), (G[0]-1/2,G[1]-1/2), (G[0]-1/2,G[1]+1/2)],alpha=.6) for G in Gaussian_primes])
    show(plot_Gaussian_primes+plot_lattice_pts, aspect_ratio=1)
    pretty_print(html("Plot of Gaussian primes with coordinates less than {0} in absolute value".format(viewsize)))

🔗

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.

xxxxxxxxxx
 
ZZI.<I> = GaussianIntegers()
(1+I).is_prime()

🔗

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.

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 primitive Pythagorean triples as Gaussian integers as well. In this case one uses Fact 13.1.7 to put a group multiplication on this set! See [C.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.