Trabajar con los mínimos absolutos en el Algoritmo Euclidiano (posible error tipográfico)

Question

Estoy leyendo el libro de Burton Teoría elemental de los números (4ª edición). En la página 29, leemos: "El número de pasos del Algoritmo Euclidiano suele reducirse seleccionando restos $|r_{k+1}|<r_k/2$ ."

En caso de que el $k^\mbox{th}$ ¿también se puede encerrar el resto por valor absoluto? En símbolos, ¿debería decirse $|r_{k+1}|<|r_k|/2$ ?

Answer 1

También podría ocurrir que $\lvert r_{k+1} \rvert = \lvert r_k \rvert/2$ . Por ejemplo, considere la siguiente aplicación del Algoritmo Euclidiano:

$$\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}$$

Estos son los restos mínimos en cada paso, y podemos ver que $2 = 4/2$ . (Este es un ejemplo particular de una situación aludida en los comentarios). Cuando se permiten residuos positivos y negativos para una convergencia más rápida, no tiene sentido tener $\lvert r_{k+1} \rvert \leq r_k / 2$ cuando $r_k$ es negativo.

Por lo tanto, la restricción "rápida" correcta es elegir restos tales que $\lvert r_{k+1} \rvert \leq \lvert r_k \rvert / 2$ .