matematicas

mcd y mcm

Máximo Común Divisor y Mínimo Común múltiplo




Contenido

1. Divisores de un número entero

2

2. Máximo común divisor
2.1. Otra forma de encontrar el máximo común divisor . . . . . . . . . . . .
2.2. El mcd usando el algoritmo de Euclides . . . . . . . . . . . . . . . . .

4
5
5

3. Mínimo común multiplo
3.1. Relación entre el mcd y el mcm . . . . . . . . . .. . . . . . . . . . .

7
8

1
Divisores de un número entero
Dado un número entero positivo a decimos que c divide a a, si podemos escribir a
a = cd, se acostumbra a escribir esto como c|a, también se dice que c es un factor de a
ó que a es múltiplo de c.

Ejemplos:
Ejemplo 1 Sea a = 10, entonces 5 divide a 10, porque 10 = 5 · 2, (también 2|10).
Ejemplo 2 Sea a = 16, entonces 2 dividea 16, porque 16 = 2 · 8., (también 8|16, 4|16).
Ejemplo 3 Sea a = 24, entonces 6 divide a 24, porque 24 = 6 · 4., (también 2|24, 4|24, 12|24).

Por el teorema fundamental de la aritmética, todo número se puede escribir como producto de potencias de números primos de manera única, es decir si conocemos la representación de un número entero a = pa1 pa2 pa3 · · · pan . Entonces conocemos a todoslos
1 2 3
n
factores de a.

Ejemplos:
Ejemplo 1 Si a = 10, como a = 5 · 2, entonces
{1, 2, 5, 10}
son los únicos factores de 10.
Ejemplo 2 Si a = 16, como a = 24 , entonces
{1, 2, 4, 8, 16}

3

son los únicos factores de 16.
Ejemplo 3 Si a = 24, como a = 23 · 3, entonces
{1, 2, 4, 8, 3, 6, 12, 24}
son los únicos factores de 24.

2
Máximo común divisor
El máximo común divisorde dos enteros a, b no cero, es el entero d más grande que
divide a ambos, y se escribe como d = (a, b).

Existen dos formas comunes para conocer el m.c.d. de a, b. La primera hace uso del
conocimiento de todos los factores de los dos números a, b. Esto es efectivo solo para
números pequeños ya que conocer la factorización (conocer todos los factores) completa
de un número es eficiente solopara números pequeños.
La segunda forma, es a través del algoritmo de Euclides.

Ejemplos:
Ejemplo 1 Sea a = 10 y b = 15.
Para a = 10 los factores son {1, 2, 5, 10}
Para a = 15 los factores son {1, 3, 5, 15}
Los factores comunes de 10, 15 son {1, 5}
Entonces el máximo común divisor es (10, 15) = 5.
Ejemplo 2 Sea a = 20 y b = 30.
Para a = 20
los factores son {1, 2, 3, 4, 5, 10, 20}
Paraa = 30 los factores son {1, 2, 3, 5, 6, 10, 15, 30}
Los factores comunes de 20, 30 son {1, 2, 3, 5, 10}
Entonces el máximo común divisor es (20, 30) = 10.

2.1. Otra forma de encontrar el máximo común divisor

5

2.1. Otra forma de encontrar el máximo común divisor

Ejemplo 1 Sea a = 20 y b = 24.
La factorización de a = 20 es 20 = 22 · 5
La factorización de a = 24 es 24 = 23 · 3Entonces nos fijamos en los factores comunes, qué en este caso son las potencias
de 2, y tomamos la potencia menor.
Entonces el máximo común divisor de 20 y 24 es d = 22 = 4.
Ejemplo 2 Sea a = 180 y b = 168.
La factorización de a = 180 es 180 = 22 · 32 · 5
La factorización de a = 24
es 168 = 23 · 3 · 7
Entonces nos fijamos en los factores comunes, qué en este caso son las potencias
de 2 y 3, ytomamos la potencia menor.
Entonces el máximo común divisor de 180 y 168 es d = 22 · 3 = 12.
Ejemplo 3 Sea a = 900 y b = 1080.
La factorización de a = 900
es 900 = 22 · 32 · 52
La factorización de a = 1080 es 1080 = 23 · 33 · 5
Entonces nos fijamos en los factores comunes, qué en este caso son las potencias
de 2, 3 y 5, y tomamos la potencia menor.
Entonces el máximo común divisor de 900 y1080 es d = 22 · 32 · 5 = 180.

2.2. El mcd usando el algoritmo de Euclides
El algoritmo de Euclides dice que dados dos números enteros a, b entonces siempre
existen otros dos números enteros q, r tales que:
a = bq + r con ≤ r < q
Esto es realmente fácil de comprender, ya que si a es un entero mayor a b, entonces
multiplicando q veces por b antes de alcanzarlo, hará falta un resto r menor...