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, should it read $|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

It could also happen that $\lvert r_{k+1} \rvert = \lvert r_k \rvert/2$. For instance, consider the following application of the Euclidean Algorithm:

$$ \begin{align} \gcd(30,26) &= 2 \\[.2cm] \hline 30 &= 1 \cdot 26 + 4 \\ 26 &= 6 \cdot 4 + 2 \\ 4 &= 2 \cdot 2 + 0. \end{align}$$

These are the minimal remainders at each step, and we can see that $2 = 4/2$. (This is a particular example of a situation alluded to in the comments). When allowing both positive and negative remainders for faster convergence, it doesn't make sense to have $\lvert r_{k+1} \rvert \leq r_k / 2$ when $r_k$ is negative.

So the right "fast" restriction is to choose remainders such that $\lvert r_{k+1} \rvert \leq \lvert r_k \rvert / 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.