Take the 2-minute tour ×
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.

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