Editing Gaussian integer (section)

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

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.

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
:<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
:<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>