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$ ?
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$ .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
