# Gaussian integers & division theorem

Q. let $\mathbb{Z}[i] = \{a + bi | a,b \in \mathbb{Z} \}$

Show that if $s,t \in \mathbb{Z}[i],$ $t\not = 0$ then there exists $r,q \in \mathbb{Z}[i]$ s.t. $s = tq + r$ where $N(r) < N(t)$

my attempt, if we divide s by t: $\dfrac{s}{t} = m + ni$ where $m,n \in \mathbb{Q}$

now we can define $q = q_1 + q_2i$ where $q_1,q_2$ are the largest integers s.t. $q_1,q_2 \leq m,n$ then we have $\dfrac{s}{t} = q + \alpha$ where $\alpha = \alpha_1 + \alpha_2 i \in \mathbb{C}$ where $|\alpha_1|,|\alpha_2| \leq 1/2$ so we have $s = tq + \alpha t$ now I'm having troubles defining r s.t. $N(r) < N(t)$ could someone show me how to do this?

edit: using the above definitions of $\alpha$ if we let $r = \alpha t$ and $t = x + iy$ then we get $r = (\alpha_1 x -\alpha_2 y) + i(\alpha _2 x + \alpha _1 y)$ but the real and complex parts are not integers, if we label them $k = (\alpha_1 x -\alpha_2 y), l = (\alpha _2 x + \alpha _1 y)$, $r = k + il$ is there a way to choose k and l to be integers?

edit: $\alpha t = s - tq$ could I not just let $r = \alpha t$ as $s - tq$ is in $\mathbb{Z}[i]$? any help - thanks

• Hint: for a point inside a square, the distance to the nearest corner is less than the side length of the square. – bof Jan 29 '14 at 18:29
• @bof thanks for the reply, I saw a geomemtric proof of this but I didn't understand it, the proof is here: www2.math.ou.edu/~kmartin/nti/chap6.pdf prop 6.9, but I don't see how they've shown that r and q exist, and I'm assuming your hint is something to do with that (if it's not, then I don't understand how to proceed regardless, I'm not seeing this geometrically). – Warz Jan 29 '14 at 20:11
• For a fixed $t\in\mathbb Z[i],t\ne0$, the set $S=\{tq:q\in\mathbb Z[i]\}$ of all Gaussian-integer multiples of $t$ is a square lattice of dots in the plane. The point $s$ is in one of those squares, so the distance from $s$ to the nearest lattice point is less than the side length of a lattice square. The side length is $N(t)$ or $\sqrt{N(t)}$ depending on how your norm $N(t)$ is defined, you didn't say. – bof Jan 29 '14 at 20:19
• First look at the points $tq$ where $q$ is a real integer, i.e., $0,t,-t,2t,-2t,3t,-3t,\dots$; these are equally spaced dots on a line through the origin, right? Now look at the points $tq$ where $q\in\mathbb Z[i]$ is pure imaginary, i.e., $0,it,-it,2it,-2it,3it,-3it,\dots$; these are on a line perpendicular to the other line, right? Now, the Gaussian-integer multiples of $t$ are just the vector sums of points on those two lines (points in the plane being identified with their position vectors), so there is a square lattice of points. Let $tq$ be a nearest lattice point to $s$; let $r=s-tq$. – bof Jan 29 '14 at 20:36

$\newcommand{\ZZ}{\mathbb{Z}}$ It is pretty similar, but you cannot use $\le$ in $\ZZ[i]$. There's no nice ordering on the Gaussian integers. Plus, at no point do you use the well-ordering of the integers, which is critical to proving it in $\ZZ$, and necessary if you want to mimic the proof in $\ZZ[i]$.

But since you've already proven the division algorithm, why not put it to use? You may want to restate it in this form; it's a bit more useful this way. $$\forall a,b \in \ZZ \ \exists q, r \in \ZZ \ a = bq + r, \ |r| \le \frac{|b|}{2}$$

So if you have $\alpha = a + bi$, $\beta = c + di$, can you find $\rho$ and $\sigma$ such that $\alpha = \beta \rho + \sigma$?

Use what you know about $\mathbb{C}$ (well, $\mathbb{Q}[i]$, strictly speaking), but don't actually divide, because then you leave the integers. Just use the above division algorithm to find its components.

As motivation, we look at $\mathbb{Q}[i]$. We know $\frac{\alpha}{\beta} = \frac{\alpha\overline{\beta}}{N(\beta)}$. Since the denominator is an integer, we consider the latter expression.

We know $\alpha\overline{\beta} = m + ni$ and that $N(\beta) = p \in \mathbb{N}_0$. We use the integer division algorithm twice: $$m = pq_1 + r_1, \ 2|r_1| \le p$$ $$n = pq_2 + r_2, \ 2|r_2| \le p$$

Letting $\rho = q_1 + q_2i$ and $\eta = r_1 + r_2i$: $$\alpha\overline{\beta} = m + ni = (pq_1 + r_1) + (pq_2 + r_2)i = p(q_1 + q_2i) + (r_1 + r_2i) = N(\beta) \rho + \eta$$

Since $\eta = \alpha\overline{\beta} - N(\beta)\rho$, and $\overline{\beta}$ divides $N(\beta)$, one can see that $\overline{\beta}$ divides $\eta$. We pick $\sigma \in \ZZ[i]$ such that $\sigma \overline{\beta} = \eta$. So now we can cancel the $\overline{\beta}$ on each side to get $\alpha = \beta \rho + \sigma$, and all we need to do is verify the condition $N(\sigma) < N(\beta)$.

We know that $2|r_1| \le p$ and $2|r_2| \le p$. We look at $N(2\eta)$, for some reason: $$N(2\eta) = N(2r_1 + 2r_2i) = (2r_1)^2 + (2r_2)^2 \le p^2 + p^2 = 2p^2$$

Messing around with the left and right sides: $$N(2\eta) = N(2 \sigma \overline{\beta}) = 4 N(\sigma) N(\overline{\beta})$$ $$2p^2 = 2N(\beta)^2 = 2N(\beta)N(\overline{\beta})$$

Since $4 N(\sigma) N(\overline{\beta}) \le 2N(\beta)N(\overline{\beta})$, we can conclude $2N(\sigma) \le N(\beta)$, and since $\beta \ne 0$, we have $N(\sigma) < N(\beta)$, as desired.

Or you can do this in $\mathbb{Q}[i]$, but formalizing it is... interesting. It uses the same idea though; pick your $\rho$ such that its real part is $\le \frac{1}{2}$ away from the real part of $\frac{\alpha}{\beta}$, and same with the imaginary part. Thus, the remainder is $r_1 + r_2i$, where both components are less than or equal to one half. Taking the norm: $$(r_1^2 + r_2^2) \le \left( \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 \right) = \left( \frac{1}{4} + \frac{1}{4} \right) = \frac{1}{2}$$ which is less than $1$.

• edited- new attempt – Warz Jan 29 '14 at 16:36