Section14.1A Complex Situation

There is yet another way to interpret all of this. Suppose that \[n=a^2+b^2\; .\] Then, if we let the symbol \(i\) stand for a (putative) square root of negative one, so that \(-1=i^2\), we could legitimately factor this: \[n=a^2-(i^2b^2)=(a+bi)(a-bi)\] For instance, we could factor the prime number thirteen!!!

It turns out that there is a beautiful connection between the theory of numbers in \(S_2\) and the Gaussian integers (named after C.F. Gauss, who explored them a great deal, though others were at least incipiently aware of them).

Definition14.1.1
The Gaussian Integers\(\mathbb{Z}[i]\) may be defined as the set \[\mathbb{Z}[i]=\{a+bi\mid a,b\in\mathbb{Z}\}\] This does assume that we can have such a symbol \(i\) with \(i^2=-1\).

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\), 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. More to our purposes, there is a direct connections the other direction to writing numbers as a sum of squares. In fact, one can prove that first, rather than second as we did here.

The factorization of \(a^2+b^2\) yielding \(i\), a “square root of negative one” over the integers, should mean we aren't surprised that there is a connection with “square roots modulo \(n\)”.

Subsection14.1.1Revisiting the Norm

How can we decide whether the word “factor” becomes the legitimate word factor in such a number system? The reason we can do this it because prime numbers can be defined for this new system as well.

Viewing these so-called Gaussian primes is fun. Many authors have created beatiful graphics such as this.

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 earlier for the points, so that \(N(x+iy)=x^2+y^2\).

Example14.1.3
The norm of \(3+2i\) is \(3^2+2^2=13\) while the norm of \(13=13+0i\) is \(169\).

The difference is that instead of saying simply that \(a=bq+r\) for \(r< b\), we will need to compare the norms of \(r\) and \(b\). Namely, you can write two Gaussian integers \(a\) and \(b\) as \(a=bq+r\), where \(0\leq N(r)<N(b)\), and this process ends by well-ordering to define \(gcd(a,b)\). 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\). So we have a Bezout identity as well to play with.

Computing with Gaussian integers this way is possible, but the naive things one might do are tricky to get to work nicely with the not-so-naive things professional number theorists need factorization in general algebraic structures coming from the complex numbers to do.

Crucially, I am skipping whether we actually have unique factorization in \(\mathbb{Z}[i]\).

Subsection14.1.2

This allows 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. Unfortunately, it requires us to take an algebraic fact on faith – the fact we proved using geometry.

Still, it's worth looking at.

  • Let \(p\equiv 1\text{ mod }(4)\), as we know.
  • We already know that \[r = \left(\frac{p-1}{2}\right)!\] is a square root of \(-1\) modulo \(p\).
  • But now, instead of doing geometry, let's look at what that means. It means, by definition of \[r^2\equiv -1\text{ mod }(p)\] that \[p\mid r^2+1\; .\]
  • Since \(r^2+1\) is \(r^2-i^2\), let's factor: \[r^2+1=(r+i)(r-i)\]
  • Clearly \(p\) does not divide either of those as something of the form \(a+bi\).
  • So (crucial!), if we assume the FTA still holds for Gaussian integers, then \(p\) factors in \(\mathbb{Z}[i]\), and has a prime divisor \(a+bi\).
  • It's not hard to show that then \(a-bi\) also must divide \(p\). We'll skip this.
  • Then \[(a+bi)(a-bi)\mid p^2\Rightarrow a^2+b^2 \mid p^2\]
  • Further, this is a nontrivial divisor, since \(a+bi\) was a proper divisor of \(p\). So the only possibility is \[a^2+b^2=p\; .\]