Editing Gaussian integer (section)

=={{Anchor|congruences}}Congruences and residue classes==
Given a Gaussian integer {{math|''z''<sub>0</sub>}}, called a ''modulus'', two Gaussian integers {{math|''z''<sub>1</sub>,''z''<sub>2</sub>}} are ''congruent modulo'' {{math|''z''<sub>0</sub>}}, if their difference is a multiple of {{math|''z''<sub>0</sub>}}, that is if there exists a Gaussian integer {{math|''q''}} such that {{math|''z''<sub>1</sub> − ''z''<sub>2</sub> {{=}} ''qz''<sub>0</sub>}}. In other words, two Gaussian integers are congruent modulo {{math|''z''<sub>0</sub>}}, if their difference belongs to the [[ideal (ring theory)|ideal]] generated by {{math|''z''<sub>0</sub>}}. This is denoted as {{math|''z''<sub>1</sub> ≡ ''z''<sub>2</sub> (mod ''z''<sub>0</sub>)}}.

The congruence modulo {{math|''z''<sub>0</sub>}} 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''<sub>0</sub>'''Z'''[''i'']}}, or {{math|'''Z'''[''i'']/{{angbr|''z''<sub>0</sub>}}}}, or simply {{math|'''Z'''[''i'']/''z''<sub>0</sub>}}.

The residue class of a Gaussian integer {{math|''a''}} is the set
:<math> \bar a := \left\{ z \in \mathbf{Z}[i] \mid z \equiv a \pmod{z_0} \right\}</math>
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''<sub>0</sub>)}}.

Addition and multiplication are compatible with congruences. This means that {{math|''a''<sub>1</sub> ≡ ''b''<sub>1</sub> (mod ''z''<sub>0</sub>)}} and {{math|''a''<sub>2</sub> ≡ ''b''<sub>2</sub> (mod ''z''<sub>0</sub>)}} imply {{math|''a''<sub>1</sub> + ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> + ''b''<sub>2</sub> (mod ''z''<sub>0</sub>)}} and {{math|''a''<sub>1</sub>''a''<sub>2</sub> ≡ ''b''<sub>1</sub>''b''<sub>2</sub> (mod ''z''<sub>0</sub>)}}.
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''<sub>0</sub>}}, which is also traditionally called the ''residue class ring modulo''&nbsp;{{math|''z''<sub>0</sub>}} (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''}}<sup>2</sup> {{=}} {{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)<sup>3</sup>}} 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''<sub>00</sub>}} (light green background) for the modulus {{math|''z''<sub>0</sub> {{=}} 3 + 2''i''}}. One residue class with {{math|''z'' {{=}} 2 − 4''i'' ≡ −''i'' (mod ''z''<sub>0</sub>)}} is highlighted with yellow/orange dots.]]

Given a modulus {{math|''z''<sub>0</sub>}}, all elements of a residue class have the same remainder for the Euclidean division by {{math|''z''<sub>0</sub>}}, 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<sub>mn</sub>''}} have been chosen in order that every complex number belong to exactly one square; that is, the squares {{math|''Q<sub>mn</sub>''}} 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''<sub>0</sub>}} to a unique Gaussian integer in {{math|''Q''<sub>00</sub>}} (the green square in the figure), which its remainder for the division by {{math|''z''<sub>0</sub>}}. In other words, every residue class contains exactly one element in {{math|''Q''<sub>00</sub>}}.

The Gaussian integers in {{math|''Q''<sub>00</sub>}} (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''<sub>0</sub> {{=}} ''a'' + ''bi''}} equals its norm {{math|''N''(''z''<sub>0</sub>) {{=}} ''a''<sup>2</sup> + ''b''<sup>2</sup>}} (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<sub>mn</sub>'' {{=}} (''m'' + ''in'')''z''<sub>0</sub> + ''Q''<sub>00</sub>}} means that all {{math|''Q<sub>mn</sub>''}} are obtained from {{math|''Q''<sub>00</sub>}} by [[translation (geometry)|translating]] it by a Gaussian integer. This implies that all {{math|''Q<sub>mn</sub>''}} have the same area {{math|''N'' {{=}} ''N''(''z''<sub>0</sub>)}}, and contain the same number {{math|''n<sub>g</sub>''}} 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<sub>mn</sub>''}}, then it contains {{math|''k''<sup>2</sup>''N'' + ''O''(''k''{{sqrt|''N''}})}} grid points. It follows {{math|''k''<sup>2</sup>''n<sub>g</sub>'' {{=}} ''k''<sup>2</sup>''N'' + ''Θ''(''k''{{sqrt|''N''}})}}, and thus {{math|''n<sub>g</sub>'' {{=}} ''N'' + ''Θ''({{sfrac|{{sqrt|''N''}}|''k''}})}}, after a division by {{math|''k''<sup>2</sup>}}. Taking the limit when {{math|''k''}} tends to the infinity gives {{math|''n<sub>g</sub>'' {{=}} ''N'' {{=}} ''N''(''z''<sub>0</sub>)}}.
}}

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

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

If, on the other hand, {{math|''z''<sub>0</sub>}} is an inert prime (that is, {{math|''N''(''z''<sub>0</sub>) {{=}} ''p''<sup>2</sup>}} is the square of a prime number, which is congruent to 3 modulo 4), then the residue class field has {{math|''p''<sup>2</sup>}} 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''}}).