8.6. Máximo Común Divisor.

8.6.1 Definición. Se llama común divisor de dos enteros a un entero que los divida.

Ejemplo 17.

2, 3 y 6 son divisores comunes de 18 y 24.

8.6.2 Definición. Se llama máximo común divisor de dos enteros, al menos uno de ellos diferente de cero, al mayor entero que los divide exactamente.

De la definición anterior es claro que el máximo común divisor de dos enteros es siempre un entero positivo.

Ejemplo 18.

Sean a = 24, b = 27. Escribamos el conjunto de todos los divisores comunes positivos de 27 y 24. Sea S este conjunto: S = {1, 3}. Luego el máximo común divisor de 24 y 27 es 3.

Ejemplo 19.

Halle el máximo común divisor de 32 y 48.

Sea S el conjunto de los divisores comunes positivos, entonces, S= {1,2,4,8,16}.

Luego el máximo común divisor de 32 y 48 es 16.

Si d es el máximo común divisor de dos números a y b se escribe: d = M.C.D.(a,b).

8.6.3 Teorema. Dados los enteros a y b no ambos cero, existen enteros x y y tales que M.C.D.(a, b) = ax + by.

Ejemplo 20.

Como M.C.D.(24, 27) = 3. Entonces se cumple 3 = 27x(1) + 24x(-1).

En este caso x = 1 y y = -1.

Más adelante se estudiará un método expedito para hallar x y y.

8.6.4 Definición. Dos enteros a y b no ambos cero se llaman primos relativos si M.C.D.(a, b) = 1.

Ejemplo 21.

Sea a = 28, sus divisores positivos son {1, 2, 4, 7, 14}. b = 25, sus divisores positivos son {1, 5}.

El único divisor común es 1. Luego 25 y 28 son primos relativos.

8.6.5 Teorema. Dados dos enteros a y b no ambos cero; a y b son primos relativos sí y sólo sí existen enteros x e y tales que 1 = ax + by.

Demostración: Si a y b son primos relativos entonces M.C.D.(a, b) = 1. Luego por teorema 2.3.3 1 = ax + by.

Ahora, sea d = M.C.D.(a, b), luego d|a y d|b y por teoremas 2.2.2 y 2.2.3 se tiene que d|ax + by, o sea que d1. Necesariamente d = 1.

8.6.6 Corolario. Si M.C.D.(a, b) = d, entonces se tiene que M.C.D..
Recíprocamente, si d|a, d|b y M.C.D. entonces M.C.D.(a,b) = d.

Ejemplo 22.

ComoM.C.D.(24, 27) = 3, entonces se cumple que:

M.C.D. = M.C.D.(8, 9) = 1.



8.6.7 Teorema.Sean a, b, c enteros. Sí a|c y b|c y M.C.D.(a, b) = 1, entonces ab|c.

Demostración. Como: a|c,c = ar para algún r. b|c,c = bs para algún s.

Sea d = M.C.D. (a, b). Entonces d = 1, entonces existen enteros x, y tales que 1 =ax + by.

Multiplicando por c: c = acx +bcy. Implica que c = a(bs)x + b(ar)y = ab(sx + ry), o sea que ab|c.

8.6.8 Lema de Euclides.a|bc y M.C.D.(a, b) = 1, entonces a|c.

Demostración

Como M.C.D.(a, b) = 1, luego 1 = ax + by para algún par de enteros x e y. Luego c = (ac)x + (bc)y.

Además a|ac.

a|bc por hipótesis.

Se sigue entonces: a|(ac)x + (bc)y; de donde .

Se concluye que a|c.

Ejemplo 23.

Si a y b no son relativamente primos, el resultado es falso. Así por ejemplo, sean a = 12, b= 9, c = 8.

Se tiene 12|9x8, sin embargo 129 y 128, y esto no se cumple porque M.C.D.(12, 9) = 3 ¹ 1.

8.6.9 Teorema. Sean a y b enteros no ambos cero. Si se cumple que d = M.C.D.(a, b), entonces:

a) d|a y d|b.

b) Sí c|a y c|b entonces c|d.

Ejemplo 24.

Sean a = 28, b = 42. El conjunto de los divisores comunes de 28 y 42 es {1,2,7,14}.

El M.C.D.(28, 42) = 14. Los demás divisores son 1, 2 y 7 y cumplen que 1|14; 2|14; 7|14.

8.6.10 Definición. Un entero p > 1 es primo sí y sólo sí sus únicos divisores positivos son 1 y p. Un entero mayor que 1 que no es primo se llama compuesto.

Ejemplo 25.

2, 3, 5, 7, 11, 17, 19 son números primos.

Ejemplo 26.

4, 6, 8, 12, 15, 24 son números compuestos.

8.6.11 Teorema.Para todo entero k ¹ 0, M.C.D. (ka,kb) = |k|xM.C.D.(a,b) siendo a, b enteros no ambos cero.

Ejemplo 27.

Demuestre que el único entero primo de la forma n3-1 es 7.

Sea p un primo de la forma n3-1 Entonces p=n3-1=(n-1)(n2+n+1). Como p es primo, luego p=n-1 y n2+n+1=1 ó p=n2+n+1 y n-1=1.

La primera posibilidad no se puede dar.

De la segunda posibilidad se tiene que n=2, luego p=22+2+1=7.

Ejemplo 28.

Demuestre que cada entero de la forma n4 + 4 con n >1 es compuesto.

n4 = (n2-2n+2)(n2+2n+2) y como n >1, n2-2n+2 > 1 y n2-2n+2 >1. Entonces n4+4 es compuesto.

Ejemplo 29.

Demuestre que para p 5 y p primo se cumple que p2+2 es compuesto.

Todo p primo 5 es de la forma p = 6k+1 ó p = 6k+5.

Si p = 6k+1, p2+2 = 36k2 +12k+3, p2+2=3(12k2+4k+1) que es compuesto.

Si p = 6k+5, p2+2 = 36k2 +60k+27, p2+2=3(12k2+20k+9) que es compuesto.

Ejercicios 8.6

1. Demuestre que el máximo común divisor de dos enteros no ambos cero, es único.

2. Demuestre que si M.C.D.(a,b) = 1 y M.C.D.(a,c) = 1 entonces M.C.D.(a,b,c) = 1.

Nota: Si entonces se cumple que existen enteros x, y, z tales que .

3. Demuestre que si b|c entonces M.C.D.(a, b) = M.C.D.(a + c, b).

4. Demuestre que si M.C.D.(a, c) = 1 entonces M.C.D.(a, b) = M.C.D.(a, bc).

5. Demuestre que si M.C.D.(a,bc) = 1 entonces, M.C.D.(a,b) = 1 y M.C.D (a, c)=1.

6. Asumiendo que M.C.D.(a, b) = 1 probar que M.C.D.(2a+b, a+2b) es 1 o 3.

7. Demostrar que si n es un entero entonces n(n+1)(2n+1) es divisible por 6.

8. Asumiendo que M.C.D.(a, b) = 1 probar que M.C.D.(a+b, a2 + b2) es 1 o 2.

9. Si el máximo común divisor de dos números es 21 y la relación entre ellos es de 5 a 8, hallar los números.

10. Si el máximo común divisor de dos números es 2, y su producto es 840, hallar los dos números.

11.Dados enteros a y b no ambos cero, probar que M.C.D.(a, b) = m.c.m.(a, b) si sólo si a = b.