Gaussian integer: Difference between revisions

Revision as of 07:10, 6 September 2013

Latest revision as of 00:08, 26 August 2025

(239 intermediate revisions by more than 100 users not shown)

Line 1:

{{Short description|Complex number whose real and imaginary parts are both integers}}

In [[number theory]], a '''Gaussian integer''' is a [[complex number]] whose real and imaginary part are both [[integer]]s. The Gaussian integers, with ordinary [[addition]] and [[multiplication]] of [[complex numbers]], form an [[integral ___domain]], usually written as '''Z'''[''i'']. The Gaussian integers are a special case of the [[quadratic integer]]s. This ___domain does not have a [[total order]]ing that respects arithmetic.

{{distinguish|text=[[Gaussian integral]]}}

In [[number theory]], a '''Gaussian integer''' is a [[complex number]] whose real and imaginary parts are both [[integer]]s. The Gaussian integers, with ordinary [[addition]] and [[multiplication]] of [[complex number]]s, form an [[integral ___domain]], usually written as <math>\mathbf{Z}[i]</math> or <math>\Z[i].</math><ref name="Fraleigh 1976 286">{{harvtxt|Fraleigh|1976|p=286}}</ref>

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.

[[Image:Gaussian integer lattice.png|thumb|217px|Gaussian integers as [[lattice point]]s in the [[complex plane]]]]

Formally, Gaussian integers are [[algebraic integer]]s and form the setsimplest ring of [[quadratic integer]]s.

Gaussian integers are named after the German mathematician [[Carl Friedrich Gauss]].

:<math>\mathbb{Z}[i]=\{a+bi \mid a,b\in \mathbb{Z} \},\ \mbox{where}\ i = \sqrt{-1}.</math>

[[File:Gaussian integer lattice.svg|thumb|217px|Gaussian integers as [[integer lattice point]]s in the [[complex plane]]]]

Note that when they are considered within the [[complex plane]] the Gaussian integers may be seen to constitute the 2-dimensional [[integer lattice]].

==Basic definitions==

The [[Field norm|''(arithmetic or field) norm'']] of a Gaussian integer is the square of its (Euclidean) norm as a complex number and a [[natural number]] defined as

The Gaussian integers are the set<ref name="Fraleigh 1976 286"/>

:<math>\mathbf{Z}[i]=\{a+bi \mid a,b\in \mathbf{Z} \}, \qquad \text{ where } i^2 = -1.</math>

In other words, a Gaussian integer is a [[complex number]] such that its [[real part|real]] and [[imaginary part]]s are both [[integer]]s.

:<math>N \left(a+bi \right) = a^2+b^2 = (a+bi)\overline{(a+bi)} = (a+bi)(a-bi).</math>

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 {{math|2}}-dimensional [[square lattice]].

(Where the overline over "a+bi" refers to the [[complex conjugate]].)

The ''conjugate'' of a Gaussian integer {{math|''a'' + ''bi''}} is the Gaussian integer {{math|''a'' − ''bi''}}.

The norm is [[completely multiplicative function|multiplicative]], since the norm of complex numbers is multiplicative, i.e., one has

The [[field norm|''norm'']] of a Gaussian integer is its product with its conjugate.

:<math>N(z\cdot w) = N(z)\cdot N(w).</math>

:<math>N(a+bi) = (a+bi)(a-bi) = a^2+b^2.</math>

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 [[square number|squares]]. By the [[sum of two squares theorem]], a norm cannot have a factor <math>p^k</math> in its [[prime decomposition]] where <math>p \equiv 3 \pmod 4</math> and <math>k</math> is odd (in particular, a norm is not itself congruent to 3 modulo 4).

The latter can also be verified by a straightforward check. The [[unit (ring theory)|unit]]s of '''Z'''[''i''] are precisely those elements with norm 1, i.e. the elements 1, &minus;1, ''i'' and &minus;''i''.

The norm is [[completely multiplicative function|multiplicative]], that is, one has<ref>{{harvtxt|Fraleigh|1976|p=289}}</ref>

==As a principal ideal ___domain==

:<math>N(zw) = N(z)N(w),</math>

The Gaussian integers form a [[principal ideal ___domain]] with [[unit (ring theory)|unit]]s 1, &minus;1, ''i'', and &minus;''i''. If ''x'' is a Gaussian integer, the four numbers ''x'', ''ix'', &minus;''x'', and &minus;''ix'' are called the associates of ''x''. As for every principal ideal ___domain, the Gaussian integers form also a [[unique factorization ___domain]].

for every pair of Gaussian integers {{math|''z'', ''w''}}. This can be shown directly, or by using the multiplicative property of the modulus of complex numbers.

The [[unit (ring theory)|unit]]s 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, {{math|''i''}} and {{math|−''i''}}.<ref>{{harvtxt|Fraleigh|1976|p=288}}</ref>

The [[prime element]]s of '''Z'''[''i''] are also known as '''Gaussian primes'''. An associate of a Gaussian prime is also a Gaussian prime. The Gaussian primes are symmetric about the real and imaginary axes. The ''positive integer'' Gaussian primes are the [[prime numbers]] [[Congruence class|congruent to]]&nbsp;3 modulo&nbsp;4, {{OEIS|A002145}}. One should not refer to only these numbers as "the Gaussian primes", which refers to ''all'' the Gaussian primes, many of which do not lie in '''Z'''.<ref name="Gaussian Primes naming error">[http://oeis.org/A002145#COMMENT], OEIS sequence A002145 "COMMENT" section</ref>

==Euclidean division==

A Gaussian integer <math>a+bi</math> is a Gaussian prime if and only if either:

[[File:Gauss-euklid.svg|250px|thumb|Visualization of maximal distance to some Gaussian integer]]

* one of ''a'', ''b'' is zero and the other is a prime number of the form <math>4n+3</math> (with ''n'' a nonnegative integer) or its negative <math>-(4n+3)</math>, or

* both are nonzero and <math>a^2+b^2</math> is a prime number (which will ''not'' be of the form <math>4n+3</math>).

Gaussian integers have a [[Euclidean division]] (division with remainder) similar to that of [[integer]]s and [[polynomial]]s. 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 divisor]]s, [[Bézout's identity]], the [[principal ideal ___domain|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.

The following elaborates on these conditions.

A Euclidean division algorithm takes, in the ring of Gaussian integers, a dividend {{math|''a''}} and divisor {{math|''b'' ≠ 0}}, and produces a quotient {{math|''q''}} and remainder {{math|''r''}} such that

2 is a special case (in the language of [[algebraic number theory]], 2 is the only [[Ramification#In_algebraic_number_theory|ramified]] prime in '''Z'''[''i'']).

:<math>a=bq+r\quad \text{and} \quad N(r)<N(b).</math>

In fact, one may make the remainder smaller:

:<math>a=bq+r\quad \text{and} \quad N(r)\le \frac{N(b)}{2}.</math>

{{Anchor|unique remainder}}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 {{math|''x'' + ''iy'' {{=}} {{sfrac|''a''|''b''}}}}. There are unique integers {{math|''m''}} and {{math|''n''}} such that {{math|−{{sfrac|1|2}} < ''x'' − ''m'' ≤ {{sfrac|1|2}}}} and {{math|−{{sfrac|1|2}} < ''y'' − ''n'' ≤ {{sfrac|1|2}}}}, and thus {{math|''N''(''x'' − ''m'' + ''i''(''y'' − ''n'')) ≤ {{sfrac|1|2}}}}. Taking {{math|1=''q'' = ''m'' + ''in''}}, one has

The integer 2 factors as <math>2=(1+i)(1-i)=i(1-i)^2</math> as a Gaussian integer, the second factorisation (in which ''i'' is a unit) showing that 2 is divisible by the square of a Gaussian prime; it is the unique prime number with this property.

:<math>a = bq + r,</math>

with

:<math>r=b\bigl(x-m+ i(y-n)\bigr), </math>

and

:<math>N(r)\le \frac{N(b)}{2}.</math>

The choice of {{math|''x'' − ''m''}} and {{math|''y'' − ''n''}} 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 {{mvar|ξ}} to the closest Gaussian integer is at most {{math|{{sfrac|{{sqrt|2}}|2}}}}.<ref>{{harvtxt|Fraleigh|1976|p=287}}</ref>

==Principal ideals==

The necessary conditions can be stated as following: if a Gaussian integer is a Gaussian prime, then either its norm is a prime number, or its norm is a square of a prime number. This is because for any Gaussian integer <math>g</math>, notice

Since the ring {{math|''G''}} of Gaussian integers is a Euclidean ___domain, {{math|''G''}} is a [[principal ideal ___domain]], which means that every [[ideal (ring theory)|ideal]] of {{mvar|G}} is [[principal ideal|principal]]. Explicitly, an [[ideal (ring theory)|ideal]] {{mvar|I}} is a subset of a ring {{mvar|R}} such that every sum of elements of {{mvar|I}} and every product of an element of {{mvar|I}} by an element of {{mvar|R}} belong to {{mvar|I}}. An ideal is [[principal ideal|principal]] if it consists of all multiples of a single element {{math|''g''}}, that is, it has the form

:<math>g \mid g\bar{g} =N(g)</math>.

:<math>\{gx\mid x\in G\}.</math>

In this case, one says that the ideal is ''generated'' by {{math|''g''}} or that {{math|''g''}} is a ''generator'' of the ideal.

Every ideal {{math|''I''}} in the ring of the Gaussian integers is principal, because, if one chooses in {{math|''I''}} a nonzero element {{math|''g''}} of minimal norm, for every element {{math|''x''}} of {{math|''I''}}, the remainder of Euclidean division of {{math|''x''}} by {{math|''g''}} belongs also to {{math|''I''}} and has a norm that is smaller than that of {{math|''g''}}; because of the choice of {{math|''g''}}, this norm is zero, and thus the remainder is also zero. That is, one has {{math|1=''x'' = ''qg''}}, where {{math|''q''}} is the quotient.

Here <math>\mid</math> means “divides”; that is, <math>x \mid y</math> if <math>x</math> is a divisor of <math>y</math>.

For any {{math|''g''}}, the ideal generated by {{math|''g''}} is also generated by any ''associate'' of {{math|''g''}}, that is, {{math|''g'', ''gi'', −''g'', −''gi''}}; 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.

Now <math>N(g)</math> is an integer, and so can be factored as a product <math>p_{1}p_{2}\cdots p_{n}</math> of prime numbers, by the [[fundamental theorem of arithmetic]]. By definition of prime element, if <math>g</math> is a Gaussian prime, then it divides (in '''Z'''[''i'']) some <math>p_i</math>. Also, <math>\bar g</math> divides

:<math>\overline{p_i}=p_i</math>, so <math>N(g) = g\bar{g} \mid p_{i}^{2}</math> in '''Z'''.

{{Anchor|selected associates}}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 {{math|1=''g'' = ''a'' + ''bi''}} has an odd norm {{math|''a''² + ''b''²}}, then one of {{math|''a''}} and {{math|''b''}} is odd, and the other is even. Thus {{math|''g''}} has exactly one associate with a real part {{math|''a''}} 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 {{math|2 + 2''i''}} is one. In fact, as {{math|1=''N''(2 + 2''i'') = 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. Multiplying {{math|''g''}} by the inverse of this unit, one finds an associate that has one as a remainder, when divided by {{math|2 + 2''i''}}.

This gives only two options: either the norm of <math>g</math> is a prime number, or the square of a prime number.

If the norm of {{math|''g''}} is even, then either {{math|1=''g'' = 2^''k''''h''}} or {{math|1=''g'' = 2^''k''''h''(1 + ''i'')}}, where {{math|''k''}} is a positive integer, and {{math|''N''(''h'')}} is odd. Thus, one chooses the associate of {{math|''g''}} for getting a {{math|''h''}} which fits the choice of the associates for elements of odd norm.

If in fact <math>N(g)=p^2</math> for some prime number <math>p</math>, then both <math>g</math> and <math>\overline{g}</math> divide <math>p^2</math>. Neither can be a unit, and so

:<math>g=pu</math> and <math>\overline{g}=p\overline{u}</math>

==Gaussian primes==

where <math>u</math> is a unit. This is to say that either <math>a=0</math> or <math>b=0</math>, where <math>g=a+bi</math>.

As the Gaussian integers form a [[principal ideal ___domain]], they also form a [[unique factorization ___domain]]. This implies that a Gaussian integer is [[irreducible element|irreducible]] (that is, it is not the product of two [[unit (ring theory)|non-unit]]s) if and only if it is [[prime element|prime]] (that is, it generates a [[prime ideal]]).

The [[prime element]]s of {{math|'''Z'''[''i'']}} 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).

However, not every prime number <math>p</math> is a Gaussian prime. 2 is not because <math>2=(1+i)(1-i)</math>. Neither are prime numbers of the form <math>4n+1</math> because [[Fermat's theorem on sums of two squares]] assures us they can be written <math>a^2+b^2</math> for integers <math>a</math> and <math>b</math>, and <math>a^2+b^2 = (a+bi)(a-bi)</math>. The only type of prime numbers remaining are of the form <math>4n+3</math>.

A positive integer is a Gaussian prime if and only if it is a [[prime number]] that is [[Congruence class|congruent to]] 3 [[modulo operator|modulo]] 4 (that is, it may be written {{math|4''n'' + 3}}, with {{math|''n''}} a nonnegative integer) {{OEIS|A002145}}. The other prime numbers are not Gaussian primes, but each is the product of two conjugate Gaussian primes.

Prime numbers of the form <math>4n+3</math> are also Gaussian primes. For suppose <math>g=p+0i</math> for <math>p=4n+3</math>, and it can be factored <math>g=hk</math>. Then <math>p^2=N(g)=N(h)N(k)</math>. If the factorization is non-trivial, then <math>N(h)=N(k)=p</math>. But no sum of squares of integers can be written <math>4n+3</math>. So the factorization must have been trivial and <math>g</math> is a Gaussian prime.

If <math>g</math> is aA Gaussian integer whose norm is {{math|''a'' prime+ number, then <math>g</math>''bi''}} is a Gaussian prime, becauseif theand normonly isif multiplicative.either:

*one of {{math|''a'', ''b''}} is zero and the [[absolute value]] of the other is a prime number of the form {{math|4''n'' + 3}} (with {{mvar|n}} a nonnegative integer), or

*both are nonzero and {{math|''a''² + ''b''²}} is a prime number (which will ''never'' be of the form {{math|4''n'' + 3}}).

In other words, a Gaussian integer {{math|''m''}} is a Gaussian prime if and only if either its norm is a prime number, or {{math|''m''}} is the product of a unit ({{math|±1, ±''i''}}) and a prime number of the form {{math|4''n'' + 3}}.

===As an integral closure===

The ring of Gaussian integers is the [[integral closure]] of '''Z''' in the [[field (mathematics)|field]] of [[Gaussian rational]]s '''Q'''(''i'') consisting of the complex numbers whose real and imaginary part are both [[rational number|rational]].

It follows that there are three cases for the factorization of a prime natural number {{math|''p''}} in the Gaussian integers:

===As a Euclidean ___domain===

*If {{math|''p''}} is congruent to 3 modulo 4, then it is a Gaussian prime; in the language of [[algebraic number theory]], {{math|''p''}} is said to be [[inert prime|inert]] in the Gaussian integers.

It is easy to see graphically that every [[complex number]] is within <math>\frac{\sqrt 2}{2}</math> units of a Gaussian integer.

*If {{math|''p''}} 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); {{math|''p''}} is said to be a [[decomposed prime]] in the Gaussian integers. For example, {{math|1=5 = (2 + ''i'')(2 − ''i'')}} and {{math|1=13 = (3 + 2''i'')(3 − 2''i'')}}.

*If {{math|1=''p'' = 2}}, we have {{math|2 {{=}} (1 + ''i'')(1 − ''i'') {{=}} ''i''(1 − ''i'')²}}; that is, 2 is the product of the square of a Gaussian prime by a unit; it is the unique [[ramification (mathematics)#In algebraic number theory|ramified prime]] in the Gaussian integers.

==Unique factorization==

Put another way, every complex number (and hence every Gaussian integer) has a maximal distance of

As for every [[unique factorization ___domain]], every Gaussian integer may be factored as a product of a [[unit (ring theory)|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).

:<math>\frac{\sqrt 2}{2}\sqrt{N(z)}</math>

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 [[#selected associates|choices described above]], the resulting unique factorization has the form

units to some multiple of z, where z is any Gaussian integer; this turns '''Z'''[''i''] into a [[Euclidean ___domain]], where

:<math>vu(z1+i)^{e_0}{p_1}^{e_1}\cdots = N(z). \{p_k}^{e_k},</math>

where {{math|''u''}} is a unit (that is, {{math|''u'' ∈ {1, −1, ''i'', −''i''}{{void}}}}), {{math|''e''₀}} and {{math|''k''}} are nonnegative integers, {{math|''e''₁, …, ''e_k''}} are positive integers, and {{math|''p''₁, …, ''p_k''}} are distinct Gaussian primes such that, depending on the choice of selected associates,

*either {{math|''p_k'' {{=}} ''a_k'' + ''ib_k''}} with {{math|''a''}} odd and positive, and {{math|''b''}} even,

*or the remainder of the Euclidean division of {{math|''p_k''}} by {{math|2 + 2''i''}} equals 1 (this is Gauss's original choice<ref>{{harvtxt|Gauss|1831|p=546}}</ref>).

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 {{nowrap|3 × 7 × 11}}, while it is {{nowrap|(−1) × (−3) × (−7) × (−11)}} with the second choice.

==Gaussian rationals==

==Historical background==

The [[field (mathematics)|field]] of [[Gaussian rational]]s 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 number|rational]].

The ring of Gaussian integers is the [[integral closure]] of the integers in the Gaussian rationals.

The ring of Gaussian integers was introduced by [[Carl Friedrich Gauss]] in his second monograph on [[quartic reciprocity]] (1832) (see [http://www.ems-ph.org/journals/show_pdf.php?issn=0013-6018&vol=53&iss=1&rank=2]). The theorem of [[quadratic reciprocity]] (which he had first succeeded in proving in 1796) relates the solvability of the congruence ''x''² ≡ ''q'' (mod ''p'') to that of ''x''² ≡ ''p'' (mod ''q''). Similarly, cubic reciprocity relates the solvability of ''x''³ ≡ ''q'' (mod ''p'') to that of ''x''³ ≡ ''p'' (mod ''q''), and biquadratic (or quartic) reciprocity is a relation between ''x''⁴ ≡ ''q'' (mod ''p'') and ''x''⁴ ≡ ''p'' (mod ''q''). 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).

This implies that Gaussian integers are [[quadratic integer]]s and that a Gaussian rational is a Gaussian integer, if and only if it is a solution of an equation

In a footnote he notes that the [[Eisenstein integer]]s are the natural ___domain for stating and proving results on [[cubic reciprocity]] and indicates that similar extensions of the integers are the appropriate domains for studying higher reciprocity laws.

:<math>x^2 +cx+d=0,</math>

with {{math|''c''}} and {{math|''d''}} integers. In fact {{math|''a'' + ''bi''}} is solution of the equation

:<math>x^2-2ax+a^2+b^2,</math>

and this equation has integer coefficients if and only if {{math|''a''}} and {{math|''b''}} are both integers.

=={{Anchor|gcd}}Greatest common divisor==

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.

As for any [[unique factorization ___domain]], a ''[[greatest common divisor]] (gcd)'' of two Gaussian integers {{math|''a'', ''b''}} is a Gaussian integer {{math|''d''}} that is a common divisor of {{math|''a''}} and {{math|''b''}}, which has all common divisors of {{math|''a''}} and {{math|''b''}} as divisor. That is (where {{math|{{!}}}} denotes the [[divisibility]] relation),

*{{math|''d'' {{!}} ''a''}} and {{math|''d'' {{!}} ''b''}}, and

==Unsolved problems==

*{{math|''c'' {{!}} ''a''}} and {{math|''c'' {{!}} ''b''}} implies {{math|''c'' {{!}} ''d''}}.

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 {{math|''a''}} and {{math|''b''}} is a [[ideal (ring theory)#Ideal generated by a set|generator]] of the [[ideal (ring theory)|ideal]] generated by {{math|''a''}} and {{math|''b''}} (this characterization is valid for [[principal ideal ___domain]]s, but not, in general, for unique factorization domains).

[[Image:gauss-primes-768x768.png|170px|thumb|Repartition in the plane of the small Gaussian primes]]

The greatest common divisor of two Gaussian integers is not unique, but is defined up to the multiplication by a [[unit (ring theory)|unit]]. That is, given a greatest common divisor {{math|''d''}} of {{math|''a''}} and {{math|''b''}}, the greatest common divisors of {{math|''a''}} and {{math|''b''}} are {{math|''d'', −''d'', ''id''}}, and {{math|−''id''}}.

Most of the unsolved problems are related to the repartition in the plane of the Gaussian primes.

There are several ways for computing a greatest common divisor of two Gaussian integers {{math|''a''}} and {{math|''b''}}. When one knows the prime factorizations of {{math|''a''}} and {{math|''b''}},

* [[Gauss's circle problem]] does not deal with the Gaussian integers ''per se'', but instead asks for the number of [[lattice point]]s inside a circle of a given radius centered at the origin. This is equivalent to determining the number of Gaussian integers with norm less than a given value.

:<math>a = i^k\prod_m {p_m}^{\nu_m}, \quad b = i^n\prod_m {p_m}^{\mu_m},</math>

where the primes {{math|''p_m''}} are pairwise non associated, and the exponents {{math|''μ_m''}} non-associated, a greatest common divisor is

:<math>\prod_m {p_m}^{\lambda_m},</math>

with

:<math>\lambda_m = \min(\nu_m, \mu_m).</math>

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 {{math|(''a'', ''b'')}} by {{math|(''b'', ''r'')}}, where {{math|''r''}} is the remainder of the Euclidean division of {{math|''a''}} by {{math|''b''}}, and repeating this operation until getting a zero remainder, that is a pair {{math|(''d'', 0)}}. This process terminates, because, at each step, the norm of the second Gaussian integer decreases. The resulting {{math|''d''}} is a greatest common divisor, because (at each step) {{math|''b''}} and {{math|1=''r'' = ''a'' − ''bq''}} have the same divisors as {{math|''a''}} and {{math|''b''}}, and thus the same greatest common divisor.

There are also conjectures and unsolved problems about the Gaussian primes. Two of them are:

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 {{math|''N''(''d'')}} of the greatest common divisor of {{math|''a''}} and {{math|''b''}} is a common divisor of {{math|''N''(''a'')}}, {{math|''N''(''b'')}}, and {{math|''N''(''a'' + ''b'')}}. When the greatest common divisor {{math|''D''}} of these three integers has few factors, then it is easy to test, for common divisor, all Gaussian integers with a norm dividing {{math|''D''}}.

* The real and imaginary axes have the infinite set of Gaussian primes 3, 7, 11, 19, ... and their associates. Are there any other lines that have infinitely many Gaussian primes on them? In particular, are there infinitely many Gaussian primes of the form 1+''ki''?<ref>Ribenboim, Ch.III.4.D Ch. 6.II, Ch. 6.IV (Hardy & Littlewood's conjecture E and F)</ref>

For example, if {{math|1=''a'' = 5 + 3''i''}}, and {{math|1=''b'' = 2 − 8''i''}}, one has {{math|1=''N''(''a'') = 34}}, {{math|1=''N''(''b'') = 68}}, and {{math|1=''N''(''a'' + ''b'') = 74}}. As the greatest common divisor of the three norms is 2, the greatest common divisor of {{math|''a''}} and {{math|''b''}} has 1 or 2 as a norm. As a gaussian integer of norm 2 is necessary associated to {{math|1 + ''i''}}, and as {{math|1 + ''i''}} divides {{math|''a''}} and {{math|''b''}}, then the greatest common divisor is {{math|1 + ''i''}}.

* Is it possible to walk to infinity using the Gaussian primes as stepping stones and taking steps of bounded length? This is known as the [[Gaussian moat]] problem; it was posed in 1962 by [[Basil Gordon]] and remains unsolved.<ref>{{cite journal

| last1 = Gethner | first1 = Ellen

If {{math|''b''}} is replaced by its conjugate {{math|1=''b'' = 2 + 8''i''}}, then the greatest common divisor of the three norms is 34, the norm of {{math|''a''}}, thus one may guess that the greatest common divisor is {{math|''a''}}, that is, that {{math|''a'' {{!}} ''b''}}. In fact, one has {{math|1=2 + 8''i'' = (5 + 3''i'')(1 + ''i'')}}.

| last2 = Wagon | first2 = Stan | author2-link = Stan Wagon

| last3 = Wick | first3 = Brian

=={{Anchor|congruences}}Congruences and residue classes==

| doi = 10.2307/2589708

Given a Gaussian integer {{math|''z''₀}}, called a ''modulus'', two Gaussian integers {{math|''z''₁,''z''₂}} are ''congruent modulo'' {{math|''z''₀}}, if their difference is a multiple of {{math|''z''₀}}, that is if there exists a Gaussian integer {{math|''q''}} such that {{math|''z''₁ − ''z''₂ {{=}} ''qz''₀}}. In other words, two Gaussian integers are congruent modulo {{math|''z''₀}}, if their difference belongs to the [[ideal (ring theory)|ideal]] generated by {{math|''z''₀}}. This is denoted as {{math|''z''₁ ≡ ''z''₂ (mod ''z''₀)}}.

| issue = 4

| journal = [[The American Mathematical Monthly]]

The congruence modulo {{math|''z''₀}} is an [[equivalence relation]] (also called a [[congruence relation]]), which defines a [[partition of a set|partition]] of the Gaussian integers into [[equivalence class]]es, called here [[congruence class]]es or ''residue classes''. The set of the residue classes is usually denoted {{math|'''Z'''[''i'']/''z''₀'''Z'''[''i'']}}, or {{math|'''Z'''[''i'']/{{angbr|''z''₀}}}}, or simply {{math|'''Z'''[''i'']/''z''₀}}.

| mr = 1614871 | zbl=0946.11002

| pages = 327–337

The residue class of a Gaussian integer {{math|''a''}} is the set

| title = A stroll through the Gaussian primes

:<math> \bar a := \left\{ z \in \mathbf{Z}[i] \mid z \equiv a \pmod{z_0} \right\}</math>

| volume = 105

of all Gaussian integers that are congruent to {{math|''a''}}. It follows that {{math|{{overline|''a''}} {{=}} {{overline|''b''}}}} [[if and only if]] {{math|''a'' ≡ ''b'' (mod ''z''₀)}}.

| year = 1998}}</ref><ref>{{cite book |last=Guy | first=Richard K. | authorlink=Richard K. Guy | title=Unsolved problems in number theory | publisher=[[Springer-Verlag]] |edition=3rd | year=2004 |isbn=978-0-387-20860-2 | zbl=1058.11001 | pages=55–57}}</ref>

Addition and multiplication are compatible with congruences. This means that {{math|''a''₁ ≡ ''b''₁ (mod ''z''₀)}} and {{math|''a''₂ ≡ ''b''₂ (mod ''z''₀)}} imply {{math|''a''₁ + ''a''₂ ≡ ''b''₁ + ''b''₂ (mod ''z''₀)}} and {{math|''a''₁''a''₂ ≡ ''b''₁''b''₂ (mod ''z''₀)}}.

This defines well-defined [[operation (mathematics)|operations]] (that is independent of the choice of representatives) on the residue classes:

:<math>\bar a + \bar b := \overline{a+b}\quad \text{and}\quad \bar a \cdot\bar b := \overline{ab}.</math>

With these operations, the residue classes form a [[commutative ring]], the [[quotient ring]] of the Gaussian integers by the ideal generated by {{math|''z''₀}}, which is also traditionally called the ''residue class ring modulo''&nbsp;{{math|''z''₀}} (for more details, see [[Quotient ring]]).

===Examples===

*There are exactly two residue classes for the modulus {{math|1 + ''i''}}, namely {{math|{{overline|0}} {{=}} {0, ±2, ±4,…,±1 ± ''i'', ±3 ± ''i'',…}{{void}}}} (all multiples of {{math|1 + ''i''}}), and {{math|{{overline|1}} {{=}} {±1, ±3, ±5,…, ±''i'', ±2 ± ''i'',…}{{void}}}}, which form a checkerboard pattern in the complex plane. These two classes form thus a ring with two elements, which is, in fact, a [[field (mathematics)|field]], the unique (up to an isomorphism) field with two elements, and may thus be identified with the [[modular arithmetic|integers modulo 2]]. These two classes may be considered as a generalization of the partition of integers into even and odd integers. Thus one may speak of ''even'' and ''odd'' Gaussian integers (Gauss divided further even Gaussian integers into ''even'', that is divisible by 2, and ''half-even'').

*For the modulus 2 there are four residue classes, namely {{math|{{overline|0}}, {{overline|1}}, {{overline|''i''}}, {{overline|1 + ''i''}}}}. These form a ring with four elements, in which {{math|1=''x'' = −''x''}} for every {{math|''x''}}. Thus this ring is not [[isomorphic]] with the ring of integers modulo 4, another ring with four elements. One has {{math|{{overline|1 + ''i''}}² {{=}} {{overline|0}}}}, and thus this ring is not the [[finite field]] with four elements, nor the [[direct product]] of two copies of the ring of integers modulo 2.

*For the modulus {{math|2 + 2i {{=}} (''i'' − 1)³}} there are eight residue classes, namely {{math|{{overline|0}}, {{overline|±1}}, {{overline|±''i''}}, {{overline|1 ± ''i''}}, {{overline|2}}}}, whereof four contain only even Gaussian integers and four contain only odd Gaussian integers.

===Describing residue classes===

[[File:Gauss-Restklassen-wiki.png|250px|thumb|All 13 residue classes with their minimal residues (blue dots) in the square {{math|''Q''₀₀}} (light green background) for the modulus {{math|''z''₀ {{=}} 3 + 2''i''}}. One residue class with {{math|''z'' {{=}} 2 − 4''i'' ≡ −''i'' (mod ''z''₀)}} is highlighted with yellow/orange dots.]]

Given a modulus {{math|''z''₀}}, all elements of a residue class have the same remainder for the Euclidean division by {{math|''z''₀}}, provided one uses the division with unique quotient and remainder, which is described [[#unique remainder|above]]. Thus enumerating the residue classes is equivalent with enumerating the possible remainders. This can be done geometrically in the following way.

In the [[complex plane]], one may consider a [[square grid]], whose squares are delimited by the two lines

:<math>\begin{align}

V_s&=\left\{ \left. z_0\left(s-\tfrac12 +ix\right) \right\vert x\in \mathbf R\right\} \quad \text{and} \\

H_t&=\left\{ \left. z_0\left(x+i\left(t-\tfrac12\right)\right) \right\vert x\in \mathbf R\right\},

\end{align}</math>

with {{math|''s''}} and {{math|''t''}} integers (blue lines in the figure). These divide the plane in [[semi-open interval|semi-open]] squares (where {{math|''m''}} and {{math|''n''}} are integers)

:<math>Q_{mn}=\left\{(s+it)z_0 \left\vert s \in \left [m - \tfrac12, m + \tfrac12\right), t \in \left[n - \tfrac12, n + \tfrac12 \right)\right.\right\}.</math>

The semi-open intervals that occur in the definition of {{math|''Q_mn''}} have been chosen in order that every complex number belong to exactly one square; that is, the squares {{math|''Q_mn''}} form a [[partition (set theory)|partition]] of the complex plane. One has

:<math>Q_{mn} = (m+in)z_0+Q_{00}=\left\{(m+in)z_0+z\mid z\in Q_{00}\right\}.</math>

This implies that every Gaussian integer is congruent modulo {{math|''z''₀}} to a unique Gaussian integer in {{math|''Q''₀₀}} (the green square in the figure), which its remainder for the division by {{math|''z''₀}}. In other words, every residue class contains exactly one element in {{math|''Q''₀₀}}.

The Gaussian integers in {{math|''Q''₀₀}} (or in its [[boundary (topology)|boundary]]) are sometimes called ''minimal residues'' because their norm are not greater than the norm of any other Gaussian integer in the same residue class (Gauss called them ''absolutely smallest residues'').

From this one can deduce by geometrical considerations, that the number of residue classes modulo a Gaussian integer {{math|''z''₀ {{=}} ''a'' + ''bi''}} equals its norm {{math|''N''(''z''₀) {{=}} ''a''² + ''b''²}} (see below for a proof; similarly, for integers, the number of residue classes modulo {{math|''n''}} is its absolute value {{math|{{abs|''n''}}}}).

{{math proof|title = Proof|drop=hidden|proof=

The relation {{math|''Q_mn'' {{=}} (''m'' + ''in'')''z''₀ + ''Q''₀₀}} means that all {{math|''Q_mn''}} are obtained from {{math|''Q''₀₀}} by [[translation (geometry)|translating]] it by a Gaussian integer. This implies that all {{math|''Q_mn''}} have the same area {{math|''N'' {{=}} ''N''(''z''₀)}}, and contain the same number {{math|''n_g''}} of Gaussian integers.

Generally, the number of grid points (here the Gaussian integers) in an arbitrary square with the area {{math|''A''}} is {{math|''A'' + ''Θ''({{sqrt|''A''}})}} (see [[Big theta]] for the notation). If one considers a big square consisting of {{math|''k'' × ''k''}} squares {{math|''Q_mn''}}, then it contains {{math|''k''²''N'' + ''O''(''k''{{sqrt|''N''}})}} grid points. It follows {{math|''k''²''n_g'' {{=}} ''k''²''N'' + ''Θ''(''k''{{sqrt|''N''}})}}, and thus {{math|''n_g'' {{=}} ''N'' + ''Θ''({{sfrac|{{sqrt|''N''}}|''k''}})}}, after a division by {{math|''k''²}}. Taking the limit when {{math|''k''}} tends to the infinity gives {{math|''n_g'' {{=}} ''N'' {{=}} ''N''(''z''₀)}}.

}}

===Residue class fields===

The residue class ring modulo a Gaussian integer {{math|''z''₀}} is a [[field (mathematics)|field]] if and only if <math>z_0</math> is a Gaussian prime.

If {{math|''z''₀}} is a decomposed prime or the ramified prime {{math|1 + ''i''}} (that is, if its norm {{math|''N''(''z''₀)}} 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, {{math|''N''(''z''₀)}}). It is thus [[isomorphic]] to the field of the integers modulo {{math|''N''(''z''₀)}}.

If, on the other hand, {{math|''z''₀}} is an inert prime (that is, {{math|''N''(''z''₀) {{=}} ''p''²}} is the square of a prime number, which is congruent to 3 modulo 4), then the residue class field has {{math|''p''²}} elements, and it is an [[field extension|extension]] of degree 2 (unique, up to an isomorphism) of the [[prime field]] with {{math|''p''}} elements (the integers modulo {{math|''p''}}).

==Primitive residue class group and Euler's totient function==

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 the ''primitive residue class group'' (also called [[multiplicative group of integers modulo n|multiplicative group of integers modulo {{math|''n''}}]]) and [[Euler's totient function]]. The primitive residue class group of a modulus {{math|''z''}} is defined as the subset of its residue classes, which contains all residue classes {{math|{{overline|''a''}}}} that are coprime to {{math|''z''}}, i.e. {{math|(''a'',''z'') {{=}} 1}}. Obviously, this system builds a [[multiplicative group]]. The number of its elements shall be denoted by {{math|''ϕ''(''z'')}} (analogously to Euler's totient function {{math|''φ''(''n'')}} for integers {{math|''n''}}).

For Gaussian primes it immediately follows that {{math|''ϕ''(''p'') {{=}} {{abs|''p''}}² − 1}} and for arbitrary composite Gaussian integers

:<math>z = i^k\prod_m {p_m}^{\nu_m}</math>

[[Euler's totient function|Euler's product formula]] can be derived as

:<math>\phi(z) =\prod_{m\, (\nu_m > 0)} \bigl|{p_m}^{\nu_m}\bigr|^2 \left( 1 - \frac 1{|p_m|{}^2} \right) = |z|^2\prod_{p_m|z}\left( 1 - \frac 1{|p_m|{}^2} \right)</math>

where the product is to build over all prime divisors {{math|''p_m''}} of {{math|''z''}} (with {{math|''ν_m'' > 0}}). Also the important [[Euler's theorem|theorem of Euler]] can be directly transferred:

: For all {{math|''a''}} with {{math|(''a'',''z'') {{=}} 1}}, it holds that {{math|''a''^{''ϕ''(''z'')} ≡ 1 (mod ''z'')}}.

==Historical background==

The ring of Gaussian integers was introduced by [[Carl Friedrich Gauss]] in his second monograph on [[quartic reciprocity]] (1832).<ref>{{harvtxt|Kleiner|1998}}</ref> The theorem of [[quadratic reciprocity]] (which he had first succeeded in proving in 1796) relates the solvability of the congruence {{math|''x''² ≡ ''q'' (mod ''p'')}} to that of {{math|''x''² ≡ ''p'' (mod ''q'')}}. Similarly, cubic reciprocity relates the solvability of {{math|''x''³ ≡ ''q'' (mod ''p'')}} to that of {{math|''x''³ ≡ ''p'' (mod ''q'')}}, and biquadratic (or quartic) reciprocity is a relation between {{math|''x''⁴ ≡ ''q'' (mod ''p'')}} and {{math|''x''⁴ ≡ ''p'' (mod ''q'')}}. 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 the [[Eisenstein integer]]s are the natural ___domain for stating and proving results on [[cubic 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.

==Unsolved problems==

[[File:gauss-primes-768x768.png|170px|thumb|The distribution of the small Gaussian primes in the complex plane]]

Most of the unsolved problems are related to distribution of Gaussian primes in the plane.

*[[Gauss's circle problem]] does not deal with the Gaussian integers per se, but instead asks for the number of [[integer lattice point]]s inside a circle of a given radius centered at the origin. This is equivalent to determining the number of Gaussian integers with norm less than a given value.

There are also conjectures and unsolved problems about the Gaussian primes. Two of them are:

*The real and imaginary axes have the infinite set of Gaussian primes 3, 7, 11, 19, ... and their associates. Are there any other lines that have infinitely many Gaussian primes on them? In particular, are there infinitely many Gaussian primes of the form {{math|1 + ''ki''}}?<ref>Ribenboim, Ch.III.4.D Ch. 6.II, Ch. 6.IV (Hardy & Littlewood's conjecture E and F)</ref>

*Is it possible to walk to infinity using the Gaussian primes as stepping stones and taking steps of a uniformly bounded length? This is known as the [[Gaussian moat]] problem; it was posed in 1962 by [[Basil Gordon]] and remains unsolved.<ref>{{cite journal |last1= Gethner |first1= Ellen |last2= Wagon |first2= Stan |author2-link= Stan Wagon |last3= Wick |first3= Brian |doi= 10.2307/2589708 |issue= 4 |journal= [[The American Mathematical Monthly]] |mr= 1614871 |zbl=0946.11002 |pages= 327–337 |title= A stroll through the Gaussian primes |volume= 105 |year= 1998|jstor= 2589708 }}</ref><ref>{{cite book |last=Guy |first=Richard K. |author-link=Richard K. Guy |title=Unsolved problems in number theory |publisher=[[Springer-Verlag]] |edition=3rd |year=2004 |isbn=978-0-387-20860-2 |zbl=1058.11001 |pages=55–57}}</ref>

==See also==

* [[QuadraticAlgebraic integer]]

* [[HurwitzCyclotomic quaternionfield]]

* [[Eisenstein integer]]

* [[DirichletEisenstein integerprime]]

* [[AlgebraicHurwitz integerquaternion]]

* [[Proofs of Fermat's theorem on sums of two squares]]

* [[Proofs of quadratic reciprocity]]

*[[Quadratic integer]]

* [[Splitting of prime ideals in Galois extensions]] describes the structure of prime ideals in the Gaussian integers

*[[Splitting of prime ideals in Galois extensions]] describes the structure of prime ideals in the Gaussian integers

* [[Table of Gaussian integer factorizations]]

*[[Table of Gaussian integer factorizations]]

==Notes==

{{Reflist}}

{{reflist}}

==References==

* {{citation|first=C. F. |last=Gauss, |year=1831|url=https://babel.hathitrust.org/cgi/pt?id=mdp.39015073697180&view=1up&seq=285|title=Theoria residuorum biquadraticorum. Commentatio secunda., |journal=Comm. Soc. Reg. Sci. Göttingen |volume=7 (1832) 1-34|pages=89–148}}; reprinted in Werke, Georg Olms Verlag, Hildesheim, 1973, pp.&nbsp;93–148. A German translation of this paper is available online in ″H. Maser (ed.): ''[https://archive.org/details/carlfriedrichga00gausgoog Carl Friedrich Gauss’ Arithmetische Untersuchungen über höhere Arithmetik.]'' Springer, Berlin 1889, pp.&nbsp;534″.

*{{citation |first1= John B. |last1= Fraleigh |year= 1976 |isbn= 0-201-01984-1 |title= A First Course In Abstract Algebra |edition= 2nd |publisher= [[Addison-Wesley]] |___location= Reading}}

<!-- Note that this is not the Israel Kleiner in wikipedia -->

* {{cite journal | url=httphttps://www.ems-ph.orgpress/journals/show_pdf.php?issn=0013-6018&vol=53&iss=1&rank=2em/articles/664 | title=From Numbers to Rings: The Early History of Ring Theory | first1=Israel | last1=Kleiner | journal=[[Elem. Math.]] | volume=53 |number=1 | doi=10.1007/s000170050029 | year=1998 | pages=18–35 | zbl=0908.16001|doi-access=free }} <!-- *** This is NOT the Israel Kleiner in Wikipedia. *** -->

*{{cite book | last1 = Ribenboim | first1 = Paulo | authorlinkauthor-link=Paulo Ribenboim | title = The New Book of Prime Number Records | edition=3rd | publisher= Springer | ___location = New York | date = 1996 | isbn = 0-387-94457-5 | zbl=0856.11001 }}

*{{cite journal |author=Henry G. Baker |year=1993 |title=Complex Gaussian Integers for "Gaussian Graphics" |journal=ACM SIGPLAN Notices |volume=28 |issue=11 |pages=22–27 |doi=10.1145/165564.165571|s2cid=8083226 }}

==External links==

*[https://web.archive.org/web/20120306225505/http://www.imocompendium.com/index.php?options=mbb%7Ctekstkut&page=0&art=extensions_ddj%7Cf&ttn=Dushan%20D%3Bjukic1%7C%20Arithmetic%20in%20Quadratic%20Fields%7CN%2FA&knj=&p=3nbbw45001 IMO Compendium] text on quadratic extensions and Gaussian Integers in problem solving

* [http://www.alpertron.com.ar/GAUSSIAN.HTM www.alpertron.com.ar/GAUSSIAN.HTM] is a Java applet that evaluates expressions containing Gaussian integers and factors them into Gaussian primes.

*Keith Conrad, [https://kconrad.math.uconn.edu/blurbs/ugradnumthy/Zinotes.pdf The Gaussian Integers].

* [http://www.alpertron.com.ar/GAUSSPR.HTM www.alpertron.com.ar/GAUSSPR.HTM] is a Java applet that features a graphical view of Gaussian primes.

* Henry G. Baker (1993) Complex Gaussian Integers for 'Gaussian Graphics', ACM SIGPLAN Notices, Vol. 28, Issue 11. [http://portal.acm.org/citation.cfm?doid=165564.165571 DOI 10.1145/165564.165571] [http://home.pipeline.com/~hbaker1/Gaussian.html (html)]

* [http://www.imocompendium.com/index.php?options=mbb|tekstkut&page=0&art=extensions_ddj|f&ttn=Dushan%20D;jukic1|%20Arithmetic%20in%20Quadratic%20Fields|N/A&knj=&p=3nbbw45001 IMO Compendium] text on quadratic extensions and Gaussian Integers in problem solving

* {{Mathworld|title= Landau's Problems|urlname= LandausProblems}}

{{Algebraic numbers}}

{{Prime number classes}}

[[Category:Cyclotomic fields]]

[[Category:Algebraic numbers]]

[[Category:Cyclotomic fields]]

[[Category:Lattice points]]

[[Category:Quadratic irrational numbers]]

[[Category:Integers]]

[[Category:Complex numbers]]