Proof that the Field of Gaussian Integers has a Division Algorithm

proofgaussian-integers

Theorem

For all $\alpha ,\beta$ in $\mathbb{Z}[i]$ with $\beta \ne 0$, there are $\gamma ,\rho$ in $\mathbb{Z}[i]$ such that

$$\alpha =\beta \gamma +\rho \text{ with }N(\rho )<N\beta \left(\text{in fact, }N(\rho )\le \frac{1}{2}N(\beta )\right)$$

Proof

Write $\frac{\alpha }{\beta }=\frac{\alpha \bar{\beta }}{\beta \bar{\beta }}=\frac{\alpha \bar{\beta }}{N(\beta )}=\frac{m+ni}{N(\beta )}$ for $m,n\in \mathbb{Z}$

We use modified division algorithm in $\mathbb{Z}$ (least $|r|$) to write in $\mathbb{Z}$

$$\begin{array}{rl}m=(N\beta )q_1+r_1& |r_1|\le \frac{1}{2}N\beta \\ n=(N\beta )q_2+r2& |r_2|\le \frac{1}{2}N\beta \end{array}$$

$⟹\alpha \bar{\beta }=m+ni=(N\beta )(q_1+q_{2}i)+r_1+r_{2}i$

We can call this $\rho =q_1+q_{2}i$, and we want to show $N(\rho )\le \frac{1}{2}N(\beta )<N\beta$

Then $\alpha \bar{\beta }=(N\beta )\gamma +(r_1+r_{2}i)$ $\alpha \bar{\beta }=\beta \bar{\beta }\gamma +r_1+r_{2}i$ $(\alpha -\beta \gamma )\bar{\beta }=r_1+r_{2}i$ $\rho \bar{\beta }=r_1+r_{2}i$ Apply norm: $N(\rho )N(\bar{\beta })=r_1^2+r_2^2\le \frac{1}{4}(N\beta {)}^2+\frac{1}{4}(N\beta {)}^2$ $N(\rho )N(\beta )\le \frac{1}{2}(N(\beta ){)}^2$ $N(\rho )\le \frac{1}{2}N(\beta ))$ $\square$

Note

If we were to do this in $\mathbb{Z}[\sqrt{2}]$ for example, the proof would be almost the same up to changing $i$ to $\sqrt{2}$, until we reach the “apply the norm” step, in which case we need to use the absolute value of the norms, since the norm can be positive or negative.

Remark

For prime $p$ and square-free $d\in \mathbb{Z}$,

$$p=x^2-d{y}^2⟹p\nmid y⟹d\equiv \square \mathrm{mod}p.$$

“Conversely,” if $\mathbb{Z}[\sqrt{d}]$ has unique factorization:

$$d\equiv \square \mathrm{mod}p⟹p\text{ or }-p\text{ is }{x}^2-d{y}^2\text{ in }\mathbb{Z}.$$