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

I'm reading Burton's Elementary Number Theory (4th edition). On page 29, we read, "The number of steps in the Euclidean Algorithm usually can be reduced by selecting remainders $|r_{k+1}|<r_k/2$."

Should the $k^\mbox{th}$ remainder be enclosed by absolute value, too? In symbols, $|r_{k+1}|<|r_k|/2$ .

share|cite|improve this question
That must be what was intended. – Brian M. Scott Oct 15 '11 at 20:01
Why? The inequality won't make sense if in the $k^{\mbox{th}}$ step we had used a negative remainder. – sasha Oct 15 '11 at 20:09
I know: that’s why I was agreeing with you. (I think that you must have misunderstood my comment as support for the version in the book.) – Brian M. Scott Oct 15 '11 at 20:14
It also seems problematic that, for instance, $r_k$ might be 4 while $r_{k+1}$ could be $2$ modulo $4$. He has no language to avoid this case (like assuming the gcd in question is 1 --- in the example he gives, the gcd is 6). – Barry Smith Oct 15 '11 at 20:18
@Barry: Good point. It should probably be corrected to $|r_{k+1}|\le|r_k|/2$. – Brian M. Scott Oct 15 '11 at 20:28

Your Answer


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

Browse other questions tagged or ask your own question.