2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hint: for a point inside a square, the distance to the nearest corner is less than the side length of the square. $\endgroup$ – bof Jan 29 '14 at 18:29
  • $\begingroup$ @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). $\endgroup$ – Warz Jan 29 '14 at 20:11
  • $\begingroup$ 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. $\endgroup$ – bof Jan 29 '14 at 20:19
  • 1
    $\begingroup$ 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$. $\endgroup$ – bof Jan 29 '14 at 20:36
1
$\begingroup$

$\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$.

$\endgroup$
  • $\begingroup$ edited- new attempt $\endgroup$ – Warz Jan 29 '14 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.