Working with least absolute remainders in the Euclidean Algorithm (possible typo)

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$?

-
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

1 Answer

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

-