Algoritmo euclidiano y ecuación diofántica: ejemplos y soluciones

El algoritmo euclidiano

Una receta de comida tiene frases como «mezclar» y «mezclar». Conocer el significado nos permite crear resultados deliciosos. En matemáticas, tenemos recetas llamadas algoritmos . Aunque los resultados no son exactamente comestibles, pueden ser fascinantes. Por ejemplo, el algoritmo de esta lección tiene los términos dividendo, divisor , cociente y resto. Curiosamente, todos ellos se relacionan con la operación matemática de división. Por ejemplo, dividamos 1,071 entre 462:

Como primer paso en la operación de división, buscamos el entero más grande , o número entero, que cuando se multiplica por 462 se ajusta (es decir, no excede) 1,071. El número se convertirá en parte de la respuesta a la división. La respuesta a la división es el cociente ; hasta ahora, el cociente es 2.

El número 462 es el divisor. ¿Ves el 924? Multiplicamos el cociente por el divisor (2 por 462) y obtuvimos 924. Luego, restamos 924 de 1,071. Lo que queda es el resto ; el resto es 147.

Cociente, divisor y resto; dejando solo el término dividendo . Adivina qué número podría ser. ¡Estás en lo correcto! El dividendo es 1071.

Normalmente, no nos molestamos en usar colores para hacer la división, pero en esta lección, realizaremos un seguimiento de los números de colores: el azul 462 y el verde 1,071.

Organicemos toda esta información con una tabla:

Siguiente paso: divide 462 entre 147. Quizás te preguntes por qué. Es porque estamos desarrollando un algoritmo para encontrar el máximo común divisor. Pero más sobre el máximo común divisor más adelante.

Por ahora, solo divide 462 entre 147 e identifica el dividendo, el divisor, el cociente y el resto:

• El número que se divide es el dividendo: 462
• El número que hace la división es el divisor: 147
• La respuesta a la división es el cociente: 3
• Lo que queda es el resto: 21

A la mesa vamos:

¿No parece la información mucho más organizada? ¿Ves cómo el divisor (segunda columna) se convierte en dividendo en el siguiente paso? ¿Ves cómo el resto (cuarta columna) se convierte en divisor en el siguiente paso?

Bien, el siguiente paso es dividir 147 entre 21, que como puede ver, nos da 7:

Y en la mesa para mantener las cosas organizadas:

El algoritmo se detiene cuando el resto se convierte en 0. La última línea contiene el máximo común divisor. El máximo común divisor es el número entero más grande que se divide en 1,071 y 462 sin producir un resto. El máximo común divisor de 1071 y 462 es 21.

Podemos comprobar: 1.071 dividido por 21 es el número entero 51. Y 462 dividido por 21 es el número entero 22.

Este algoritmo del máximo común divisor se conoce como algoritmo euclidiano .

Ecuación diofántica

A los matemáticos les encanta explorar y descubrir relaciones entre números. ¿Qué pasa si alguien le pide que escriba el máximo común divisor de los números 462 y 1,071 como la combinación lineal de 462 y 1,071? Es posible que responde con, » ¿Qué? », Pero lo único que estamos pidiendo es encontrar x e y en la siguiente ecuación:

Graficando y contra x , obtenemos el siguiente gráfico:

Infinidad de soluciones

Una línea tiene un número infinito de puntos. Lo que significa que hay un número infinito de combinaciones x – y que satisfacen la ecuación. Tenga en cuenta: esta línea 21 = x 1,071 + y 462 parece que pasa por el origen, pero no es así. En x = 0 tenemos y = .0196.

De todas estas soluciones, solo hay una en la que tanto x como y son números enteros. Las soluciones enteras son el ingrediente clave para las ecuaciones diofánticas . Puede hacerse una idea de esto eligiendo algún entero arbitrario para x (como -2) y descubriendo que la y correspondiente es 0.9.

Solo uno de los dos números de solución es un número entero

Hay una forma sencilla de encontrar la solución entera completa. Empezamos escribiendo la ecuación:

Resto = Dividendo – Cociente x Divisor

Volviendo a la última línea de la tabla, el resto es 21. Es igual al dividendo, 462, menos el cociente por el divisor, 3 x 147.

Y la línea anterior en la tabla dice resto, 147, es igual al dividendo, 1.071, menos el cociente por el divisor, 2 x 462.

Ahora nos vamos a encontrar x e y . El truco consiste en aislar los números 462 y 1.071. Empezar con:

Luego, usando la ecuación, 147 = 1071 – (2 x 462), use el lado derecho y sustituya 147:

Luego agrupa los términos:

Y, finalmente, simplifica:

De acuerdo, comparando con la ecuación diofántica, 21 = x 462 + y 1,071, vemos x = 7 e y = -3. Esta es la solución entera.

Si tenemos una solución entera, tendremos un número infinito de ellos. La forma general de las soluciones:

k es cualquier número entero. Para k = 0, x = 7 e y = -3. Para k = 1, x = 58 e y = -25. Puedes verificar estos números para resolver la ecuación diofántica original.

Resumen de la lección

Dediquemos unos minutos a revisar lo que hemos aprendido sobre el algoritmo euclidiano y la ecuación diofántica. Dados dos números enteros, podemos encontrar el número entero más grande que se divide en ambos números y produce un cociente , o el resultado de la división, que a su vez es un número entero o un número entero. Este entero más grande se llama el máximo común divisor y, por lo tanto, no incluye ningún residuo , que son, bueno, los números restantes.

Para encontrar el máximo común divisor usamos un algoritmo llamado algoritmo euclidiano . La combinación lineal de los dos números enteros se puede igualar al máximo común divisor. Una ecuación diofántica busca soluciones enteras, ya que los números enteros son el ingrediente clave para ellas.

Continúa con:

1. Química

   ¿Cuáles son los reactivos en la ecuación de la respiración celular?

   Respiración celular Comencemos esta lección con una pregunta. ¿Qué comiste hoy? O más específicamente, ¿por...

2. Álgebra

   Línea vertical: ecuación y pendiente

   Tipos de líneas Cuando observamos ecuaciones lineales en un gráfico, a menudo vemos líneas que...

3. Biologia

   Ecuación de heredabilidad en sentido estricto y amplio y aplicaciones

   ¿Qué es la heredabilidad en sentido amplio y en sentido estricto? Los rasgos observables de...

4. Geometría

   Elipse: definición, ecuación y ejemplos

   ¿Qué es una elipse? Probablemente estés muy familiarizado con los círculos. Son completamente redondos y...