3
$\begingroup$

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

  • 0
    That must be what was intended.2011-10-15
  • 0
    Why? The inequality won't make sense if in the $k^{\mbox{th}}$ step we had used a negative remainder.2011-10-15
  • 0
    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.)2011-10-15
  • 1
    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).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 1

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