1.8: El Algoritmo Euclidiana
- Page ID
- 117378
El Algoritmo Euclides lleva el nombre de Euclides de Alejandría, quien vivió alrededor del 300 a.C. El algoritmo \(^{1}\)descrito en este capítulo fue registrado y demostró ser exitoso en Elementos de Euclides, por lo que este algoritmo tiene más de dos mil años de antigüedad. Proporciona un método sencillo para calcular\(\gcd(a,b)\), aunque no sepamos mucho sobre los divisores de\(a\) y\(b\).
Ya que, como ya se señaló\(\gcd(a,b) = \gcd(b,a)\),\(\gcd(0,0)=0\)\(\gcd(a,b)=\gcd(|a|,|b|)\) y y, para poder computar\(\gcd(a,b)\) basta con encontrar un método para computar\(\gcd(a,b)\) cuándo\(a\ge b\ge 0\), así vamos a suponer que\(a\) y \(b\)satisfacer estas desigualdades.
Antes de discutir el Algoritmo Euclidiana, establecemos algunos datos útiles. En primer lugar, como\(\PageIndex{1}\) establece el Ejercicio, si\(a>0\), entonces\(\gcd(a,a)=a\). El siguiente resultado es en una vena similar.
Si\(a>0\), entonces\(\gcd(a,0)=a\).
Prueba
Dado que cada entero se divide\(0\),\(C(a,0)\) es solo el conjunto de divisores de\(a\). Por Lemma 1.7.2 el divisor más grande de\(a\) es\(|a|\). Ya que\(a>0\),\(|a|=a\). Esto demuestra que\(\gcd(a,0)=a\).
Con estos hechos ahora nos vemos reducidos al problema de encontrar\(\gcd(a,b)\) cuándo\(a>b>0\).
Vamos\(a>b>0\). Si\(a=bq+r\), entonces\[\gcd(a,b)=\gcd(b,r).\nonumber \]
Prueba
Basta con mostrar que\(C(a,b)=C(b,r)\), es decir, los divisores comunes de\(a\) y\(b\) son los mismos que los divisores comunes de\(b\) y\(r\). Para mostrar esto primero vamos\(d\mid a\) y\(d\mid b\). Tenga en cuenta que\(r=a-bq\), que es una combinación lineal de\(a\) y\(b\). Así por Teorema 1.4.1 (3)\(d\mid r\). Así\(d\mid b\) y\(d\mid r\). Siguiente asumir\(d\mid b\) y\(d\mid r\). Utilizando Teorema 1.4.1 (3) de nuevo y el hecho de que\(a=bq+r\) es una combinación lineal de\(b\) y\(r\), tenemos\(d\mid a\). Entonces\(d\mid a\) y\(d\mid b\). Así lo hemos demostrado\(C(a,b)=C(b,r)\). Entonces\(\gcd(a,b)=\gcd(b,r)\).
El Algoritmo Euclidiana es el proceso de usar Lemmas\(\PageIndex{2}\) y \(\PageIndex{1}\)calcular\(\gcd(a,b)\) cuándo\(a>b>0\).
En lugar de dar una declaración precisa del algoritmo comenzaremos con un ejemplo para mostrar cómo va.
Vamos a calcular\(\gcd(803,154)\).
| \(\gcd(803,154)\) | \(=\) | \(\gcd(154,33)\) | ya que\(803 =154\cdot5+33\); |
| \(\gcd(154,33)\) | \(=\) | \(\gcd(33,22)\) | ya que\(154 =33\cdot4+22\); |
| \(\gcd(33,22)\) | \(=\) | \(\gcd(22,11)\) | ya que\(33 =22\cdot1+11\); |
| \(\gcd(22,11)\) | \(=\) | \(\gcd(11,0)\) | ya que\(22 =11\cdot2+0\); |
| \(\gcd(11,0)\) | \(=\) | \(11\). |
De ahí\(\gcd(803,154)=11\).
A modo de comentario, observamos que en nuestra repetida aplicación del Algoritmo de División, tanto el dividendo como el divisor cambian en cada paso, con algunos números (como 33 y 22 anteriores) apareciendo primero como resto, luego moviéndose para ser el divisor en la siguiente declaración de división, y luego sirviendo finalmente como el dividendo en el estado de cuenta posterior a eso. Tenga en cuenta que el proceso termina una vez que\(0\) se alcanza un resto de (esto debe suceder, ya que en cada paso los restos disminuyen). Siempre llegamos\(\gcd(a,b)\) como el último resto distinto de cero.
Tenga en cuenta que en nuestro ejemplo hemos formado el\(\gcd\) de\(803\) y\(154\) sin factorizar\(803\) y\(154\). Este método es generalmente mucho más rápido que el factoring y puede encontrar\(\gcd\)'s cuando el factoring no es factible.
Ejercicios
Demuéstralo si\(a>0\) entonces\(\gcd(a,a)=a\).
Vamos\(a>b>0\). \(\gcd(a,b)=\gcd(b, a \bmod b)\)Demuéstralo.
(Pista: compare esta afirmación con Lema\(\PageIndex{2}\).)
Entonces, si tu calculadora puede computar\(a\bmod b\) puedes usarla al ejecutar el Algoritmo Euclideano.
Encuentre\(\gcd(a,b)\) usando el Algoritmo Euclidiana para cada uno de los siguientes valores:
- \(a=37\),\(b=60\)
- \(a=793\),\(b=3172\)
- \(a=25174\),\(b=42722\)
- \(a=377\),\(b=233\)
Usa el Algoritmo Euclidiana para mostrar que si\(n\) es un entero impar, entonces cada fracción de la forma\[\frac{2n+2}{3n+2},\nonumber\] like\(\frac{4}{5}\) y\(\frac{8}{11}\), ya está en términos más bajos. (Pista: ¿Cuál es el mayor divisor común del numerador y denominador?) \(^{2}\)
Escribir un párrafo describiendo las similitudes y diferencias del Algoritmo Euclidiana y el algoritmo para convertir un número en su\(b\) representación base.
A continuación se presentan dos pequeños proyectos que puede disfrutar:
- Llevar a cabo el Algoritmo Euclidiana para encontrar\(\gcd(a,b)\) cuándo\(a=13\) (siempre) y\(b\) es cada número en el conjunto\(\{1,2,\dots,12\}\) en turno. ¿Para cuál\(b\) es el Algoritmo Euclideano da más pasos para producir\(\gcd(13,b)\)?
- Los números que llevaron a procedimientos más largos en la última parte tienen algo en común. Si aún no estás familiarizado con ellos, haz una búsqueda en internet para conocer los “números de Fibonacci”. ¿Cómo están conectados los números de Fibonacci a lo que observó en la Parte 1 de este ejercicio?
- ¿Tienes una predicción para cuál\(b\) va a conducir a los procedimientos de Algoritmos Euclideanos más largos si calculamos\(\gcd(21,b)\)? ¡Pruebala!
- Ahora haz una búsqueda en internet de páginas web que contengan tanto las frases “algoritmo euclidiana” como “números de Fibonacci”. ¿Qué averiguas?
Aquí hay un juego simple: Comenzando con enteros positivos distintos\(a\) y\(b\) en una hoja de papel, dos jugadores se turnan para intentar escribir un nuevo número en la hoja, sujeto a las condiciones de que (1) el número no aparezca ya en el papel, y (2) el número es un número positivo que es la diferencia de dos números ya en el papel.
Por ejemplo, si los números iniciales fueran\(21\) y\(6\), el primer jugador podría agregar “\(15\)” al papel, porque\(21-6 = 15\). El segundo jugador podría entonces escribir “\(9\)” (que es igual\(15-6\)), y el primer jugador podría escribir a continuación “\(12\)” (que es\(21-9\)) o “\(3\)” (que es\(9-6\)), y el juego continuaría.
El juego termina cuando un jugador no puede encontrar otro número para agregar a la hoja de papel; ese jugador pierde el juego. Contesta las siguientes preguntas.
- Si el juego descrito anteriormente continuara, ¿quién ganaría el juego? ¿Importa qué decisiones tomen los jugadores en sus turnos?
- Cuando termina el juego anterior, ¿qué números aparecen en la hoja de papel? ¿Qué patrones ves en esta colección de números?
- Si se juega el mismo juego comenzando con dos enteros positivos distintos\(a\) y\(b\), el entero más pequeño en el papel al final del juego tiene una relación especial con\(a\) y\(b\). ¿Cuál es esta relación y por qué sucede?
(Pista: ¡piensa en los resultados de este capítulo!) - ¿Puedes idear una estrategia de decidir qué jugador ser (el primero o el segundo jugador) si quisieras estar seguro de ganar el juego, si sabías qué\(a\) y lo\(b\) eras? ¿Qué sería? ¿Por qué funcionaría?
Notas al pie
[1] A diferencia del algoritmo de división, ¡el algoritmo euclidiano realmente es un algoritmo!
[2] Este problema está adaptado de un concurso mensual 2017 del Círculo de Matemáticas de Berkeley. Consultado en https://mathcircle.berkeley.edu/site...files/handouts mc/problems/2017/mc4.pdf el 17 de agosto de 2021.