[Quema]

Hola

a) Existe algún otro algoritmo para hallar el máximo común divisor de dos números, además del de Euclides? Pensando en alguno más eficiente.
b) Hay alguna algoritmo para hallar el mínimo común múltiplo de dos números?

Saludos

[ingmarov]

Hola Quema

A mí en la escuela no me enseñaron el de Euclides, me enseñaron el siguiente, (desconozco si tiene algún nombre)

Por ejemplo si queremos encontrar el MCD de 36 y 48, encontramos los divisores primos de cada uno

\( \begin{matrix}36&2\\18&2\\9&3\\3&3\\1&\end{matrix} \) de aquí tenemos que \( 36=2^2\times 3^2 \)

\( \begin{matrix}48&2\\24&2\\12&2\\6&2\\3&3\\1&\end{matrix} \) de aquí tenemos que \( 48=2^4\times 3 \)

Finalmente se escoge las potencias (de sus factores primos) comunes con menor exponente. En nuestro ejemplo vemos que tanto 2 como tres son factores primos de 36 y 48, el menor exponente con que aparecen es \( 2^2\textsf{ y }3^1 \). por tanto \( MCD(36,48)=2^2\times 3=12 \)


En cuanto al mcm me lo enseñaron de la siguiente forma, siempre encontrando los factores primos pero ahora lo hacemos de forma conjunta

\( \begin{matrix}48&36&2\\24&18&2\\12&9&2\\6&9&2\\3&9&3\\1&3&3\\1&1&\end{matrix} \) Y en este caso basta con multiplicar los factores encontrados \( mcm=2^4\times3^2=144 \)

Con la primera descomposición también se puede calcular el mcm escogiendo los factores comunes de mayor exponente, resulta lo mismo

Espero haber sido claro en la explicación.

Nota: en la columna de la derecha se ubican los divisores de los números que están a su izquierda, debajo del numero del número de la izquierda se anota la división de los dos anteriores, en el caso del mcm si la división no es exacta se anota el mismo número(si te fijas el 9 lo baje dos veces).

[Quema]

Hola

Yo me refiero al siguiente. Si querés hallar el mcd entre enteros \( A,B \). Si \( A=B \) entonces \( A \) es el mcd. Si son distintos, tomás su resta y lo comparás con el menor, hasta llegar a que las comparaciones son iguales. Por ejemplo, si se quiere hallar el mcd(10,4), se hace (6,4), (2,4),(2,2) entonces mcd(10,4)=2.

Saludos

[ingmarov]

Hola

Yo me refiero al siguiente. Si querés hallar el mcd entre enteros \( A,B \). Si \( A=B \) entonces \( A \) es el mcd. Si son distintos, tomás su resta y lo comparás con el menor, hasta llegar a que las comparaciones son iguales. Por ejemplo, si se quiere hallar el mcd(10,4), se hace (6,4), (2,4),(2,2) entonces mcd(10,4)=2.

Saludos

Ya veo, muy interesante

Investigando encontré esta página. Calculan el mcm de A y B dividiendo AxB entre su mcd. Espero te sirva

Lo anterior coincide con la información en la wikipedia
Así que si conoces el mcd(A,B) el \( mcm(A,B)=\dfrac{A\times B}{mcd(A,B)} \)

[ingmarov]

Hola

Yo me refiero al siguiente. Si querés hallar el mcd entre enteros \( A,B \). Si \( A=B \) entonces \( A \) es el mcd. Si son distintos, tomás su resta y lo comparás con el menor, hasta llegar a que las comparaciones son iguales. Por ejemplo, si se quiere hallar el mcd(10,4), se hace (6,4), (2,4),(2,2) entonces mcd(10,4)=2.

Saludos

Cuando dices resta ¿es A-B por ejemplo? si es así, sí que se hace largo el proceso. Quizás entendí mal

En esta página utilizan el módulo resto o cociente de A y B (Le llaman algoritmo de Euclides)

por ejemplo

624 mod 124=4 (no es cero) se continua con 124 mod 4=0 por tanto el mcd(624,124)=4

Y el \( mcm(624,124)=\dfrac{624\times 124}{mcd(624,124)}=\dfrac{77376}{4}=19344 \)

mcm(624,124)=19344

[Fallen Angel]

Hola!

Los algoritmos más eficientes a la hora de calcular el mcd de dos enteros están basados en el algoritmo de euclides (con ciertas variaciones a veces), ya que es muy rápido y eficiente (el Teorema de Lamé te dará una idea de lo rápido que es este algoritmo).

Lo de tomar la resta es básicamente hacer el algoritmo de euclides utilizando siempre un cociente 1.

La factorización en números primos es computacionalmente inviable. (Es un problema NP, al menos de momento  )

El mcm como bien dice ingmarov sólo es hacer una cuenta, una vez obtenido el mcd.

Un saludo!