# Part of a proof in Herstein about Gaussian Integers being a Euclidean Ring

In Herstein topics in algebra (2nd Edition) page 150, in proof of theorem 3.8.1, in the first special case where $n$ is a positive integer and $y=a+bi$ is a general Gaussian integer, where he is trying to employ the Euclidean algorithm in the ring of integers to find four integers $u,v,u_1,v_1$ such that $a=u n + u_1$ and $b=v n + v_1$ why is it the case that $|u_1|\leq\frac{n}{2}$ and $|v_1|\leq\frac{n}{2}$ and not just $|u_1|\leq n$ and $|v_1|\leq n$?

I don't understand how he got to this assertion. If $a,b,n$ are general, I could take $n=5$, $a=9$ and $b=8$ and the statement would be false...

-

The standard (positive) division algorithm asserts that $0\leq u_1<n$. There is a second Euclidean algorithm which allows the remainder, $u_1$, to be negative - where then the condition is $\left|u_1\right|\leq \frac{n}{2}$. This needs to be proved, but it is an easy corollary of the positive division algorithm.
For $a=9,n=5$, you'd have $u=2$ and $u_1=-1$, so $9=5\cdot 2 + (-1)$. Similarly, $8=5\cdot 2 +(-2)$.