Ejercicio · ZW-ALGORITMO-DE-EUCLIDES-009 · ★★★ Avanzado
¿Por qué el algoritmo de Euclides siempre termina?
Elige una opción.
Ver respuesta
- C. Los residuos forman una sucesión estrictamente decreciente de enteros no negativos
Explicación
Los residuos son enteros no negativos y cada uno es menor que el divisor anterior; una sucesión estrictamente decreciente de enteros no negativos es finita.
Repasa el concepto: Algoritmo de Euclides
El algoritmo de Euclides calcula el máximo común divisor de dos enteros \(a\) y \(b\) dividiendo una y otra vez, y reemplazando cada par por el divisor y el residuo, hasta que el residuo sea 0.
\[\gcd(a,b)=\gcd(b,\,a\bmod b)\]
Más ejercicios de algoritmo de euclides
- ZW-ALGORITMO-DE-EUCLIDES-001 Calcula gcd(252,105) con el algoritmo de Euclides.
- ZW-ALGORITMO-DE-EUCLIDES-002 ¿Cuál es el residuo de dividir 100 entre 36?
- ZW-ALGORITMO-DE-EUCLIDES-003 Al aplicar el primer paso de Euclides al par (84,30), ¿qué par se obtiene?
- ZW-ALGORITMO-DE-EUCLIDES-004 Calcula gcd(1071,462).
- ZW-ALGORITMO-DE-EUCLIDES-005 ¿Cuántas divisiones (la última con residuo 0) requiere el algoritmo de Euclides para gcd(1071,462)?
- ZW-ALGORITMO-DE-EUCLIDES-006 Calcula gcd(391,221).
- ZW-ALGORITMO-DE-EUCLIDES-007 Reduce la fracción (143)/(221) a su forma irreducible.
- ZW-ALGORITMO-DE-EUCLIDES-008 Para cualquier entero positivo n, ¿cuánto vale gcd(n,n+1)?
← ZW-ALGORITMO-DE-EUCLIDES-008 ZW-ALGORITMO-DE-EUCLIDES-010 →