Algoritmo de Euclides

Descargar como docx, pdf o txt
Descargar como docx, pdf o txt
Está en la página 1de 16

1.1. Los nmeros enteros.

Una parte muy importante de la aritmtica se dedica al estudio de


los nmeros enteros, Z= {...,-3,-2,-1,0,1,2,3,...}. Estos nmeros fueron perdiendo, con el tiempo,
su relacin con supersticiones y misticismos, pero su inters para los matemticos no
disminuy jams.

Se comenzar suponiendo que los elementos del conjunto Z satisfacen ciertas propiedades y
se demostrarn, a partir de stas, una serie de propiedades que caracterizan a Z.

Se entiende que los smbolos empleados a,b,c,.. representan elementos de Z, mientras que + y
(o simplemente ". ") representan las operaciones usuales de adicin y multiplicacin.

1.2. Propiedades de los enteros

1.2.1. (a+b) +c = a+(b+c)

1.2.2. a+b = b+a

1.2.3. 0+a = a

1.2.4. Dado cualquier existe un tal que a+b = b+a = 0. Este b se simboliza por - a y
se llama el opuesto de a; a-c significa a+(-c).

1.2.5. (ab)c = a(bc)

1.2.6. (ab) = b a

1.2.7. 1a = a

1.2.8. a(b+c) = ab + ac.

1.3. Leyes cancelativas para la suma y el producto

i. Si a+b = a+c, entonces b=c.

ii. Si y ca = cb, entonces a=b.

Demostracin de i.

Segn la propiedad 1.2.4., a+(-a) = (-a) +a = 0. Por lo tanto, a partir de + = + tenemos


() + ( + ) = () + ( + ) y aplicando las propiedades 1.2.1 y 1.2.3 se obtiene que b=c.

1.4. Otras propiedades. Para todo se cumple


i. a0 = 0
ii. -(-a) = a
iii. (-a)b = a(-b) = -(ab)
iv. (-a) (-b) = ab

Demostracin de i.
a0 = a(0+0) = a0 + a0 por las propiedades 1.2.3. y 1.2.8.; adems a0 = a0+0, por lo tanto,
a0+a0 = a0 + 0.

De donde a0 = 0 por la ley cancelativa para la suma.

1.5. Propiedades de orden. Existe un subconjunto de Z, llamado "enteros positivos" (en


smbolos Z+), con las siguientes propiedades:
1.5.1. Si a y b pertenecen a Z+, entonces a+b y ab pertenecen a Z+.

1.5.2. Dado cualquier : + o a=0 o + .

Las expresiones a < b, que se lee "a es menor que b" y b > a, que se lee "b es mayor que a"

son equivalentes y significan que .

1.6. Principio de Induccin Matemtica.

1.6.1. Conjuntos Inductivos. Intuitivamente se obtienen los enteros positivos, tomando como
punto de partida un primero, designado por "1" y formando 1 + 1 (llamado "2"), 2 + 1 (llamado "3"),
y as sucesivamente.

En virtud de que no se puede depender del significado un poco oscuro de "y as sucesivamente,"
y de que se debe tener una base para proporcionar teoremas relativos a los enteros positivos, se
d una definicin del conjunto de los enteros positivos, basada en el concepto de conjunto
inductivo.

1.6.2. Definicin. Un conjunto S de nmeros es un conjunto inductivo, s y slo s S tiene las


siguientes propiedades:
i. 1 S.
ii. a S > (a+1) S

Ejemplo: El conjunto de los enteros positivos es un conjunto inductivo.

Ejemplo: El conjunto de los nmeros reales es un conjunto inductivo.

Ejemplo: El conjunto S1={1,3,5,7,...}no es un conjunto inductivo, porque no obstante que


1 S1; (1+1) S1.

El conjunto Z+ es el conjunto de nmeros con la propiedad de que si k es cualquier conjunto


inductivo de nmeros, entonces Z+ k. Se dice, a veces, que el conjunto de los enteros positivos
es el "ms pequeo" conjunto inductivo de nmeros.

1.6.3. Teorema fundamental de Induccin Matemtica. Sea Sn una funcin proposicional cuyo
conjunto de referencia es Z+. Si Sn satisface las dos condiciones siguientes:

i. S1 es cierta.
ii. Sk > Sk+1 es cierta.

Entonces, Sn es cierta para todo n Z+.

Demostracin
Sea k el conjunto de todos los enteros positivos para el cual S n es cierta. Es decir:
k = {x/x Z+ Sn es cierta}

De i., se observa que 1 k.


De ii., se observa que k k, > (k+1) k.

Por tanto, k es un conjunto inductivo y por la definicin de k se sabe que k Z+ .

De otra parte, Z+ k. Por consiguiente, Z+ = k, es decir Sn es cierta para todo n Z+.


Arqumedes

Muchos de los maravillosos escritos de Arqumedes han sobrevivido, pero slo se conocen
algunos fragmentos de su vida. El gramtico BizantinoTzetzes refiere que Arqumedes muri a la
edad de setenta y cinco aos; puesto que muri en la cada de Siracusa, se deduce que naci
hacia el ao 287 a. J. C. Del historiador griego Diodoro aprendemos que estudi matemticas en
Alejandra; de Pappus, que escribi un libro sobre mecnica, SOBRE LA CONSTRUCCION DE
ESFERAS; de Cicern, que construy una esfera que imitaba el movimiento del sol, de la luna y
de los planetas; de Luciano, que incendi los barcos romanos mediante una disposicin de
espejos cncavos y cristales para quemar; de Ptolomeo, que hizo muchas observaciones
astronmicas; del filsofo romano Macrobio, que descubri las distancias de los planetas.

De Pappus , procede la no menos famosa narracin segn la cual Arqumedes, despus de haber
resuelto el problema: "Mover un peso dado mediante una fuerza dada", declar triunfalmente:
"Dadme un punto de apoyo y podr mover la tierra".

2.1. Algoritmo de la divisin. Dados los enteros a, b, con 0 existen enteros q y r tales que
= + 0 <
Al nmero a se le llama dividendo.
Al nmero b se le llama divisor.
Al nmero q se le llama cociente.
Al nmero r se le llama residuo.

En el caso particular que a y b sean enteros positivos, se trata de hallar el nmero de veces
que el dividendo contiene al divisor. Este nmero se llama cociente y lo que queda se llama
residuo.

Ejemplo: Si queremos hallar el resultado de dividir 19 entre 5 tenemos:


19 = 5 x 3 + 4, es decir que el cociente es 3 y el residuo 4.
Se puede observar que el residuo 4 es mayor que 0 y menor que 5, que es el divisor.

Ejemplo: Si queremos hallar el resultado de dividir 23 entre 7 tenemos:


23 = 7 x 3 + 2, lo que quiere decir que el cociente es 3 y el residuo es 2.

Cuando el residuo es cero, se dice que la divisin es exacta, y en este caso, se cumple que el
dividendo es igual al divisor por el cociente.

Si la divisin es exacta, se dice que el divisor b divide al dividendo a y esto se simboliza de la


manera siguiente

Lo anterior motiva la primera definicin de la seccin siguiente.


2.2. Divisibilidad

2.2.1. Definicin. Un entero a es divisible por un entero b, o b es divisor de a cuando el residuo es


cero. Por tanto, existe tal que a = b x c..

Ejemplo: 7 es divisor de 35 porque:


35 = 5 veces 7.
Se dice, entonces, que 7 l 35.

Ejemplo: 9 es divisor de 27 porque:


27 = 3 veces 9.
Se dice, entonces, que 9 l 27.

Cuando un entero b no es divisor de un entero a, se dice que b no divide a a o que b no es divisor


de a y se denota por b a.

2.2.2. Teorema. Todo entero que es divisor de otros es divisor de la suma de ellos.

Ejemplo: Sea 7 el nmero que divide a 35, 42 y 56.


Luego: 35 = 5 veces 7.
42 = 6 veces 7.
56 = 8 veces 7.

Sumando ordenadamente resulta:


133 = (5 + 6 + 8) veces 7.

Luego 133 = 19 veces 7. Se concluye que 7 divide a 133.


El teorema se demuestra generalizando este resultado. Sea d divisor de A, B, C y sean a, b, c sus
cocientes respectivos.

Luego: A = ad
B = bd
C = cd
Se concluye: A + B + C = (a + b + c)d

Lo anterior se puede reescribir de la forma siguiente:


Si d|A, d|B, d|C, entonces d|(A + B + C).

2.2.3. Teorema. Todo entero que es divisor de otro es tambin divisor de los mltiplos de ese otro.

Ejemplo: Como 2 divide a 6, luego 2 dividir a 4 x 6 = 24.

En efecto: 24 = 6 + 6 + 6 + 6.

Ahora bien: 2 divide a 6, luego, dividir a 4 veces 6, es decir, a 24, utilizando el teorema 2.2.2.

Generalizando, ,

2.2.4. Teorema. Todo entero que es divisor de otros dos es divisor de su diferencia.

Ejemplo: Si 3 que divide a 27 y a 18.


Se tiene: 27 = 9 veces 3.
18 = 6 veces 3.
Restando ordenadamente tenemos:
27 - 18 = (9 - 6) veces 3.
Luego, 9 = 3 veces 3.

Generalizando, si d es divisor de A y B tal que a y b son sus cocientes respectivos, entonces:


A = ad.
B = bd.

Restando ordenadamente se tiene:


A - B = (a - b)d.

Lo anterior se puede reescribir en la forma siguiente:


Si d|A y d|B, luego d|(A - B).

2.2.5. Teorema. Todo entero que divide a otros dos divide al residuo de la divisin de stos.

Ejemplo: Si 7 que divide a un dividendo 49 y a un divisor 35, como el residuo de dividir 49 entre 35
es 14, luego 7 divide a 14.

Generalizando este resultado se tiene:


Sea la divisin de A entre B con cociente q y residuo r y sea d un entero que es divisor de A y de B,
es decir:
A = Bq + r con < |B|.

Luego, A = Bq + r, por el algoritmo de la divisin.


Entonces, r = A - Bq.
Como d divide a B, dividir a Bq. Si divide a A y Bq divide tambin a su diferencia A - Bq. Luego, d
divide a r.

2.2.6. Teorema. Si dos enteros divididos por un tercero dejan residuos iguales, la diferencia de
estos dos nmeros es divisible por el tercero.

Demostracin
Sean a y b dos nmeros que divididos por d dejan residuo r y cocientes q y q respectivamente, o
sea:

a = dq + r.
b = dq+ r.

Restando ordenadamente, se tiene a - b = d(q - q). Luego d divide a la diferencia entre a y b.

Este teorema es de gran importancia cuando se estudia la teora de congruencias.

El recproco de este teorema tambin se cumple, es decir: si la diferencia de dos nmeros es


divisible por un tercero, entonces estos nmeros divididos por el tercero dan residuos iguales.

Carl Friedrich Gauss (1777-1855)

Es el matemtico ms grande del siglo diecinueve y uno de los tres ms grandes de todos los
tiempos. Los otros dos Arqumedes y Newton.
Gauss naci en Brunsvick, Alemania en 1977. Su padre, un trabajador pertinaz que fue
excepcionalmente obstinado, nunca crey en la educacin formal; hizo todo lo que pudo para
mantener a Gauss fuera de las escuelas. Afortunadamente para Carl, su madre, pese a no contar
tampoco con educacin formal, alent a su hijo en sus estudios y particip con orgullo de sus
logros hasta los das de su muerte, a la edad de 97 aos.
Gauss fue un nio prodigio. A la edad de 3 aos encontr un error en la contabilidad de su padre.

Cuando tena 15 aos, el Duque de Brunsvick advirti su talento y le ayud a ingresar a la


universidad. Titubeante entre las disciplinas de filosofa y matemtica, finalmente eligi las Ciencias
Matemticas despus de dos extraordinarios descubrimientos.

Primero, invent el Mtodo de los Mnimos Cuadrados, una dcada antes de que Legendre
publicara el resultado. Segundo, un mes antes de cumplir 19 aos, resolvi un problema cuya
solucin se haba buscado por ms de 2000 aos. Gauss mostr cmo construir, con slo comps
y regla, polgonos regulares cuyo nmero de lados no fuese un mltiplo de 2, 3 5, en particular el
polgono regular de 17 lados, que se inscribi sobre su tumba. A los 20 aos dio la primera
demostracin rigurosa del teorema fundamental del lgebra.

Gauss realiz un gran nmero de descubrimientos en fsica y en matemticas.

Por ejemplo, en 1801 us un nuevo procedimiento para calcular, con muy pocos datos, la rbita del
Asteroide Ceres. En 1833 invent el telgrafo electromagntico con su colega Weber. En 1811,
descubri un resultado que indujo a Cauchy a desarrollar la Teora de la Variable Compleja. Gauss
era un perfeccionista y es quiz el ltimo matemtico que saba todo de su materia. A su muerte,
en 1855, fue honrado con una medalla conmemorativa en la que se inscribi "De Jorge V, Rey de
Hnover, al Prncipe de las Matemticas".

2.3 Ejercicios resueltos

1. Usando el algoritmo de la divisin, demuestre que cada entero impar es de la forma 4k + 1 4k


+ 3, con k que pertenece a Z.

Solucin
Cualquier entero al ser dividido por cuatro deja residuo de 0 1 2 3.

Es decir, todo entero es de una de estas formas:


.4k; 4k + 1; 4k + 2; 4k + 3.

De lo anterior se tiene que cualquier nmero impar es de la forma


.4k + 1 4k + 3.

2. Usando el algoritmo de la divisin, demuestre que todo nmero entero se puede escribir en una
de las formas 3s, 3s + 1, 3s + 2.

Solucin
Sea n un entero cualquiera. Luego, al ser dividido por 3, se obtiene residuo de 0 1 2. Entonces,
se cumple alguno de los tres casos:

n = 3s
n = 3s + 1;
n = 3s + 2;

donde s es el cociente entero de dividir n por 3.

3. Muestre con un contraejemplo que si a|(b + c) no necesariamente a|b a|c.

Solucin
Sea a = 4; b = 5; c = 3.

Se cumple 4|(5 + 3) pero .

4. Muestre que si a es un entero arbitrario, luego 2|a(a + 1).


Solucin.
Si a es par, entonces, a(a + 1) es par.
Por tanto, a (a + 1) = 2s, luego, 2|a(a+1).

Si a es impar luego a + 1 es par, o sea que a (a + 1) es par.


Por tanto, a (a + 1) = 2k, luego, 2|a(a+1).

5. Muestre que la diferencia entre dos cubos consecutivos nunca es divisible por 2.

Solucin.
Sean n3 y (n + 1)3 esos cubos.
Luego, (n + 1)3 - n3 = n3 + 3n2 + 3n + 1 - n3.

Pero n2 + n = n (n + 1), siempre es par por el ejercicio # 4. Luego 3(n2 + n) = 1 es impar.

Por tanto, .

6. Cules son los enteros que divididos por 5 dejan 3 por residuo?

Solucin.
Sean todos los enteros que al dividirlos por 5 dejan 3 por residuo.

Luego, .
O sea que son todos los enteros de la forma .

7. Demuestre que si dos enteros no son divisibles por 3, entonces, su suma o su diferencia es
divisible por 3.

Solucin.
Si a y b son dos enteros que no son divisibles por 3 es porque son de una de estas dos formas.

a = 3k + 1
b= 3t + 2

Luego: a + b = 3k + 3t + 3 = 3(k + t + 1))

O sea que 3|(a + b).

O de la forma siguiente:

a = 3k + 1
b = 3t + 1

Por tanto: a - b = 3k - 3t = 3(k - t)

O sea que 3|(a - b).

que se trabaja de manera similar.

8. Demuestre que el cuadrado de un entero que no es divisible por 3 es mltiplo de 3 ms 1.


Solucin.
Si un entero no es divisible por 3, es porque corresponde a una de estas dos formas:

a = 3s + 1

a = 3s + 2

Si , a = 3s + 1, a2 = 9s2 + 6s + 1.
Entonces, a2 = 3(3s2 +2s) + 1.
a2 = 3t + 1, que es mltiplo de 3 ms 1.

Si , a = 3s + 2, a2 = 9s2 + 12s + 4.
a2 = 3(3s2 + 4s + 1)

entonces, a2 = 3t + 1, que es mltiplo de 3 ms 1.

2.4 Ejercicios propuestos

1. Encuentre todos los enteros positivos n tales que 28 + 211 + 2n sea un cuadrado perfecto.

2. Resuelva este problema: Juanito sale de casa con varios caramelos y vuelve sin
ninguno.
Su madre le pregunta: qu ha hecho con ellos?
El responde:
- A cada amigo que me encontr le d la mitad de los caramelos que llevaba ms uno.

con cuntos amigos te encontraste?


- Con seis.

Con cuntos caramelos sali Juanito?

3. Demuestre que si dos enteros a y b divididos por un tercero c dan residuos iguales, los
productos am y bm divididos por c darn tambin residuos iguales.

4. Si a, b, c divididos por d, dan como residuos r, r' y r'' respectivamente, demuestre que la
suma de a + b+ c, dividida por d, da el mismo residuo que la suma dividida por d.

5. Demuestre: Si a es un mltiplo de b ms uno, entonces todas las potencias de a son


mltiplos de b ms uno.

6. Un alumno, al dividir un entero positivo por 8, obtuvo 4 por residuo; y al dividir el mismo
nmero por 12, le dio por residuo 3. Demuestre que el alumno cometi un error.

7. Demuestre que el cuadrado de un nmero que no es mltiplo de 5 es mltiplo de 5 ms


o menos 1.

8. Demuestre que la suma de dos enteros impares consecutivos siempre es divisible por 4.

9. Frmense los nmeros 49; 4489; 444889; 44448889... etc. obteniendo cada uno
intercalando 48 en el centro del numero anterior. Demostrar que son cuadrados perfectos y
hallar la raz cuadrada del que consta de 2n cifras.

10. Halle los nmeros que al ser divididos por 31, dejan residuos que son iguales al triple
de su respectivo cociente.
3.1 Mximo Comn Divisor

3.1.1. Definicin. Se llama comn divisor de dos enteros a un entero que los divida exactamente.

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

3.1.2. Definicin. Se llama mximo comn divisor de dos enteros, al menos uno de ellos diferente
de cero, al mayor entero que los divide exactamente.

De la definicin anterior es claro que el mximo comn divisor de dos enteros es siempre un entero
positivo.

Ejemplo: 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 mximo comn divisor de 24 y 27 es 3.

Ejemplo: Halle el mximo comn divisor de 32 y 48.


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

Luego, el mximo comn divisor de 32 y 48 es 16.

Si d es el mximo comn divisor de dos nmeros a y b se escribe:


d = M.C.D.(a, b).

3.1.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: como M.C.D. (24, 27) = 3. Entonces se cumple 3 = 27*(1) + 24*(-1).


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

Ms adelante se estudiar un mtodo expedito para hallar x y y.

3.1.4. Definicin. Dos enteros a y b, no ambos cero, se llaman primos relativos si M.C.D. (a, b) =
1.

Ejemplo: Sea a = 28, sus divisores positivos son {1, 2, 4, 7, 14}.


b = 25, sus divisores positivos son {1, 5}.

El nico divisor comn es 1. Luego 25 y 28 son primos relativos.

3.1.5. Teorema. Dados dos enteros a y b, no ambos cero, a y b son primos relativos s y slo s
existen enteros x e y tales que 1 = ax + by.

Demostracin: 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 los teoremas 2.2.2. y 2.2.3. se tiene que d|ax +
by, o sea que d|1. Necesariamente d = 1.


3.1.6. Corolario. Si M.C.D.(a, b) = d, entonces, se tiene que M.C.D. ( , ) = 1.


Recprocamente, si d|a, d|b y M.C.D. ( , ) = 1. entonces, M.C.D. (a,b) = d.

Ejemplo: como M.C.D. (24, 27) = 3, entonces, se cumple que

24 27
M.C.D. ( , )= M.C.D.(8, 9) = 1.
3 3

3.1.7. Teorema. Sean a, b, c enteros. Si a|c y b|c y M.C.D. (a, b) = 1, entonces, ab|c.

Demostracin
Como: a|c, c = ar para algn r.
b|c, c = bs para algn s.

Sea d = M.C.D. (a, b). Por tanto, d = 1, de ac se concluye que 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 abc.

Euclides

De este matemtico griego, se sabe poco de su vida y su carcter, pero probablemente pas sus
aos de instruccin en Atenas, antes de aceptar la invitacin de Ptolomeo para instalarse en
Alejandra. Ense, durante veinte o treinta aos, escribiendo sus conocidos ELEMENTOS y
muchas otras obras de importancia.

Se nos ha transmitido la imagen de un hombre de estudio, genial, modesto y escrupulosamente


honrado, siempre pronto a reconocer el trabajo original de otros y visiblemente amable y paciente.

En los Elementos, Euclides comenz a escribir una descripcin exhaustiva de las matemticas,
tarea colosal an en su tiempo. Su obra consta de trece libros. Los libros VII, VIII y IX son
aritmticos y dan una descripcin interesante de la Teora de Nmeros. Se introducen los nmeros
primos y compuestos, distincin relativamente tarda; tambin, por primera vez, el M.C.D. y el
m.c.m. de los nmeros, la teora de las progresiones geomtricas y el teorema am+n=am.an, junto
con el mtodo de sumar la progresin, mediante una hermosa utilizacin de las razones iguales.
Euclides utiliz este mtodo, incidentalmente, para presentar sus nmeros perfectos tales como 6,
28, 496, cada uno de los cuales es igual a la suma de sus factores.

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

Demostracin
Como M.C.D.(a, b) = 1 luego 1 = ax + by para algn par de enteros x e y.

Luego, c = (ac)x + (bc)y.

Se sabe lo siguiente: a|ac que es evidente.

a|bc por hiptesis. Se sigue, entonces, a|(ac)x + (bc)y; de donde a|c[(ax+by)].

Se concluye que a|c.

Ejemplo: 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 12 9 y 12 8, y esto no se cumple porque


.
3.2.1. 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) Si c|a y c|b entonces, c|d.

Ejemplo: Sean a = 28, b = 42.

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

Vemos que M.C.D.(28, 42) = 14. Los dems divisores son 1, 2 y 7 y cumplen que 1|14; 2|14; 7|14.

3.2.2. Definicin. Un entero p > 1 es primo s y slo s sus nicos divisores positivos son 1 y p. Un
entero mayor que 1 que no es primo se llama compuesto.

Ejemplo: 2, 3, 5, 7, 11, 17, 19 son nmeros primos.

Ejemplo: 4, 6, 8, 12, 15, 24 son nmeros compuestos.

3.2.3. Teorema. Para todo entero , M.C.D (ka, kb) = | k | x M.C.D (a,b) siendo a, b enteros,
no ambos cero.

3.3 Ejercicios resueltos

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

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

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

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

Entonces, n4+4 es compuesto.

3. Demuestre que s p>5 y p primo, se cumple que p2+2 es compuesto.

Solucin
Todo primo p mayor o igual que 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 completo.

Si p = 6k+5, p2+2 = 36k2+60k+27


p2+2 = 3(12k2+20k+9) que es completo.
4. Demuestre que para cada entero a, se cumple que M.C.D.(a, a + 1) = 1

Solucin
Sea d = M.C.D.(a, a + 1). Luego d|a y d|(a + 1).

Entonces, tambin es divisor de la diferencia entre ellos (teorema 2.2.4.).

Luego, d|(a + 1) - a o sea d|1. Necesariamente, d = 1 porque d es un nmero positivo.

5. Demuestre que M.C.D.(-a, b) = M.C.D.(a, b).

Solucin
Sea d = M.C.D.(-a, b), luego, d|-a y d|b.

Como -a|a, por transitividad d|a.

Entonces, d es divisor comn de a y b. Veamos cul es el mximo comn divisor de a y b.

Sea c tal que c|a y c|b. Como a|-a, c|-a. Entonces, c es divisor comn de -a y b. Como d es el
mximo comn divisor de -a y b, entonces .

6. Demuestre que si es tal que , entonces 24|(a2-1) .

Solucin.
Si entonces a=4s+1 (1): o a=4s+3 (2)

Si entonces: a=3r+1 (3)


a=3r+2 (4)

Se consideran los casos (1) y (3); (1) y (4); (2) y (3); (2) y (4).

Veamos el caso (1) y (3):

Como a=4s+1, luego a2=16s2+8s+1


a2=8k+1,

Entonces, a2-1=8k, de ac se tiene 8|(a2-1).

Como a=3r+1, luego a2=9r2+6r+1


a2=3t+1,

Entonces, a2-1=3t, de ac se tiene 3|(a2-1).

Como 3|(a2-1) y 8|(a2-1) y M.C.D. (3, 8) =1, luego por el lema de Euclides se tiene: 3*8|(a 2-1 ).

O sea 24|(a2-1 ). Una argumentacin similar se sigue en los dems casos.

7. Muestre que si M.C.D. (u, v) = 1, entonces M.C.D. (u + v, u - v) es 1 2.

Solucin.
Sea d = M.C.D.(u + v, u - v). Luego, d|u + v y d|u - v.

Entonces, d|1(u + v) + 1(u - v), o sea d|2u.


Tambin, d|1(u + v) -1(u - v), o sea d|2v.

De ac se tiene que d es divisor comn de 2u y 2v.

En particular, se tiene que d|M.C.D.(2u, 2v).

Pero M.C.D. (2u, 2v) = 2 M.C.D. (u, v) = 2 porque M.C.D. (u, v) = 1. Luego, d|2. La nica
posibilidad es que d = 1 d = 2

3.4 Ejercicios propuestos

1. Demuestre que el mximo comn 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 d = M.C.D.(a, b, c), entonces, se cumple que existen enteros x, y, z tales que d =
ax+by+cz.

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 pruebe que M.C.D. (2a+b, a+2b) es 1 3.

7. Demostrar que si n es un entero entonces es divisible por 6.

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

9. Si el mximo comn divisor de dos nmeros es 21 y la relacin entre ellos es de 5 a 8,


halle los nmeros.

10. Si el mximo comn divisor de dos nmeros es 2, y su producto es 840, halle los dos
nmeros.

11. Dados los enteros a y b, no ambos cero, pruebe que M.C.D. (a, b) = m.c.m, (a, b) s y
slo s a = b.

4.1. Algoritmo de Euclides. El mximo comn divisor de dos enteros puede obtenerse
escogiendo el mayor de todos los divisores comunes. Hay un proceso ms eficiente que utiliza
repetidamente el algoritmo de la divisin. Este mtodo se llama algoritmo de Euclides.
El algoritmo de Euclides se describe de la forma siguiente: dados dos enteros a y b, cuyo
mximo comn divisor se desea hallar, y asumiendo que a b > 0, (El mtodo funciona
tambin si a y b son negativos. Basta trabajar con los valores absolutos de estos nmeros,
debido a que M.C.D(| a |, | b |) = M.C.D (a,b) se siguen los siguientes pasos:

a) Se usa el algoritmo de la divisin para obtener = 1 + 1 con 0 1 < .

Si = 0, entonces, b|a y M.C.D.(a, b) = b.

b) Si 1 0 se divide b por 1 y se producen enteros 2 y 2 que satisfacen

b= + con .

Si = 0 el proceso termina y M.C.D.(a, b) = .

c) Si se procede a dividir por ,

obteniendo .

d) Este proceso continua hasta que algn residuo cero aparece. Esto ocurre porque en la
secuencia > 1 > 2 > 0 no puede haber ms de b enteros. Es decir, el proceso es finito.

e) En estas circunstancias, el mximo comn divisor de a y b no es ms que el ltimo residuo


no cero del proceso anterior.

Esto lo garantiza la aplicacin reiterada del siguiente teorema.

4.1.1. Teorema. Si a y b son enteros positivos con


entonces M.C.D.(a, b) = M.C.D.( b, r ).

Demostracin
Sea d = M.C.D.(a, b). Luego d | a y d | b. De donde d | (a+qb) por los teoremas 2.2.3. y 2.2.4.

Como a+qb = r, se tiene que d | r.

Luego d es divisor comn de b y r.

Por otra parte, sea c un divisor comn de b y r, luego c | (qb + r) por teorema 2.2.2. y 2.2.3.

Como qb + r = a, entonces, c | a. De lo anterior tenemos que c es un divisor comn de a y b.

Como d = M.C.D.(a, b) se tiene que .

Luego, d = M.C.D. (b, r).

Ej: Halle M.C.D. (12.378, 3.054).

Solucin
12.378 = 4x3.054 + 162

3.054 = 18x162 + 138


162 = 1x138 + 24

138 = 5x24 + 18

24 = 1x18 + 6

18 = 3x6 + 0

Luego M.C.D. (12.378, 3.054) = 6 que es el ltimo residuo no cero.

Ejemplo: Como el M.C.D. (12.378, 3.054) = 6 podemos utilizar el ejercicio anterior para
encontrar enteros x y y que cumplan la condicin: 6 = 12.378x + 3.054y.

6 = 24 - 18

= 24 - (138 - 5x24)

= 6x24 - 138

= 6x (162 - 138) - 138

= 6x162 - 7x138

= 6x162 - 7x(3.054 - 18x162)

= 132x162 - 7x3.054

= 132x(12.378 - 4x3.054) - 7x3.054

= 132x12.378 + (- 535) x3.054

Luego, x = 132; y = -535

Diofanto de Alejandra

Fue un gran matemtico griego que dio fama a Alejandra, hacia el ao 280 d. J. C.

Diofanto se dedic al lgebra, como indican los trminos de un epigrama griego que nos relata
la corta historia de su vida. Su infancia dur 1/6 de su vida; su barba creci despus de 1/12
ms; se cas despus de 1/7 ms, y su hijo naci cinco aos ms tarde; el hijo vivi hasta la
mitad de la edad de su padre, y el padre muri cuatro aos ms tarde que su hijo.

Si x es la edad a la cual muri, entonces:

y Diofanto debi haber vivido hasta los ochenta y cuatro aos de edad.

De los principales escritos de Diofanto se conservan algunos: son seis de los trece libros que
formaban la ARITHMETICA, y fragmentos de sus nmeros POLIGONALES y PORISMAS. Su
obra perenne se halla en la teora de nmeros y de Ecuaciones Indeterminadas.
Se interes especialmente por ecuaciones cuadrticas y otros tipos ms elevados, como por

ejemplo la ecuacin: .

Hall cuatro nmeros enteros positivos x, y, z, u para los cuales esta afirmacin es cierta.

Siglos ms tarde, sus pginas fueron vidamente ledas por Fermat, el cual demostr que la

ecuacin no tiene solucin en los enteros positivos.

También podría gustarte