I believe I have an algorithm for division in $\mathbb{Z}[i],$ but I can't seem to prove it works, nor can I find references for it online (although my searches for "division algorithm in Z[i]" seem to result in nothing but proofs that division is possible...)
Anyways, here it goes for $\tfrac{z}{w}$:
- Compute $z\overline{w}$ and then do "integer division" by $|w|^2$ to get $q,$ i.e. if $z\overline{w} = 17+34i$ and $|w|^2 = 5$ then $q = 3+6i.$
- Let $r = z - qw.$
It seems that we always have $|r| < |w|.$ For example, dividing $9+17i$ by $4+7i$ with this would produce $(9+17i)(4-7i) = 155 + 5i$ and so we divide by $65$ to get $2+0i.$ So, we'd have $9+17i = (4+7i)(2+0i) + (1+3i).$ Then, since $|1+3i| = \sqrt{10} < \sqrt{65} = |4+7i|,$ we've got a valid quotient and remainder for $9+17i$ divided by $4+7i.$
Does this actually work? If not, why have I gotten so lucky with my examples that it seems to work--is there perhaps a specific set of numbers this works for?
All I can add is to round the real and imaginary parts of $\frac{z \bar{w}}{|w|^2}$ to the nearest integers, rather than a strict floor function.
Suppose the actual quotient is $s + i t$ where both $s,t$ are rational. The closest Gaussian integer is some $m + n i$ where $m - s = \delta,$ then $n - t = \varepsilon,$ and $|\delta| , | \varepsilon| \leq \frac{1}{2} $
$$ (s+it) w = z $$ $$ (m+in) w - z = (\delta + i \varepsilon) w, $$ $$ |\delta + i \varepsilon| \leq \sqrt {\frac{1}{4} + \frac{1}{4}} = \frac{1}{\sqrt 2} $$
If you got quotient $5.9 + 7.9 i$ and took integer point $5 + 7 i$ rather than rounding, the required inequality would fail