Gauss Integers
Created | Updated Oct 3, 2007
Gauss 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) as a tool to solve some arithmetic problems.
The purpose of this Entry is to give an idea of Gauss integers and what one can do with them. We will also outline the similarity between Gauss 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 Gauss integers.
Definition
Gauss 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.
Definition
A Gauss integer is an expression of the form:
x + y i,
where x and y are integers. 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 Gauss integers with each other. For example:
1 + 2i and 5 - 7i
are Gauss integers. 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 Gauss integers:
ordinary integers, such as 42 or -5 (that is, 42 + 0i and -5 + 0i),
purely imaginary numbers such as 3 i or -i (meaning 0 + 3i and 0 - i),
not to forget 0 (the extreme case 0 + 0i).
Computing with Gauss Integers
One reason why Gauss integers are useful is because you are allowed to add and multiply them in the same way as you do with ordinary numbers. We will illustrate with an example what this 'same way' means.
Consider the Gauss 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 Gauss 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 like 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 Gauss integers! Specifically:
(1 + 2i)×(5 - 7i) = 19 + 3i.
Comparing Gauss 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 word, 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 Gauss Integer
Back to Gauss integers. We would like to have a notion of 'large' and 'small' Gauss 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 Gauss integer. Define the norm of x + y i to be the following number:
Norm(x + y i) = x² + y².
Comparing Gauss 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?
We have:
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.
Geometric Meaning
There is actually a way to draw pictures of Gauss 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 origin. In some sense, this is where an observer (that is, you!) is sitting, and everything else is described relatively to his or her position.
You can represent any Gauss integer x + y i by the point of coordinates (x,y) in this plane. Now, the norm of a Gauss integer x + y i is essentially given by the distance of the corresponding point to the origin3. Thus, 'larger' Gauss integers are represented by 'more distant' points. Also, if two Gauss integers have the 'same size', it means that the corresponding points are located on the same circle4.
Arithmetic of Gauss Integers
In this section, we will outline what arithmetic means in the context of Gauss integers, and point out some similarities with arithmetic as we know it.
Division with Remainder
Arithmetic is a part of mathematics which deals with 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 Gauss integers, one can also perform divisions with remainder5. Only, in this situation, the requirement that the remainder be 'smaller' than the divisor has to be understood using the Norm described in Section 2. In this context, saying that a Gauss 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 to the reader to check that all equalities are true.
We have proved in Section 1 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 Gauss Integers
Because of this division procedure, Gauss integers behave very much like ordinary integers. In particular, there are analogues of prime numbers, called prime Gauss integers. Loosely speaking, these are Gauss integers which cannot be divided by any smaller Gauss integer6; for this reason, such numbers are also called irreducible Gauss integers.
Prime Gauss 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 Gauss integer divides the product of two Gauss integers, then it must divide at least one of the Gauss integers.
Any non-zero Gauss integer can be written in a unique8 manner as a product of prime Gauss integers.
Examples
We give examples of prime and non-prime Gauss 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 Gauss integers,
3,7 are prime Gauss integers,
2,5,13 are not prime Gauss integers. Indeed, 2 = (1 + i)×(1 - i), 5 = (4 - i)×(4 + 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 Gauss integer' or 'ordinary prime number'. This is linked with the Two Squares theorem, which is stated in the next Section.
Applications
Gauss 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 Gauss integers might help you at all! Here are several examples of innocent-looking theorems which can be proved using Gauss integers.
The Two Squares Theorem
This is a result due to Fermat9. It gives a condition on ordinary prime numbers to 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,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,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, Gauss integers can provide a way to prove the theorem in the case n = 4.
Diophantine Equations
Diophantine equations are equations for which one seeks solutions which are integers. For example, Fermat's equation is a diophantine equation. Gauss 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.
