Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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