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