Sea a el menor entero positivo que es multiplo de 6, 7, y 8?

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.

Seana = 24, b = 27.

Escribamos el conjunto de todos los divisores comunes positivos de 27 y 24.

SeaSeste 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.

SeaSel 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.

Sides el máximo común divisor de dos númerosaybse escribe : d = M.

C. D.

(a, b).

8. 6.

3 Teorema.

Dados los enterosaybno ambos cero, existen enterosxyytales 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 casox = 1 yy = - 1.

Más adelante se estudiará un método expedito para hallarxyy.

8. 6.

4 Definición.

Dos enterosaybno ambos cero se llaman primos relativos si M.

C. D.

(a, b) = 1.

Ejemplo 21.

Seaa = 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 enterosaybno ambos cero ; aybson primos relativos sí y sólo sí existen enterosxeytales que 1 = ax + by.

Demostración : Siaybson primos relativos entonces M.

C. D.

(a, b) = 1.

Luego por teorema 2.

3. 3 1 = ax + by.

Ahora, sead = M.

C. D.

(a, b), luegod|ayd|by por teoremas 2.

2. 2 y 2.

2. 3 se tiene qued|ax + by, o sea qued1.

Necesariamented = 1.

8. 6.

6 Corolario.

Si M.

C. D.

(a, b) = d, entonces se tiene que M.

C. D.

Recíprocamente, sid|a, d|by 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.

Seana, b, centeros.

Sía|c y b|cy M.

C. D.

(a, b) = 1, entoncesab|c.

Demostración.

Como : a|c, c = arpara algúnr.

B|c, c = bspara algúns.

Sead = M.

C. D.

(a, b).

Entoncesd = 1, entonces existen enterosx, ytales que 1 = ax + by.

Multiplicando porc : c = acx + bcy.

Implica quec = a(bs)x + b(ar)y = ab(sx + ry), o sea que ab|c.

8. 6.

8 Lema de Euclides.

Sía|bcy M.

C. D.

(a, b) = 1, entoncesa|c.

DemostraciónComo M.

C. D.

(a, b) = 1, luego 1 = ax + bypara algún par de enterosxey.

Luegoc = (ac)x + (bc)y.

Ademása|ac.

A|bcpor hipótesis.

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

Se concluye quea|c.

Ejemplo 23.

Siaybno son relativamente primos, el resultado es falso.

Así por ejemplo, seana = 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.

Seanaybenteros no ambos cero.

Si se cumple qued = M.

C. D.

(a, b), entonces : a)d|ayd|b.

B) Síc|ayc|bentoncesc|d.

Ejemplo 24.

Seana = 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) siendoa, b enteros no ambos cero.

Ejemplo 27.

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

Seapun primo de la forma n3 - 1 Entonces p = n3 - 1 = (n - 1)(n2 + n + 1).

Comopes 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 p5 y p primo se cumple que p2 + 2 es compuesto.

Todo p primo5 es de la formap = 6k + 1 ó p = 6k + 5.

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

Sip = 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 enterosx, y, ztales que .

3. Demuestre que sib|centonces 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 sines 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 enterosaybno ambos cero, probar que M.

C. D.

(a, b) = m.

C. m.

(a, b) si sólo sia = b.