Gaussian Integers form Euclidean Domain

From ProofWiki
Jump to: navigation, search

Theorem

Let $\left({\Z \left[{i}\right], +, \times}\right)$ be the integral domain of Gaussian Integers.

Let $\nu: \Z \left[{i}\right] \to \R$ be the real-valued function defined as:

$\forall a \in \Z \left[{i}\right]: \nu \left({a}\right) = \left \vert{a}\right \vert^2$

where $\left \vert{a}\right \vert$ is the (complex) modulus of $a$.


Then $\nu$ is a Euclidean valuation on $\Z \left[{i}\right]$.

Hence $\left({\Z \left[{i}\right], +, \times}\right)$ with $\nu: \Z \left[{i}\right] \to \Z$ forms a euclidean domain.


Proof 1

We have by definition that $\Z \left[{i}\right] \subseteq \C$.

Let $a, b \in \Z \left[{i}\right]$.

We have from Modulus of Product that $\left \vert{a}\right \vert \cdot \left \vert{b}\right \vert = \left \vert{a b}\right \vert$.

From Properties of Complex Modulus we have that:

$\forall a \in \C: \left \vert{a}\right \vert \ge 0$
$\left \vert{a}\right \vert = 0 \iff a = 0$

Let $a = x + i y$.

Suppose $a \in \Z \left[{i}\right] \ne 0$.

Then $x \ne 0$ or $y \ne 0$ and $x^2 \ge 1$ or $y^2 \ge 1$.

So $\left \vert{a}\right \vert \ge 1$.

Similarly, $b \in \Z \left[{i}\right], b \ne 0 \implies \left \vert{b}\right \vert \ge 1$.

Thus it follows that $\left \vert{a b}\right \vert \ge \left \vert{a}\right \vert$ and so $\nu$ is a Euclidean valuation on $\Z \left[{i}\right]$.



Now, consider $x, y \in \Z \left[{i}\right]$.

We want to find $q, r \in \Z \left[{i}\right]$ such that $x = q y + r$.

Note that this means we want $r = y \left({\dfrac x y - q}\right)$ where $\dfrac x y$ is complex but not necessarily Gaussian.

We extend $\nu$ to the complex numbers and define $\nu: \C \to \C$ as:

$\forall z \in \C: \nu \left({z}\right) = \left \vert{z}\right \vert$

Then we have:

$\nu \left({r}\right) = \nu \left({y}\right) \cdot \nu \left({\dfrac x y - q}\right)$

Thus if $\nu \left({\dfrac x y - q}\right) < 1$ we have:

$\nu \left({r}\right) < \nu \left({y}\right)$


Consider the point $P = \dfrac x y$ as a point on the complex plane.

Let $Q$ lie at a point representing the Gaussian integer $q$ which lies closest to $P$.

The distance $P Q$ is at most half the length of a diagonal of a unit square in the complex plane.

Thus:

$\nu \left({\dfrac x y - q}\right) = \left \vert {\dfrac x y - q} \right \vert \le \dfrac {\sqrt 2} 2 = \dfrac 1 {\sqrt 2} < 1$

This element $q$ and the element $r$, where $\nu \left({r}\right) < \nu \left({y}\right)$, are the required values.

Thus $\Z \left[{i}\right]$ is a euclidean domain.

$\blacksquare$



Proof 2

We have by definition that $\Z \left[{i}\right] \subseteq \C$.

Let $a, b \in \Z \left[{i}\right]$.

We have from Modulus of Product that:

$\left \vert{a}\right \vert \cdot \left \vert{b}\right \vert = \left \vert{a b}\right \vert$

From Complex Modulus is Norm we have that:

$\forall a \in \C: \left \vert{a}\right \vert \ge 0$
$\left \vert{a}\right \vert = 0 \iff a = 0$


Suppose $a = x + i y \in \Z \left[{i}\right]$ and $a \ne 0$.

Then either $x \ne 0$ or $y \ne 0$, so either $x^2 \ge 1$ or $y^2 \ge 1$.

So $\left \vert{a}\right \vert^2 \ge 1$.

If also $b \in \Z \left[{i}\right], b \ne 0$, then:

$\nu \left({a b}\right) = \left \vert{a b}\right \vert^2 \ge \left \vert{a}\right \vert^2 = \nu \left({a}\right)$


Now, consider $x, y \in \Z \left[{i}\right]$ with $y \ne 0$.

We want to find $q, r \in \Z \left[{i}\right]$ such that $x = q y + r$ and $\nu \left({r}\right) < \nu \left({y}\right)$.

Note that this means we want $r = y \left({\dfrac x y - q}\right)$ where $\dfrac x y$ is complex but not necessarily Gaussian.

Consider the complex number $p = \dfrac x y = p_r + i p_i$.

We extend $\nu$ to the complex numbers and define $\nu: \C \to \C$ as:

$\forall z \in \C: \nu \left({z}\right) = \left \vert{z}\right \vert^2$


Let $q = q_r + i q_i$ be the Gaussian integer such that:

$\nu\left({p - q}\right) = \left\vert p - q \right\vert^2 = \left({p_r - q_r}\right)^2 + \left({p_i - q_i}\right)^2$

is minimal.

That is, $q_r$ is the nearest integer to $p_r$ and $q_i$ is the nearest integer to $p_i$.

A given real number can be at a distance at most $1/2$ from an integer, so it follows that:

$(1): \quad \nu \left({p - q}\right) \le \left({\dfrac 1 2}\right)^2 + \left({\dfrac 1 2}\right)^2 = \dfrac 1 2$


Now by Complex Modulus is Norm, for any two complex numbers $z_1, z_2$ we have:

$\nu\left({z_1 z_2}\right) = \nu \left({z_1}\right) \nu \left({z_2}\right)$

Thus we obtain:

\(\displaystyle \nu \left({y \left({p - q}\right)}\right)\) \(=\) \(\displaystyle \nu \left({y}\right) \nu \left({p - q}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\le\) \(\displaystyle \dfrac {\nu \left({y}\right)} 2\) $\quad$ by $(1)$ $\quad$
\(\displaystyle \) \(<\) \(\displaystyle \nu \left({y}\right)\) $\quad$ since $\nu \left({y}\right) \ne 0$ $\quad$

On the other hand:

\(\displaystyle \nu \left({y \left({p - q}\right)}\right)\) \(=\) \(\displaystyle \nu \left({y \left({\frac x y - q}\right)}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \nu \left({x - y q}\right)\) $\quad$ $\quad$

So letting $r = x - y q$ we have $\nu \left({r}\right) < \nu \left({y}\right)$.

Moreover we trivially have $x = q y + r$.

Thus $\Z \left[{i}\right]$ is a Euclidean domain.

$\blacksquare$