Diferencia entre revisiones de «Máximo común divisor»
Contenido eliminado Contenido añadido
m Revertidos los cambios de 24.139.132.20 a la última edición de Diegusjaimes |
|||
Línea 28:
En palabras más simples, el máximo común divisor de dos o más números es el número, más grande posible, que permite dividir a esos números al mismo tiempo.
== Cálculo del MCD ==
Los dos métodos más utilizados para el cálculo del máximo común divisor de dos números son:
:* Se descompondrán los números en factores primos y se tomarán los factores comunes con su menor exponente, el producto de los cuales será el m.c.d.
:* Si el número es muy grande este método no es operativo porque no conocemos los posibles factores. En ese caso tenemos que utilizar el mucho más rápido [[algoritmo de Euclides]].
El m.c.d. de tres números se puede calcular como sigue: mcd(''a'',''b'',''c'') = mcd(''a'', mcd(''b'',''c'')).
* mcd(48, 60). Podemos comprobar que los divisores de 48 y 60 son:
:48 = {1,2,3,4,6,8,12,16,24,48};
:60 = {1,2,3,4,5,6,10,12,15,20,30,60}
por lo que el máximo común divisor de ambos es 12. Véamoslo utilizando los dos métodos descritos anteriormente:
:*De las factorizaciones de 48 y 60, (48 = 2<sup>4</sup>.3 y 60=2<sup>2</sup>.3.5) podemos inferir que su m.c.d. es 2<sup>2</sup>.3 = 12 o comúnmente expresado como mcd(60,48)=12.
::Como puede verse hemos necesitado calcular los factorización de 48 y 60 en factores primos (En torno a 10 divisiones siendo los factores sencillos).
:*Si en cambio utilizamos el algoritmo de Euclides:
::Calculamos el resto de dividir 60 por 48, 12 (En este caso es igual a restar 48 a 60).
::Calculamos el resto de dividir 48 por 12: 0. Por tanto, el mcd de 48 y 60 es 12.
:Como puede verse utilizando el algoritmo de Euclides hemos necesitado:
:: Una resta
:: Una división
* otro ejemplo:
(6936,1200) = 2<sup>3</sup> · 3 = 24.
* un último ejemplo, mcd(7000000, 7000002).
Tras un sencillo cálculo obtenemos los factores de ambos números:
:7000000 = 2<sup>6</sup> . 5<sup>6</sup> . 7
:7000002 = 2<sup>1</sup> . 3<sup>2</sup> . 157 . 2477
por lo que su mcd es 2 (Se trata del único factor común elevado al mínimo exponente, 1).
Si utilizamos el algoritmo de Euclides llegamos al mismo resultado (haciendo dos divisiones).
| |||