Prime Suspects

Sophie Maclean

In the English-speaking world, we have a saying. “All prime numbers are odd, except for 2 which is the oddest of all.” But what if I told you that 2 is not prime. Nor is 5. Nor is 13. In fact, roughly half of all prime numbers you know are not prime.

I imagine your reaction would be somewhere on the spectrum between outraged and disbelieving, and both of these responses would be fair. Whilst I have not, strictly speaking, lied to you, I have been somewhat misleading. You see, I am not talking about prime numbers as you know them. I am talking specifically about Gaussian prime numbers. So let us investigate.

Gaussian Numbers 

We begin with a brief recap on complex numbers. As you may well know, the real numbers are all the numbers on the number line from \( -\infty\) to \(\infty\), including fractions and irrational numbers like \(\pi\). When looking at real numbers, there is no solution to the equation \( x^2 = -1\). Complex numbers were created to solve this problem, and call the solution to this equation as \(i\). You may also see this written as \(i = \sqrt{-1}\).

A complex number is then a number of the form \(a + bi\), where \(a\) and \(b\) are real numbers. A quick check shows that multiplying, dividing, (and adding and subtracting) complex numbers gives other complex numbers. For example

\( (a+bi)(a’+b’i) = aa’ + (ab’ + a’b)i + bb’ (i)^2 = (aa’ – bb’) + (ab’ + a’b)i\).

This is promising for being able to define an equivalent notion of prime numbers.

As a side note, those who are already familiar with the concept of complex numbers may be interested to learn that we can define complex numbers without introducing the concept of \(i\) at all. Instead of considering complex numbers as \(a + bi\), we can define them as ordered pairs \( (a,b) \). “Multiplication” is then defined as the function that takes \( (a,b)\) and \( (a’,b’)\) as inputs, and outputs \( (aa’-bb’, ab’ + a’b)\). 

The Gaussian integers are a subset of the complex numbers. Specifically, they are the complex numbers for which \(a\) and \(b\) (in either of the definitions of complex numbers above!) are integers. Written in slightly more formal language, we can say that the Gaussian integers are the set of \(a + bi\) for which \(a, b\) are in the set of integers. 

Now we have defined the Gaussian integers, the next step is to get a rigorous definition of prime numbers.

Prime Numbers 

You probably already know a definition for prime numbers, namely that \(p\) is prime if and only if it is only divisible by \(1\) and itself. This definition does not work with complex numbers. In fact, it does not even work with the integers. This is because \( 1 = -1 \times -1\), and so the only integer that is divisible ONLY by \(1\) and itself is \(-1\) (all others must also have a factor of \(-1\)).

So, we need a more general definition for prime numbers. A definition that not only works for the natural numbers, but also the integers and the Gaussian integers. Thankfully mathematicians long ago solved this problem, so the official definition of a prime number is as follows:

A number \(p\) is prime if for any \(c, d\) for which \(p\) is a factor of \(cd\), \(p\) is either a factor of \(c\), or \(d\) is a factor of \(b\) (or both)

By “\(x\) is a factor of \(y\)”, we mean that there exists some \(k\) such that \(x=ky\).

This new definition can now be applied to our Gaussian integers!

Gaussian Primes

Putting all this together, we get our definition of Gaussian primes! They are Gaussian integers satisfying the above definition of prime numbers. So when I said that \(2\) is not a prime number, I was being truthful because we can take \(c = 1 + i\) and \(d = 1 – i\). \(cd = (1 + i)(1-i) = 2\), so \(2\) is definitely a divisor of \(cd\). But \(2\) does not divide \(c\) or \(d\) on their own, so it cannot be prime.

Our definition for Gaussian primes ends up being equivalent to \(p\) is prime if its only divisors are itself, \(1, -1, i\) and \(-i). So \). \(2 = (1 + i)(1-i) \) is not prime.

Similarly, \(5 = (2+i)(2-i)\) is also not a Gaussian prime. And 13? \(13 = (2+3i)(2-3i)\). Once again, not a Gaussian prime.

The eagle-eyed among you will now have spotted a pattern. All the examples of numbers that we’d normally consider to be prime, which are not Gaussian primes are equal to \( (x+iy)(x-iy) = x^2 + y^2\). In fact, from this, we can see that any prime number that is the sum of two square numbers is not a Gaussian prime.

This is where our old friend Pierre de Fermat pops up. Though he is most famous for his eponymous “Last” theorem, Fermat also has a theorem on the sum of two squares. This theorem states that an odd prime \(p\) can be written as the sum of two squares \(x^2 + y^2 = p\), for \(x\) and \(y\) integers, if and only if \(p\) is one more than a multiple of 4.

So, there we have it: Any prime number that is one more than a multiple of 4 is not a Gaussian prime.

As for a proof of Fermat’s theorem on the sum of two squares, Fermat never wrote one down. Several proofs and algorithms for finding \(x\) and \(y\) with \(x^2 + y^2 = p\) have since been discovered, but I will not spoil your fun and I will let you have a go at working one out yourself.

The post Prime Suspects originally appeared on the HLFF SciLogs blog.