Crash course in Gaussian integers

Yesterday, I attended the UKMT mentoring conference in Murray Edwards College (affectionately abbreviated to ‘Medwards’), which mainly consisted of an excellent dinner in the Fellows’ dining room and informal discussion about various topics. Speaking of mentoring, I recently prepared for one of my mentees a crash course in the application of Gaussian integers to solving certain olympiad-style Diophantine equations.

What follows is an almost verbatim regurgitation of that e-mail.

Brief introduction

So, basically a Gaussian integer is a complex number of the form a + bi, where a and b are both integers. When plotted in the complex plane, they form a square lattice, as shown in the left-hand diagram below.

gaussian-and-eisenstein

The hexagonal lattice of blue points is the ring of Eisenstein integers, which shares many of the same interesting properties as the Gaussian integers. Now, the most important fact about Gaussian integers is this:

Gaussian integers are a Unique Factorisation Domain.

The ordinary integers are also a Unique Factorisation Domain, as I’ll explain below.

Unique factorisation domains

Basically, the elements of \mathbb{Z} (the ring of integers) can be categorised as follows:

  • Zero: 0
  • Units: +1 and -1
  • Irreducibles: +2, -2, +3, -3, +5, -5, +7, -7, +11, -11, …
  • Composite numbers: +4, -4, +6, -6, +8, -8, +9, -9, …

Units are defined as elements whose reciprocals also belong to the ring. In particular, every non-zero element in a field is a unit. Irreducibles are defined to be elements that cannot be expressed as a product of two non-units; everything else is composite.

Now, we define a prime to be a number p such that if p|ab, then p|a or p|b. It’s straightforward to show logically that every prime must be an irreducible. It’s very non-trivial to show that the converse holds (that all irreducibles are primes), and there are rings in which this is not the case, such as \mathbb{Z}[\sqrt{-3}]. But for the integers, this is true, because they form a Principal Ideal Domain.

The integers are also a Unique Factorisation Domain (this follows from the property that all irreducibles are primes), which essentially means that the Fundamental Theorem of Arithmetic holds. Specifically:

Every integer can be uniquely expressed as a product of irreducibles, up to reordering and multiplication by units.

A proof of this from the prime property is given in the bottom-right corner of the second page of this GRM revision sheet I prepared earlier. Anyway, now that I’ve described these concepts in terms of the ordinary integers, I’ll now explain the Gaussian integers.

The Gaussian integers

The Gaussian integers, written Z[sqrt(-1)], also form a PID (hence a UFD), so we have the nice property that all irreducibles are primes. Firstly, we need to identify which elements are units; in this case, they are +1, -1, +i and -i.

Note that the number 2 is not a prime in the Gaussian integers, since (1 + i)(1 – i) = 2, and neither 1 + i nor 1 – i is a unit. 1 + i and 1 – i are irreducibles (and called `associates’ since they differ only by multiplication by a unit, analogous to the irreducibles +3 and -3 in the ordinary integers). In fact, we can show the following:

A positive integer is a Gaussian prime if and only if it is prime (as an ordinary integer) of the form p = 4k + 3.

One direction is easy to prove; p cannot be divisible by any integers >= 2 (by primality), so we need to show that it can’t be expressed as the product of two (complex conjugate) Gaussians, p = (a + bi)(a – bi) = a^2 + b^2. But p is congruent to 3 mod 4, so is not the sum of two squares.

In the other direction, a prime of the form p = 4k + 1 can be expressed of the form a^2 + b^2 = (a + bi)(a – bi), so factorises over the Gaussians and is therefore not a Gaussian primes. There’s a nice proof of this based on Wilson’s theorem, and relying on the notion of Gaussian integers.

It might be informative for you to see what the Gaussian primes look like. Here’s a lovely picture by David Eppstein:

The Gaussian primes are shown as white islands. This particular image is concerned with the ‘Gaussian moat’ (open) problem, which Imre Leader happened to mention to me whilst on a train from Oxford:

Suppose a grasshopper begins at the origin, and can jump to any Gaussian prime within a radius of R. If we choose R sufficiently large at the beginning, is it possible for the grasshopper to escape to infinity?

It has been shown that R = 5 is not sufficient.

Applying Gaussian integers to IMO-style Diophantine equations

Anyway, I guess I should apply this technique to solving an IMO-style problem.

Find all integer solutions to x^2 + 4 = y^3

If that plus had instead been a minus, then you could have easily factorised the left-hand side over the integers. But if we consider factorisations over the Gaussian integers instead, then we get the following:

(x + 2i)(x – 2i) = y^3

The greatest common divisor of x + 2i and x – 2i divides 4, so no primes (with the exception of 1 + i and its associates) can divide both x + 2i and x – 2i. Note that the left-hand side and right-hand side, when fully factorised into primes, must be the same (as the Gaussians are a UFD). Paying particularly careful attention to the prime 1 + i and its associates, we can deduce that x + 2i and x – 2i must be perfect cubes over the Gaussians!

x + 2i = (a + bi)^3 = (a^3 – 3ab^2) + (3a^2b – b^3)i

Hence, equating real and imaginary parts, we get x = a^3 – 3ab^2 and 2 = (3a^2 – b^2)b. The second of these is easy to solve, noting that b must be in the set {-2, -1, +1, +2} (by virtue of dividing 2), leading to the following solutions:

(a,b) = (±1, 1) or (±1, -2)

Substituting back into x = a^3 – 3ab^2, this gives the solutions x = ±2 and x = ±11, respectively, leading to the following integer solutions:

  • 2² + 4 = 2³
  • 11² + 4 = 5³

and no others.

Miscellaneous exercises

So, you’ve now seen how one can use “Gaussians form a UFD” to kill an otherwise difficult Diophantine equation. There are many other useful UFDs, such as Z[sqrt(-2)] — that is to say numbers of the form a + b sqrt(-2), where a and b are integers. Here are a few questions concerned with that particular UFD:

  1. Identify the units of Z[sqrt(-2)].
  2. Give examples of irreducible and composite numbers in Z[sqrt(-2)].
  3. Find all integer solutions to x^2 + 2 = y^3.

The Eisenstein integers are also pretty awesome (and a PID). They’re numbers of the form a + bω, where ω = (-1/2 + sqrt(3) i/2) is a complex cube-root of unity. When plotted on the complex plane, they form a nice hexagonal lattice, as shown in the diagram nearer the beginning of this article.

  1. What are the units in the Eisenstein integers, Z[ω]?

(You can look at the Wikipedia page on Eisenstein integers if you want to understand them better, but the ‘Properties’ section gives a spoiler to question 4.)

There are also rings that don’t form unique factorisation domains. Here’s an example:

  1. In Z[sqrt(-5)] (i.e. numbers of the form a + b sqrt(-5), where a and b are integers), find a number that is expressible as a product of irreducibles in more than one way.

Hence, Z[sqrt(-5)] is not particularly useful for solving problems, since the Fundamental Theorem of Arithmetic does not carry over. The Stark-Heegner theorem states that the only imaginary quadratic fields where the Fundamental Theorem of Arithmetic applies to the integral elements are Q[sqrt(-n)] for n = 1, 2, 3, 7, 11, 19, 43, 67, and 163.

About these ads
This entry was posted in Uncategorized. Bookmark the permalink.

6 Responses to Crash course in Gaussian integers

  1. Anonymous says:

    $!=$

  2. wojowu says:

    How about ring of numbers of form a+b sqrt(-2)+c sqrt(-3)? (does it even have a name?) I really doubt it’s UFD, but I won’t be really surprised if it is.

    • apgoucher says:

      It’s not a ring unless you append +d sqrt(6) to the expression, in which case it’s the ring Z[sqrt(-2),sqrt(-3)].

      Define the norm of an element to be the product of all four Galois conjugates (including itself). Then a quick search finds six units, ±1 and ±sqrt(-2)±sqrt(-3). Ouch.

      Anyway, this is not a UFD since:

      (2 + Sqrt[-2] + Sqrt[-3] + Sqrt[6])(2 – Sqrt[-2] + Sqrt[-3] – Sqrt[6]) = Sqrt[-3]^2

      and those are all irreducibles.

  3. “the only imaginary quadratic fields where the Fundamental Theorem of Arithmetic applies to the integral elements are Q[sqrt(-n)] for n = 1, 2, 3, 7, 11, 19, 43, 67, and 163.”

    All of those except 1 are prime. Coincidence? I’m guessing not. :)

  4. Thomas says:

    Does this have any relation to the fact that e^sqrt(163)*pi is approximately an integer?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s