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}| Should the $k^\mbox{th}$ remainder be enclosed by absolute value, too? In symbols, should it read $|r_{k+1}|<|r_k|/2$?
Working with least absolute remainders in the Euclidean Algorithm (possible typo)
3
$\begingroup$
number-theory
elementary-number-theory
euclidean-algorithm
-
0That must be what was intended. – 2011-10-15
-
0Why? The inequality won't make sense if in the $k^{\mbox{th}}$ step we had used a negative remainder. – 2011-10-15
-
0I 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.) – 2011-10-15
-
1It 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). – 2011-10-15
-
0@Barry: Good point. It should probably be corrected to $|r_{k+1}|\le|r_k|/2$. – 2011-10-15
-
0@Brian Yes, I did. And that comment got me the commentator badge. – 2011-10-15
-
0@B If one of you can copy your comment down below as an answer, I will accept it. And thank you both for the responses. – 2011-10-16
1 Answers
0
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$.