Become a fan of h2g2
Gaussian integers are numbers which look like, and in some ways behave like, ordinary integers. They are named after the German mathematician Carl Friedrich Gauss (1777-1855) and are used as a tool to solve some arithmetic problems.
The purpose of this Entry is to give an idea of Gaussian integers and what one can do with them. We will also outline the similarity between Gaussian integers and ordinary integers, and why they are useful for arithmetic. Finally we will give some examples of concrete1 problems which can be solved using Gaussian integers.
Gaussian integers can be defined as special cases of complex numbers. Since no prior knowledge of these is required, we will make all descriptions below fairly explicit.
A Gaussian integer is an expression of the form:
x + y i,where x and y are integers, and y is multiplied by i. For the moment, the letter 'i' in this expression is just a meaningless symbol. Readers familiar with complex numbers will recognise the so-called 'square root of -1': this property will become relevant later, when we try to multiply Gaussian integers by each other. Examples of Gaussian integers are:
1 + 2i and 5 - 7i
In the first case, x = 1 and y = 2. In the second case, x = 5 and y = -7. Of course, one may choose x or y to be zero, so there are also simpler-looking Gaussian integers:
ordinary integers, such as 42 or -5 (that is, 42 + 0i and -5 + 0i),
purely imaginary numbers such as 3i or -i (meaning 0 + 3i and 0 - i),
not to forget 0 (the extreme case 0 + 0i).
Computing with Gaussian Integers
One reason why Gaussian integers are useful is that you are allowed to add and multiply them in the same way as you do with ordinary numbers. We will illustrate with an example of what this 'same way' means.
Consider the Gaussian integers given in the first example: (1 + 2i) and (5 - 7i). You can add them very easily:
(1 + 2i) + (5 - 7i) = (1 + 5) + (2 - 7)i = 6 - 5i.In other words, you just add separately the bits with 'i' and the bits without 'i'.
The multiplication seems to be more tricky at first sight, but if you just follow simple rules as if you were dealing with ordinary numbers, nothing wrong can happen. Let us try to multiply the Gaussian integers (1 + 2i) and (5 - 7i). Here, the insecure reader may want to follow the computations with a pen and paper.
First, you have to use the usual expanding rules2:
(1 + 2i)×(5 - 7i) = 1×5 + 1×(-7i) + (2i)×5 + (2i)×(-7i).
Now you multiply all involved integers as usual and regroup all bits which can be grouped in an obvious manner:
1×5 + 1×(-7i) + (2i)×5 + (2i)×(-7i) = 5 - 7i + 10i -14×i² = 5 + 3i - 14×i².
The time has come to remember that 'i' is a square root of -1: in other words, i² = -1. Replace in the expression above and collect similar-looking terms:
5 + 3i - 14×i² = 5 + 3i - 14×(-1) = 5 + 3i + 14 = 19 + 3i.
We have just multiplied two Gaussian integers! Specifically:
(1 + 2i)×(5 - 7i) = 19 + 3i.
Comparing Gaussian Integers
Large and Small Integers
For ordinary integers, we have a very intuitive notion of 'large' and 'small', or rather 'larger' and 'smaller'. For instance, it seems natural to claim that 77 is larger than 42, or that 1 is smaller than 2.
Problems arise when you involve negative numbers: if you want to compare -77 and 42, then it is not clear which one is to be declared larger. If these were meant to be, for instance, temperatures, then you would say that -77 is lower than +42. If these meant altitudes, -77 would refer to a point which is further away from sea level than 42: in this sense, -77 could be considered to be 'larger' than 42. In other words, you don't mind whether it's up or down, the important feature is just how far away it is.
This is the point of view which we will adopt here: the sign doesn't matter, and -77 is considered to be larger than 42. We are looking at the 'absolute value' of numbers - in other words, their magnitude irrespective of the sign.
Norm of a Gaussian Integer
Back to Gaussian integers. We would like to have a notion of 'large' and 'small' Gaussian integers, but it is not clear how to do this. While it seems natural to say that 2007 + 1999i is larger than 5 + 7i, it is not quite obvious at first how one should compare 1 + 4i and 2 + 3i.
One way to do it is by means of the norm of a Gaussian integer. Define the norm of x + y i to be the following number:
Norm(x + y i) = x² + y².
Comparing Gaussian integers will mean comparing the norms. Let us give two examples before giving a geometric meaning to the norm.
Which one is 'smaller': 1 + 4i or 2 + 3i?
Norm(1 + 4i) = 1² + 4² = 1 + 16 = 17, and Norm(2 + 3i) = 2² + 3² = 13.
Thus, 2 + 3i is 'smaller' than 1 + 4i.
Which one is 'smaller': 7 + 6i or 2 + 9i?
You can compute as above: Norm(7 + 6i) = 85 and Norm(2 + 9i) = 85.
Thus, 7 + 6i has the 'same size' as 2 + 9i, even though they are different numbers.
There is actually a way to draw pictures of Gaussian integers. Take a plane equipped with a co-ordinate system given by two perpendicular axes (traditionally called 'x -axis' and 'y-axis'). These axes meet at a point called the origin. In some sense, this is where an observer (that is, you!) is sitting, and everything else is described relative to his or her position.
You can represent any Gaussian integer x + y i by the point of co-ordinates (x,y) in this plane. Now, the norm of a Gaussian integer x + y i is essentially given by the distance of the corresponding point to the origin3. Thus, 'larger' Gaussian integers are represented by 'more distant' points. Also, if two Gaussian integers have the 'same size', it means that the corresponding points are located on the same circle4.
Arithmetic of Gaussian Integers
In this section, we will outline what arithmetic means in the context of Gaussian integers, and point out some similarities with arithmetic as we know it.
Division with Remainder
One of the concepts dealt with in arithmetic is the idea of divisibility. For ordinary integers, we know what this means - for instance, 20 is divisible by 5 because 20 = 5×4. Yet it is not divisible by 7, because 20 ÷ 7 is not an integer. You can express this by means of a division with remainder: you can write:
20 = 7×2 + 6,
where the remainder (6) is smaller than 7, but non-zero. In the division 20 = 5×4, the remainder is zero.
For Gaussian integers, one can also perform divisions with the remainder5. Only, in this situation, the requirement that the remainder be 'smaller' than the divisor has to be understood using the Norm described earlier. In this context, saying that a Gaussian integer is divisible by another means the same as saying the remainder in the corresponding division is zero.
Let us just give two examples. We leave it as an exercise for the reader to check that all equalities are true.
We have proved earlier that 19 + 3i is divisible by 1 + 2i. Indeed, we computed: 19 + 3i = (1 + 2i)×(5 - 7i).
We want to divide (5 + 42i) by (4 + 2i). One can check that:
5 + 42i = (4 + 2i)×(5 + 7i) + (-1 + 4i),and the remainder (-1 + 4i) is smaller than the divisor (4 + 2i). Hence, 5 + 42i is not divisible by 4 + 2i.
Prime Gaussian integers
Because of this division procedure, Gaussian integers behave very much like ordinary integers. In particular, there are analogues of prime numbers, called prime Gaussian integers. Loosely speaking, these are Gaussian integers which cannot be divided by any smaller Gaussian integer6; for this reason, such numbers are also called irreducible Gaussian integers.
Prime Gaussian integers behave in many ways like prime numbers do. We quote as an example two major results involving these:
(Euclid's Lemma7): If a prime Gaussian integer divides the product of two Gaussian integers, then it must divide at least one of the Gaussian integers.
Any non-zero Gaussian integer can be written in a unique8 manner as a product of prime Gaussian integers.
We give examples of prime and non-prime Gaussian integers. Although one can painstakingly check the result by hand, it is easier to just believe the author of this Entry.
1 + i, -2 + i are prime Gaussian integers,
3 and 7 are prime Gaussian integers,
2, 5 and 13 are not prime Gaussian integers. Indeed, 2 = (1 + i)×(1 - i), 5 = (2 - i)×(2 + i) and 13 = (2 + 3i)×(2 - 3i).
The last two examples are all made of ordinary integers which are also ordinary prime numbers. This illustrates the fact that, when dealing with 'prime' numbers, it is important to always specify carefully whether one means 'prime Gaussian integer' or 'ordinary prime number'. This is linked with the Two Squares theorem, which is stated in the next section.
Gaussian integers are a very convenient tool to prove several mathematical results, even though these results concern only ordinary numbers. The tricky part is usually to imagine that using Gaussian integers might help you at all! Here are several examples of innocent-looking theorems which can be proved using Gaussian integers.
The Two Squares Theorem
This is a result due to Fermat9. It gives a condition where ordinary prime numbers can be decomposable as the sum of two squares:
Let p be an ordinary prime number, but p ≠ 2. Then p can be written as a sum of two squares if and only if p-1 is divisible by 4.
For instance, the numbers 5, 13 and 41 are prime numbers p such that p-1 is divisible by 4. One can check that:
5 = 1² + 2², 13 = 2² + 3², 41 = 4² + 5².
Also, the numbers 3, 7 and 1023 are prime numbers such that p-1 is not divisible by 4: according to the Two Squares theorem, you cannot write them as a sum of two squares. While this is fairly easy to check for 3 and 7, one can be happy to have such an easy criterion to use for 1023.
Fermat's Last Theorem
Also known as the Fermat-Wiles theorem, this is the famous result stating that:
It is impossible to find non-zero integers a, b, c satisfying the equation an + bn = cn, provided that n is an integer larger than two.
While it is a very difficult result to prove in full generality, it is a fairly classical academic exercise to prove some particular cases, for small values of the parameter n. For instance, Gaussian integers can provide a way to prove the theorem in the case n = 4.
Diophantine equations are equations for which one seeks solutions which are integers. For example, Fermat's equation is a diophantine equation. Gaussian integers are a convenient tool to solve many other examples. For instance:
There exist no non-zero integers a,b such that a³ = b² + 1.
In other words, the cube of an integer is never equal to the square of an integer plus one.