Introducción
En entradas anteriores estudiamos los conceptos de máximo común divisor y de mínimo común múltiplo. Ahora nos enfocaremos en un aspecto un poco más práctico sobre el máximo común divisor que dejamos pendiente: ¿cómo lo calculamos? Para ello hablaremos de un procedimiento conocido como el algoritmo de Euclides, el cual afirma que afirma que podemos aplicar iteradas veces el algoritmo de la división en ciertos números específicos, comenzando con dos enteros
Lo primero que haremos es explicar el procedimiento mediante el cual podemos encontrar el máximo común divisor de dos números aplicando repetidamente el algoritmo de la división. En la siguiente sección daremos la demostración de por qué funciona este procedimiento. Hacia el final de la entrada también veremos que este mismo procedimiento nos permite también escribir al máximo común divisor de dos enteros
El procedimiento del algoritmo de Euclides
Sean
Luego, como
Y como
Se puede continuar así sucesivamente. Pero este procedimiento debe de terminar, pues tenemos
Y en el último paso tendríamos
Lo que nos dice el algoritmo de Euclides es que el último residuo no cero, en este caso
Este procedimiento es particularmente útil cuando
Ejemplo del algoritmo de Euclides
A continuación veremos el algoritmo de Euclides en acción.
Problema. Encuentra el máximo común divisor de
Solución. Observamos que
Aplicando nuevamente el algoritmo de la división, obtenemos
Aplicando una vez más el algoritmo de la división, se tiene
Siguiendo este procedimiento,
Como el último residuo no cero es
Observación. Aunque el algoritmo de Euclides requiere que los números
Veamos un ejemplo que usa esta observación.
Ejemplo. Obtén el máximo común divisor de
Solución. Como uno de los números es negativo, antes que nada sacamos valores absolutos:
Notemos que el último residuo no cero es
Demostración de la validez del algoritmo de Euclides
Ahora, veamos la demostración de que el algoritmo de Euclides funciona. El resultado clave para demostrarlo es la siguiente proposición.
Proposición. Sean
Demostración. Sean
Tenemos que
Por otro lado,
Por propiedades de divisibilidad, tenemos entonces que
Ya con este resultado demostrado, enunciemos formalmente el algoritmo de Euclides y demos su demostración.
Teorema. Empecemos tomando dos enteros positivos
con
con
Como
Demostración. Por la proposición anterior, tenemos que
La penúltima igualdad es porque
Máximo común divisor como combinación lineal entera
Una última consecuencia del algoritmo de Euclides es que nos ayuda a poner al máximo común divisor de dos números
Una forma práctica de encontrar la combinación lineal correspondiente es mediante el siguiente procedimiento. Tomaremos como ejemplo el algoritmo de Euclides que ya habíamos hecho para encontrar
Lo que haremos es la siguiente tabla, en donde en la columna izquierda ponemos todos los residuos que vamos encontrando. Además, completaremos la primera fila con
Vamos a ir llenando la tabla con lo que ya sabemos del algoritmo de Euclides. Por el algoritmo de Euclides, sabemos que
De nuevo,
Ahora cambia un poco, pues
Siguiendo este procedimiento repetidamente, llegamos a la siguiente tabla:
Los últimos dos números que pusimos en la tabla nos dan la respuesta de cómo poner a
Verifica que en efecto las cuentas son correctas, y que esta expresión final es válida.
¿Cómo se demuestra que este procedimiento siempre funciona? Se puede mostrar inductivamente que, de hecho, para cada uno de los renglones con entradas
Más adelante…
Esta entrada termina nuestra exploración introductoria al mundo de la aritmética de los números enteros. Sin embargo, todavía hay otros lugares a los que nos llevará el algoritmo de la división. Hasta ahora hemos discutido mucho el caso de la divisibilidad, es decir, cuando el residuo de la división de un número entre otro es igual a cero. Pero también podemos encontrar estructuras matemáticas muy ricas si estudiamos al resto de los posibles residuos. A partir de la siguiente entrada hablaremos del anillo de enteros módulo
Tarea moral
A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.
- Usa el algoritmo de Euclides para encontrar el máximo común divisor de las siguientes parejas de números, y para escribirlo como combinación lineal entera de ellos.
y y y y
- ¿Cómo usarías el algoritmo de Euclides para encontrar el máximo común divisor de los números
, y ? Es decir, debes encontrar el mayor entero que divida a estos tres números de manera simultánea. - Hay otra forma de encontrar el máximo común divisor de dos números si conocemos su factorización en números primos. Imagina que tenemos dos números
y y que, conjuntamente, usan los números primos distintos en su factorización en primos (quizás con exponente cero). Esto nos permite escribirlos como: .- Demuestra que la máxima potencia de
que divide tanto a como a es . - Demuestra que el máximo común divisor de
y es
- Demuestra que la máxima potencia de
- Demuestra un resultado análogo al del inciso anterior para el mínimo común múltiplo y usa ambos resultados para dar otra demostración de que
. - Verifica que, en efecto, el método explicado en la entrada ayuda a escribir al máximo común divisor de dos enteros como combinación lineal de ellos.
Entradas relacionadas
- Ir a: Álgebra Superior II
- Entrada anterior del curso: Teorema fundamental de la aritmética e infinidad de números primos
- Siguiente entrada del curso: Problemas de divisibilidad y el algoritmo de Euclides
Agradecimientos
Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»