Máximo común divisor
El máximo común divisor de dos números enteros es el número que divide a ambos sin dejar resto y tal que no existe ningún otro número mayor que también divida a ambos sin dejar resto.
Como ejemplo tomemos los números 24 y 32. ¿Cuál es su máximo común divisor? Buscamos en primer lugar un número que divida a los dos.
- Por ejemplo, el número 12 divide al 24, pero no divide al 32, porque 32 / 12 es igual a 2,666…, que no es un número entero. Así que el número 12 no puede ser el máximo común divisor de 24 y 32.
- ¿Y el número 4? Ese divide a los dos: 24 / 4 es igual a 6 y 32 / 4 es igual a 8. El número 4 es, pues, nuestro primer candidato. ¿No existe algún número mayor que divida a ambos?
- El número 8 divide tanto al 24 como al 32 y, además, es mayor que 4.
- No existe ningún otro número mayor que 8 que divida a ambos. El número 8 es, por tanto, el máximo común divisor de 24 y 32.
Algoritmo de Euclides para hallar el máximo común divisor
Existe una manera bastante sencilla de hallar el máximo común divisor de dos números con el algoritmo de Euclides. Partimos de dos números x e y cuyo máximo común divisor queremos hallar. Como ejemplo lo probaremos con los números x = 50 e y = 35. Procederemos así:
- Dividimos x / y y nos quedamos con el resto de la división. Este resto lo anotamos como z. Para nuestro ejemplo obtenemos 50 / 35, que nos da el resto z = 15.
- Ahora intercambiamos las variables: en la variable x guardamos el valor de y y en y guardamos el valor de z. El valor original de x lo descartamos. Después de este paso obtenemos x = 35 e y = 15.
- Ahora miramos si y es igual a cero. Si lo es, el máximo común divisor es el número x. Como y no es igual a cero, seguimos adelante y repetimos todo el procedimiento desde el primer punto.
- Volvemos a dividir x / y, es decir, 35 / 15, que nos da el resto z = 5.
- Intercambiamos las variables y obtenemos x = 15 e y = 5. Como y no es igual a cero, seguimos adelante.
- Dividimos x / y, es decir, 15 / 5. El resto es z = 0.
- Intercambiamos las variables y obtenemos x = 5 e y = 0.
- En este momento y = 0 y nuestro algoritmo termina. El máximo común divisor es el número x = 5.
Lo importante es que el orden de los números da igual. Si intercambiáramos los números del ejemplo, obtendríamos el par x = 35 e y = 50. El procedimiento sería el mismo:
- Dividimos x / y, es decir, 35 / 50, que nos da el resto z = 35.
- Intercambiamos las variables: x = 50 e y = 35.
- Vemos que después de este paso lo único que hemos hecho es intercambiar entre sí el contenido de las variables x e y…
Calculadora
Esta calculadora te calcula el máximo común divisor.
