Gaussian integers are complex numbers of the form
where and are integers.
Like other complex numbers, Gaussian integers can be added, subtracted, and multiplied . For example:
Here are some examples and properties of Gaussian integers:
are all Gaussian integers, while , , and are not.
The conjugate of is , which is again a Gaussian integer.
The norm of is , which is a non-negative integer.
The absolute value of a Gaussian integer is the (positive) square root of its norm: .
There are no positive or negative Gaussian integers and one cannot say that one is less than another. One can, however, compare their norms.
One of the most useful concepts for Gaussian integers is the norm
The norm is always a non-negative integer, and is multiplicative (i.e., the norm of the product is the product of the norms). We say that a Gaussian integer is a unit if is also a Gaussian integer. A Gaussian integer is a multiple of Gaussian integer if
for some Gaussian integer . In this case we say that divides , and use the notation
A Gaussian integer is called prime if it is not equal to a product of two non-unit Gaussian integers. Otherwise, it is called composite. Clearly, multiplying by a unit does not change primality. Note that a number may be prime as a usual integer, but composite as a Gaussian integer (for example ).
In the following sequence of theorems, we give a classification of Gaussian units and Gaussian primes.
Theorem 1. For a Gaussian integer the following three statements are equivalent:
1. is a unit, i.e. is a Gaussian integer.
3. is or .
Proof. Suppose . Then , so . Since and and are integers, we have .
for integers and . Then and, similarly, , implying one of or must be and the other must be .
This can be checked directly:
Now that we know all the units, we want to classify all Gaussian primes. Here is a first result in this direction.
Theorem 2. Suppose is a Gaussian prime and its norm is even. Then and , up to a unit, is .
Proof. Note that . The integers and are either both even or both odd. In the first case, is divisible by , which is divisible by . In the second case, is divisible by . So in both cases is divisible by . Because is prime, it must equal , where is a unit.
The following theorems are classical results from elementary number theory that are important for the theory of Gaussian integers. We will skip their proofs.
Theorem 3. Suppose is an odd prime. Then the congruence has a solution if and only if .
Theorem 4. (Fermat's Two-Square Theorem) An odd prime can be expressed as for integers and if and only if
(Brahmagupta-Fibonacci Identity) Given two numbers, each of which can be written as the sum of two squares, their product can also be written as the sum of two squares. The identity is:
The above theorems suggest the following:
a) If is a prime and , then and are Gaussian primes.
b) If is a prime in then it is a prime in .
Proof. Recall that the norm of a product of two Gaussian integers equals the product of their norms.
a) The norm of is , so if is equal to a product of two Gaussian integers, one of the factors must have norm , which makes it a unit.
b) If is a product of non-unit Gaussian integers, then, because its norm is , the factors must have norm . This is impossible by Theorem 4.
Finally, we give a proof of the classification of Gaussian primes based on the uniqueness of prime factorization of Gaussian integers. Another, self-contained proof is given in the Worked Examples.
Theorem 6. (Classification of Gaussian Primes) All Gaussian primes are those described in Theorem 5.
Proof. Suppose is a Gaussian prime. Consider
We can decompose into a product of usual primes. Then for the prime , write and for the primes write . Because of the uniqueness of the decomposition into a product of primes, must be one of the primes defined above, proving the theorem.
1. Find all Gaussian primes with norm up to
Solution: By the classification, up to units, is the only Gaussian prime with norm . If is prime of the form , the norm is , so we must have . For primes is or . Note that , and . Therefore, the Gaussian primes with norm up to are, in increasing order of norm:
2. Suppose is a Gaussian integer and suppose divides . Show .
Solution: If then consider . We have . From Theorem 3, this is impossible. So , implying and . Therefore,
3. Suppose is a Gaussian integer, and divides . Suppose Show that either or (or both).
Solution: Note that . If , then, as in the Example 2, , so both and divide If consider an integer such that . Then . Similarly, for some integer . Because
either or . In the first case, for an integer we have and . So is a multiple of , so is a multiple of . Similarly, in the second case is a multiple of
4. Show that all Gaussian primes are among those described in Theorem 2 and Theorem 5.
Solution: Suppose is a Gaussian prime, and is its norm. Because it is not zero and not a unit, . From Theorem 2, Example 2 and Example 3, is a multiple of one of the known Gaussian primes. Because is a prime, the ratio must be a unit, which implies the result.
The Fundamental Theorem of Arithmetic states that every positive integer can be uniquely expressed as a product of positive primes, up to the order of multiplication. Can we create a system where it is not true?
Example. Consider the set of all positive integers of the form , where is a positive integer. A product of any two such integers in is again an integer of this form. We will call an integer from prime if it is not a product of two smaller integers from , and the integer is called composite otherwise. By definition, every integer from is a product of primes from . However, the product may not be uniquely expressed. For example, we can see that are all primes in , and we have .
Of course, is very different from integers or natural numbers, but this showcases the fact that there must be a reason for why the prime decomposition is unique. The deep reason is the existence of the division algorithm that produces a remainder that is strictly smaller than the divisor. Interestingly, the same property holds for the Gaussian integers, with respect to the norm:
Lemma 1. (Division algorithm) Suppose and are Gaussian integers, . Then there exist Gaussian integers and such that and
Proof. Dividing by , we get a number where and are rational (not necessarily integers). Suppose is the closest integer to and is the closest integer to . Denote . Then So if then
This property is called the Euclidean domain property. In fact, in every Euclidean domain the factorization into a product of primes is unique. We present an argument for the Gaussian integers, which can be easily adapted for the regular integers. The following lemma is needed in the proof, and is known as Euclid's Lemma when restricted to integers.
Lemma 2. Suppose is a prime Gaussian integer and divides for some Gaussian integers and . Then or .
Proof. Consider the set of all Gaussian integers of the form for arbitrary Gaussian integers and . This is also known as the ideal generated by and . It has the property that any sum or difference of two elements from is in , and any Gaussian integral multiple of an element from is in . Suppose is the element of with the smallest possible non-zero absolute value. From Lemma 1, every element of is a multiple of , otherwise the non-zero remainder, which also lies in , will have a smaller absolute value. In particular, . Because is prime, either is a unit or is a unit. In the first case, is a multiple of , so it is a multiple of . In the second case, multiplying by , we express as . Multiplying by , we get . Because this implies that .
Theorem 1. (Unique Factorization Property) Every non-zero Gaussian integer can be uniquely expressed as a product of Gaussian primes, up to ordering and multiplication by units.
Proof. First we prove that a factorization into a product of primes always exists. If not, take to be the Gaussian integer with smallest absolute value which is not a product of primes. Then is not a prime, so a product of two non-zero, non-unit Gaussian integers. Since norms are multiplicative and positive integers, must have smaller norm than , so they are both products of primes. If so, is also the product of primes, hence a contradiction.
Now we will prove the uniqueness. Suppose that is the Gaussian integer with smallest norm that admits two substantially different decompositions into a product of primes:
Applying lemma 2 to , , we get that either or . In the second case we apply it again, and again... as a result we get that must divide for some . Because the number is prime, this means that is up to a unit . Then we can cancel them out, and get a new with two different prime decompositions and smaller norm. This contradicts our choice of .
Another property of the Euclidean domain, very much related to the Unique Decomposition, is the existence of the Euclidean Algorithm for finding the greatest common divisor. This algorithm, as well as the uniqueness of prime decomposition for the usual integers goes all the way back to Euclid's Elements!
The Euclidean Algorithm works as follows: Suppose and are (Gaussian) integers. We order the pair so that and call it . Then we use it to get new pairs, as follows. At every step, we divide by . If the remainder is zero, we stop, and claim that the greatest common divisor of and , denoted . If there is a non-zero remainder, i.e. we take and continue.
1) For every initial pair , the Euclidean algorithm terminates after a finite number of steps.
2) The number divides both and , and every (Gaussian) integer that divides both and must divide .
Proof. 1) For the Gaussian integers, note that , and the norm, being a positive integer, cannot decrease indefinitely.
Proof. 2) Suppose . Then it clearly divides and . Because and it divides and . Continuing in this manner, we prove that divides and .
If divides both and , then it divides and . Continuing in this manner, we prove that divides .
We finish this post by reproducing one of the recent proofs of the Fermat Two Squares Theorem, due to Don Zagier. An involution is such map from a set to itself, that for all elements .
Don Zagier's One-Sentence Proof of Fermat Two Squares Theorem. (Amer. Math. Monthly 97 (1990), no. 2, 144).
The involution on the finite set defined by
has exactly one fixed point, so is odd and the involution defined by also has a fixed point.