Innumber theory, aGaussian integer is acomplex number whose real and imaginary parts are bothintegers. The Gaussian integers, with ordinaryaddition andmultiplication ofcomplex numbers, form anintegral domain, usually written as or[1]
Gaussian integers share many properties with integers: they form aEuclidean domain, and thus have aEuclidean division and aEuclidean algorithm; this impliesunique factorization and many related properties. However, Gaussian integers do not have atotal order that respects arithmetic.
Gaussian integers arealgebraic integers and form the simplest ring ofquadratic integers.
Gaussian integers are named after the German mathematicianCarl Friedrich Gauss.
The Gaussian integers are the set[1][2]
In other words, a Gaussian integer is acomplex number such that itsreal andimaginary parts are bothintegers.Since the Gaussian integers are closed under addition and multiplication, they form acommutative ring, which is asubring of the field of complex numbers. It is thus anintegral domain. When considered within thecomplex plane, the Gaussian integers constitute the2-dimensionalsquare lattice.
Theconjugate of a complex numbera +bi is the complex numbera −bi. Thenorm of a Gaussian integera +bi is its product with its conjugate:
The norm of a Gaussian integer is thus the square of itsabsolute value as a complex number. The norm of a Gaussian integer is a nonnegative integer, which is a sum of twosquares. By thesum of two squares theorem, a norm cannot have a factor in itsprime decomposition where and is odd (in particular, a norm is not itself congruent to 3 modulo 4).
The norm ismultiplicative, that is, one has[3]
for every pair of Gaussian integersz,w. This can be shown directly, or by using the multiplicative property of the modulus of complex numbers.
Theunits of the ring of Gaussian integers (that is the Gaussian integers whosemultiplicative inverse is also a Gaussian integer) are precisely the Gaussian integers with norm 1, that is, 1, −1,i and−i.[4]
Gaussian integers have aEuclidean division (division with remainder) similar to that ofintegers andpolynomials. This makes the Gaussian integers aEuclidean domain, and implies that Gaussian integers share with integers and polynomials many important properties such as the existence of aEuclidean algorithm for computinggreatest common divisors,Bézout's identity, theprincipal ideal property,Euclid's lemma, theunique factorization theorem, and theChinese remainder theorem, all of which can be proved using only Euclidean division.
A Euclidean division algorithm takes, in the ring of Gaussian integers, a dividenda and divisorb ≠ 0, and produces a quotientq and remainderr 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 thecomplex number quotientx +iy =a/b. There are unique integersm andn such that−1/2 <x −m ≤1/2 and−1/2 <y −n ≤1/2, and thusN(x −m +i(y −n)) ≤1/2. Takingq =m +in, one has
with
and
The choice ofx −m andy −n in asemi-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√2/2.[5]
Since the ringG of Gaussian integers is a Euclidean domain,G is aprincipal ideal domain, which means that everyideal ofG isprincipal. Explicitly, anidealI is a subset of a ringR such that every sum of elements ofI and every product of an element ofI by an element ofR belong toI. An ideal isprincipal if it consists of all multiples of a single elementg, that is, it has the form
In this case, one says that the ideal isgenerated byg or thatg is agenerator of the ideal.
Every idealI in the ring of the Gaussian integers is principal, because, if one chooses inI a nonzero elementg of minimal norm, for every elementx ofI, the remainder of Euclidean division ofx byg belongs also toI and has a norm that is smaller than that ofg; because of the choice ofg, this norm is zero, and thus the remainder is also zero. That is, one hasx =qg, whereq is the quotient.
For anyg, the ideal generated byg is also generated by anyassociate ofg, that is,g,gi, −g, −gi; no other element generates the same ideal. As all the generators of an ideal have the same norm, thenorm 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 theg =a +bi has an odd norma2 +b2, then one ofa andb is odd, and the other is even. Thusg has exactly one associate with a real parta 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 by2 + 2i is one. In fact, asN(2 + 2i) = 8, 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. Multiplyingg by the inverse of this unit, one finds an associate that has one as a remainder, when divided by2 + 2i.
If the norm ofg is even, then eitherg = 2kh org = 2kh(1 +i), wherek is a positive integer, andN(h) is odd. Thus, one chooses the associate ofg for getting ah which fits the choice of the associates for elements of odd norm.
As the Gaussian integers form aprincipal ideal domain, they also form aunique factorization domain. This implies that a Gaussian integer isirreducible (that is, it is not the product of twonon-units) if and only if it isprime (that is, it generates aprime ideal).
Theprime elements ofZ[i] are also known asGaussian 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 aprime number that iscongruent to 3modulo 4 (that is, it may be written4n + 3, withn a nonnegative integer) (sequenceA002145 in theOEIS). The other prime numbers are not Gaussian primes, but each is the product of two conjugate Gaussian primes.
A Gaussian integera +bi is a Gaussian prime if and only if either:
In other words, a Gaussian integerm is a Gaussian prime if and only if either its norm is a prime number, orm is the product of a unit (±1, ±i) and a prime number of the form4n + 3.
It follows that there are three cases for the factorization of a prime natural numberp in the Gaussian integers:
As for everyunique factorization domain, every Gaussian integer may be factored as a product of aunit 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 eachequivalence 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 thechoices described above, the resulting unique factorization has the form
whereu is a unit (that is,u ∈ {1, −1,i, −i}),e0 andk are nonnegative integers,e1, …,ek are positive integers, andp1, …,pk are distinct Gaussian primes such that, depending on the choice of selected associates,
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 is3 × 7 × 11, while it is(−1) × (−3) × (−7) × (−11) with the second choice.
Thefield ofGaussian rationals is thefield of fractions of the ring of Gaussian integers. It consists of the complex numbers whose real and imaginary part are bothrational.
The ring of Gaussian integers is theintegral closure of the integers in the Gaussian rationals.
This implies that Gaussian integers arequadratic integers and that a Gaussian rational is a Gaussian integer, if and only if it is a solution of an equation
withc andd integers. In facta +bi is solution of the equation
and this equation has integer coefficients if and only ifa andb are both integers.
As for anyunique factorization domain, agreatest common divisor (gcd) of two Gaussian integersa,b is a Gaussian integerd that is a common divisor ofa andb, which has all common divisors ofa andb as divisor. That is (where| denotes thedivisibility relation),
Thus,greatest is meant relatively to the divisibility relation, and not for an ordering of the ring (for integers, both meanings ofgreatest coincide).
More technically, a greatest common divisor ofa andb is agenerator of theideal generated bya andb (this characterization is valid forprincipal 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 aunit. That is, given a greatest common divisord ofa andb, the greatest common divisors ofa andb ared, −d,id, and−id.
There are several ways for computing a greatest common divisor of two Gaussian integersa andb. When one knows the prime factorizations ofa andb,
where the primespm are pairwise non associated, and the exponentsμm non-associated, a greatest common divisor is
with
Unfortunately, except in simple cases, the prime factorization is difficult to compute, andEuclidean algorithm leads to a much easier (and faster) computation. This algorithm consists of replacing of the input(a,b) by(b,r), wherer is the remainder of the Euclidean division ofa byb, and repeating this operation until getting a zero remainder, that is a pair(d, 0). This process terminates, because, at each step, the norm of the second Gaussian integer decreases. The resultingd is a greatest common divisor, because (at each step)b andr =a −bq have the same divisors asa andb, 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 normN(d) of the greatest common divisor ofa andb is a common divisor ofN(a),N(b), andN(a +b). When the greatest common divisorD of these three integers has few factors, then it is easy to test, for common divisor, all Gaussian integers with a norm dividingD.
For example, ifa = 5 + 3i, andb = 2 − 8i, one hasN(a) = 34,N(b) = 68, andN(a +b) = 74. As the greatest common divisor of the three norms is 2, the greatest common divisor ofa andb has 1 or 2 as a norm. As a gaussian integer of norm 2 is necessarily associated to1 +i, and as1 +i dividesa andb, then the greatest common divisor is1 +i.
Ifb is replaced by its conjugateb = 2 + 8i, then the greatest common divisor of the three norms is 34, the norm ofa, thus one may guess that the greatest common divisor isa, that is, thata |b. In fact, one has2 + 8i = (5 + 3i)(1 +i).
Given a Gaussian integerz0, called amodulus, two Gaussian integersz1,z2 arecongruent moduloz0, if their difference is a multiple ofz0, that is if there exists a Gaussian integerq such thatz1 −z2 =qz0. In other words, two Gaussian integers are congruent moduloz0, if their difference belongs to theideal generated byz0. This is denoted asz1 ≡z2 (modz0).
The congruence moduloz0 is anequivalence relation (also called acongruence relation), which defines apartition of the Gaussian integers intoequivalence classes, called herecongruence classes orresidue classes. The set of the residue classes is usually denotedZ[i]/z0Z[i], orZ[i]/⟨z0⟩, or simplyZ[i]/z0.
The residue class of a Gaussian integera is the set
of all Gaussian integers that are congruent toa. It follows thata =bif and only ifa ≡b (modz0).
Addition and multiplication are compatible with congruences. This means thata1 ≡b1 (modz0) anda2 ≡b2 (modz0) implya1 +a2 ≡b1 +b2 (modz0) anda1a2 ≡b1b2 (modz0).This defines well-definedoperations (that is independent of the choice of representatives) on the residue classes:
With these operations, the residue classes form acommutative ring, thequotient ring of the Gaussian integers by the ideal generated byz0, which is also traditionally called theresidue class ring modulo z0 (for more details, seeQuotient ring).
Given a modulusz0, all elements of a residue class have the same remainder for the Euclidean division byz0, provided one uses the division with unique quotient and remainder, which is describedabove. Thus enumerating the residue classes is equivalent with enumerating the possible remainders. This can be done geometrically in the following way.
In thecomplex plane, one may consider asquare grid, whose squares are delimited by the two lines
withs andt integers (blue lines in the figure). These divide the plane insemi-open squares (wherem andn are integers)
The semi-open intervals that occur in the definition ofQmn have been chosen in order that every complex number belong to exactly one square; that is, the squaresQmn form apartition of the complex plane. One has
This implies that every Gaussian integer is congruent moduloz0 to a unique Gaussian integer inQ00 (the green square in the figure), which its remainder for the division byz0. In other words, every residue class contains exactly one element inQ00.
The Gaussian integers inQ00 (or in itsboundary) are sometimes calledminimal residues because their norm are not greater than the norm of any other Gaussian integer in the same residue class (Gauss called themabsolutely smallest residues).
From this one can deduce by geometrical considerations, that the number of residue classes modulo a Gaussian integerz0 =a +bi equals its normN(z0) =a2 +b2 (see below for a proof; similarly, for integers, the number of residue classes modulon is its absolute value|n|).
The relationQmn = (m +in)z0 +Q00 means that allQmn are obtained fromQ00 bytranslating it by a Gaussian integer. This implies that allQmn have the same areaN =N(z0), and contain the same numberng of Gaussian integers.
Generally, the number of grid points (here the Gaussian integers) in an arbitrary square with the areaA isA +Θ(√A) (seeBig theta for the notation). If one considers a big square consisting ofk ×k squaresQmn, then it containsk2N +O(k√N) grid points. It followsk2ng =k2N +Θ(k√N), and thusng =N +Θ(√N/k), after a division byk2. Taking the limit whenk tends to the infinity givesng =N =N(z0).
The residue class ring modulo a Gaussian integerz0 is afield if and only if is a Gaussian prime.
Ifz0 is a decomposed prime or the ramified prime1 +i (that is, if its normN(z0) is a prime number, which is either 2 or a prime congruent to 1 modulo 4), then the residue class field has a prime number of elements (that is,N(z0)). It is thusisomorphic to the field of the integers moduloN(z0).
If, on the other hand,z0 is an inert prime (that is,N(z0) =p2 is the square of a prime number, which is congruent to 3 modulo 4), then the residue class field hasp2 elements, and it is anextension of degree 2 (unique, up to an isomorphism) of theprime field withp elements (the integers modulop).
Many theorems (and their proofs) for moduli of integers can be directly transferred to moduli of Gaussian integers, if one replaces the absolute value of the modulus by the norm. This holds especially for theprimitive residue class group (also calledmultiplicative group of integers modulon) andEuler's totient function. The primitive residue class group of a modulusz is defined as the subset of its residue classes, which contains all residue classesa that are coprime toz, i.e.(a,z) = 1. Obviously, this system builds amultiplicative group. The number of its elements shall be denoted byϕ(z) (analogously to Euler's totient functionφ(n) for integersn).
For Gaussian primes it immediately follows thatϕ(p) = |p|2 − 1 and for arbitrary composite Gaussian integers
Euler's product formula can be derived as
where the product is to build over all prime divisorspm ofz (withνm > 0). Also the importanttheorem of Euler can be directly transferred:
The ring of Gaussian integers was introduced byCarl Friedrich Gauss in his second monograph onquartic reciprocity (1832).[7] The theorem ofquadratic reciprocity (which he had first succeeded in proving in 1796) relates the solvability of the congruencex2 ≡q (modp) to that ofx2 ≡p (modq). Similarly, cubic reciprocity relates the solvability ofx3 ≡q (modp) to that ofx3 ≡p (modq), and biquadratic (or quartic) reciprocity is a relation betweenx4 ≡q (modp) andx4 ≡p (modq). Gauss discovered that the law of biquadratic reciprocity and its supplements were more easily stated and proved as statements about "whole complex numbers" (i.e. the Gaussian integers) than they are as statements about ordinary whole numbers (i.e. the integers).
In a footnote he notes that theEisenstein integers are the natural domain for stating and proving results oncubic reciprocity and indicates that similar extensions of the integers are the appropriate domains for studying higher reciprocity laws.
This paper not only introduced the Gaussian integers and proved they are a unique factorization domain, it also introduced the terms norm, unit, primary, and associate, which are now standard in algebraic number theory.
Most of the unsolved problems are related to distribution of Gaussian primes in the plane.
There are also conjectures and unsolved problems about the Gaussian primes. Two of them are:
