In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as or
Gaussian integers share many properties with integers: they form a Euclidean domain, and thus have a Euclidean division and a Euclidean algorithm; this implies unique factorization and many related properties. However, Gaussian integers do not have a total order that respects arithmetic.
Gaussian integers are algebraic integers and form the simplest ring of quadratic integers.
Gaussian integers are named after the German mathematician Carl Friedrich Gauss.
Basic definitions The Gaussian integers are the set
In other words, a Gaussian integer is a complex number such that its real and imaginary parts are both integers. Since the Gaussian integers are closed under addition and multiplication, they form a commutative ring, which is a subring of the field of complex numbers. It is thus an integral domain. When considered within the complex plane, the Gaussian integers constitute the -dimensional square lattice.
The conjugate of a complex number is the complex number . The norm of a Gaussian integer is its product with its conjugate:
The norm of a Gaussian integer is thus the square of its absolute value as a complex number. The norm of a Gaussian integer is a nonnegative integer, which is a sum of two squares. By the sum of two squares theorem, a norm cannot have a factor in its prime decomposition where and is odd (in particular, a norm is not itself congruent to 3 modulo 4).
The norm is multiplicative, that is, one has
for every pair of Gaussian integers . This can be shown directly, or by using the multiplicative property of the modulus of complex numbers.
The units of the ring of Gaussian integers (that is the Gaussian integers whose multiplicative inverse is also a Gaussian integer) are precisely the Gaussian integers with norm 1, that is, 1, −1, and .
Euclidean division
Gaussian integers have a Euclidean division (division with remainder) similar to that of integers and polynomials. This makes the Gaussian integers a Euclidean domain, and implies that Gaussian integers share with integers and polynomials many important properties such as the existence of a Euclidean algorithm for computing greatest common divisors, Bézout's identity, the principal ideal property, Euclid's lemma, the unique factorization theorem, and the Chinese remainder theorem, all of which can be proved using only Euclidean division.
A Euclidean division algorithm takes, in the ring of Gaussian integers, a dividend and divisor , and produces a quotient and remainder such that
In fact, one may make the remainder smaller:
Even with this better inequality, the quotient and the remainder are not necessarily unique, but one may refine the choice to ensure uniqueness.
To prove this, one may consider the complex number quotient . There are unique integers and such that and , and thus . Taking , one has
with
and
The choice of and in a semi-open interval is required for uniqueness. This definition of Euclidean division may be interpreted geometrically in the complex plane (see the figure), by remarking that the distance from a complex number to the closest Gaussian integer is at most .
Principal ideals Since the ring of Gaussian integers is a Euclidean domain, is a principal ideal domain, which means that every ideal of is principal. Explicitly, an ideal is a subset of a ring such that every sum of elements of and every product of an element of by an element of belong to . An ideal is principal if it consists of all multiples of a single element , that is, it has the form
In this case, one says that the ideal is generated by or that is a generator of the ideal.
Every ideal in the ring of the Gaussian integers is principal, because, if one chooses in a nonzero element of minimal norm, for every element of , the remainder of Euclidean division of by belongs also to and has a norm that is smaller than that of ; because of the choice of , this norm is zero, and thus the remainder is also zero. That is, one has , where is the quotient.
For any , the ideal generated by is also generated by any associate of , that is, ; no other element generates the same ideal. As all the generators of an ideal have the same norm, the norm of an ideal is the norm of any of its generators.
In some circumstances, it is useful to choose, once for all, a generator for each ideal. There are two classical ways for doing that, both considering first the ideals of odd norm. If the has an odd norm , then one of and is odd, and the other is even. Thus has exactly one associate with a real part that is odd and positive. In his original paper, Gauss made another choice, by choosing the unique associate such that the remainder of its division by is one. In fact, as , the norm of the remainder is not greater than 4. As this norm is odd, and 3 is not the norm of a Gaussian integer, the norm of the remainder is one, that is, the remainder is a unit. Multiplying by the inverse of this unit, one finds an associate that has one as a remainder, when divided by .
If the norm of is even, then either or , where is a positive integer, and is odd. Thus, one chooses the associate of for getting a which fits the choice of the associates for elements of odd norm.
Gaussian primes As the Gaussian integers form a principal ideal domain, they also form a unique factorization domain. This implies that a Gaussian integer is irreducible (that is, it is not the product of two non-units) if and only if it is prime (that is, it generates a prime ideal).
The prime elements of are also known as Gaussian primes. An associate of a Gaussian prime is also a Gaussian prime. The conjugate of a Gaussian prime is also a Gaussian prime (this implies that Gaussian primes are symmetric about the real and imaginary axes).
A positive integer is a Gaussian prime if and only if it is a prime number that is congruent to 3 modulo 4 (that is, it may be written , with a nonnegative integer) . The other prime numbers are not Gaussian primes, but each is the product of two conjugate Gaussian primes.
A Gaussian integer is a Gaussian prime if and only if either: one of is zero and the absolute value of the other is a prime number of the form (with a nonnegative integer), or both are nonzero and is a prime number (which will never be of the form ).
In other words, a Gaussian integer is a Gaussian prime if and only if either its norm is a prime number, or is the product of a unit () and a prime number of the form .
It follows that there are three cases for the factorization of a prime natural number in the Gaussian integers: If is congruent to 3 modulo 4, then it is a Gaussian prime; in the language of algebraic number theory, is said to be inert in the Gaussian integers. If is congruent to 1 modulo 4, then it is the product of a Gaussian prime by its conjugate, both of which are non-associated Gaussian primes (neither is the product of the other by a unit); is said to be a decomposed prime in the Gaussian integers. For example, and . If , we have ; that is, 2 is the product of the square of a Gaussian prime by a unit; it is the unique ramified prime in the Gaussian integers.
Unique factorization As for every unique factorization domain, every Gaussian integer may be factored as a product of a unit and Gaussian primes, and this factorization is unique up to the order of the factors, and the replacement of any prime by any of its associates (together with a corresponding change of the unit factor).
If one chooses, once for all, a fixed Gaussian prime for each equivalence class of associated primes, and if one takes only these selected primes in the factorization, then one obtains a prime factorization which is unique up to the order of the factors. With the choices described above, the resulting unique factorization has the form
where is a unit (that is, ), and are nonnegative integers, are positive integers, and are distinct Gaussian primes such that, depending on the choice of selected associates, either with odd and positive, and even, or the remainder of the Euclidean division of by equals 1 (this is Gauss's original choice). An advantage of the second choice is that the selected associates behave well under products for Gaussian integers of odd norm. On the other hand, the selected associate for the real Gaussian primes are negative integers. For example, the factorization of 231 in the integers, and with the first choice of associates is , while it is with the second choice.
Gaussian rationals The field of Gaussian rationals is the field of fractions of the ring of Gaussian integers. It consists of the complex numbers whose real and imaginary part are both rational.
The ring of Gaussian integers is the integral closure of the integers in the Gaussian rationals.
This implies that Gaussian integers are quadratic integers and that a Gaussian rational is a Gaussian integer, if and only if it is a solution of an equation
with and integers. In fact is solution of the equation
and this equation has integer coefficients if and only if and are both integers.
Greatest common divisor As for any unique factorization domain, a greatest common divisor (gcd) of two Gaussian integers is a Gaussian integer that is a common divisor of and , which has all common divisors of and as divisor. That is (where denotes the divisibility relation),
and , and and implies . Thus, greatest is meant relatively to the divisibility relation, and not for an ordering of the ring (for integers, both meanings of greatest coincide).
More technically, a greatest common divisor of and is a generator of the ideal generated by and (this characterization is valid for principal ideal domains, but not, in general, for unique factorization domains).
The greatest common divisor of two Gaussian integers is not unique, but is defined up to the multiplication by a unit. That is, given a greatest common divisor of and , the greatest common divisors of and are , and .
There are several ways for computing a greatest common divisor of two Gaussian integers and . When one knows the prime factorizations of and ,
where the primes are pairwise non associated, and the exponents non-associated, a greatest common divisor is
with
Unfortunately, except in simple cases, the prime factorization is difficult to compute, and Euclidean algorithm leads to a much easier (and faster) computation. This algorithm consists of replacing of the input by , where is the remainder of the Euclidean division of by , and repeating this operation until getting a zero remainder, that is a pair . This process terminates, because, at each step, the norm of the second Gaussian integer decreases. The resulting is a greatest common divisor, because (at each step) and have the same divisors as and , and thus the same greatest common divisor.
This method of computation works always, but is not as simple as for integers because Euclidean division is more complicated. Therefore, a third method is often preferred for hand-written computations. It consists in remarking that the norm of the greatest common divisor of and is a common divisor of , , and . When the greatest common divisor of these three integers has few factors, then it is easy to test, for common divisor, all Gaussian integers with a norm dividing .
For example, if , and , one has , , and . As the greatest common divisor of the three norms is 2, the greatest common divisor of and has 1 or 2 as a norm. As a gaussian integer of norm 2 is necessarily associated to , and as divides and , then the greatest common divisor is .
If is replaced by its conjugate , then the greatest common divisor of the three norms is 34, the norm of , thus one may guess that the greatest common divisor is , that is, that . In fact, one has .