Documento Teoria Del Numero

8/10/2019 Documento Teoria Del Numero

1/72

MINISTERIO DE EDUCACIN

CURSO DE POSGRADO PARA PROFESORES DE EDUCACIN MEDIA

TEORA DEL NMERO

EQUIPO DE DISEO:

AARN ERNESTO RAMREZ FLORES

ERNESTO AMRICO HIDALGO CASTELLANOS

CARLOS MAURICIO CANJURA LINARES

CARLOS ERNESTO GMEZ RODRGUEZ

CLAUDIA PATRICIA CORCIO

HUMBERTO ALFONSO SERMEO VILLALTA

JUAN AGUSTN CUADRA

DIMAS NO TEJADA TEJADA

OSCAR ARMANDO HERNNDEZ MORALES

SIMN ALFREDRO PEA

CIUDAD UNIVERSITARIA, NOVIEMBRE DE 2010

1


2/72

ndice

I Divisibilidad en Z 4

1. Divisibilidad en Z 41.1. Mltiplos de un entero relativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2. Relaciones de divisibilidad en Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3. Propiedades de la divisibilidad en Z . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2. La Divisin Euclidiana 72.1. La Divisin Euclidiana en N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2. La Divisin Euclidiana en Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Sistemas de Numeracin 12Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12Otros sistemas de numeracin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Problemas de cambios de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Bsqueda de la base de un sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

II MCM, MCD 19

1. Mximo Comn Divisor 191.1. El Mximo Comn Divisor (MCD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.2. Resultados inmediatos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2. Mximo Comn Divisor (continuacin) 212.1. Investigacin del MCD. Algoritmo de Euclides. . . . . . . . . . . . . . . . . . . . . . 212.2. Un resultado importante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3. Teorema de Bezout 243.1. Denicin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.2. Caracterizacin: El Teorema de Bezout . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4. Caractersticas y Propiedades del MCD 274.1. Caractersticas y Propiedades del MCD . . . . . . . . . . . . . . . . . . . . . . . . . 274.2. Resultado: Propiedad multiplicativa del MCD . . . . . . . . . . . . . . . . . . . . . . 27

5. Aplicaciones 285.1. Teorema de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285.2. Fracciones irreducibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

6. Mnimo Comn Mltiplo 30

6.1. Denicin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306.2. Resultados fundamentales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306.3. Caracterizaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2


3/72

Algoritmo para calcular los coecientes de las relaciones de Bezout 34Determinar u y v a travs de un ejemplo numrico . . . . . . . . . . . . . . . . . . . . . . 34Generalizaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Solucin de la ecuacin au + bv = c 34Presentacin del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34Estudio de un caso particular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Caso general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

III Las Congruencias. 44Actividad 1. El lenguaje de las Congruencias . . . . . . . . . . . . . . . . . . . . . . . . . 44Actividad 2. Los das de la semana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Actividad 3. Restos de Potencias de un entero en una divisin . . . . . . . . . . . . . . . . 47

1. Congruencias mdulo m . 471.1. Deniciones Equivalentes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471.2. Reglas de clculo de las Congruencias. . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2. Aplicacin de las Reglas de Clculo de las Congruencias. 49

3. Resolucin de la ecuacin ax b (mod m) 50Trabajo Dirigido: Criterios usuales de divisibilidad. 52

IV Los nmeros primos 62

1. Denicin. Los nmeros primos 621.1. Denicin y existencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621.2. Todos los nmeros primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

2. Descomposicin en productos de los nmeros primos. 632.1. Teorema Fundamental . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632.2. Investigando los divisores de un nmero natural no primo . . . . . . . . . . . . . . . 642.3. El Mximo Comn Divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642.4. LAS POTENCIAS DE UN NMERO Y LA DESCOMPOSICIN CANNICA. . . 64

3. Nmeros primos y divisibilidad en N 653.1. Divisibilidad por un nmero primo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653.2. El Pequeo Teorema de Fermat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653.3. Ejercicios de Nmeros Primos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3


4/72

Parte IDivisibilidad en Z

1. Divisibilidad en Z1.1. Mltiplos de un entero relativo

Denicin: Diremos que el entero m es un mltiplo de el entero b, si existe un entero c tal quem = bc.

Por ejemplo, los mltiplos de 3 son todos los nmeros 3c, con c un entero; as -12 y 342 sonmltiplos de 3 ya que 12 = 3( 4) y 342 = 3(114) .

1.2. Relaciones de divisibilidad en ZDenicin: Un entero b divide a otro entero a siempre y cuando exista un entero c tal que a = bc.

De manera equivalente, se dir que a es un mltiplo de b, o tambin que b es un divisor de a , oque a es divisible por b.

Notas:

Todo nmero divide a 0, pero 0 no divide a ningn nmero.

1 y -1 dividen a todos los enteros.

Ejemplos:

1. 3 divide a 54 ya que 54 = (3)(18) . Los enteros 3 y 18 son divisores de 54.

2. -5 divide a 45 por que 45 = 5(9) ; -5 divide a 45 por que 45 = 5(9).3. a) Encontrar todos los divisores en N de 21b) Encontrar todos los pares (a, b ) de nmeros naturales N tales que a 2 b2 = 21 .

Solucin

a) De acuerdo a la denicin, 21 lo podemos escribir como 21 = 1 21, as como 21 = 3 7, ycualquier otra forma de escribir como producto de dos (o ms) nmeros tiene, necesariamentecualquiera de estas dos formas, luego los divisores son 1, 3, 7 y 21.

b) Recordemos que a 2 b2 = ( a + b)(a b) de aqu que (a + b)(a b) = 21 y como de acuerdo alliteral anterior las nicas formas de escribir como factor a 21 son 1

21 y 3

7 as:

a + b = 21 y a b = 1 luego (10, 11) es un par y como tambin a + b = 7 y a b = 3 luego (5,2) esotra posibilidad, y como los pares deben ser naturales, estas son las nicas posibilidades.

4


5/72

1.3. Propiedades de la divisibilidad en Za) Si b divide a a entonces b tambin lo divide.Prueba.

Como b divide a a , esto signica que existe c tal que a = bc, pero esto tambin puede escribirsea = (b)(c) de esto se tiene que b tambin divide a a .

b) Si b divide a a y si a = 0 , entonces |b| |a |Prueba.

Como b divide a a , esto signica que existe c tal que a = bc, y esto implica que

|a | = |bc| |a | = |b| |c|, luego como |c| = 0 se tiene que |b| |a |.Observacin: Cuando a y b son naturales y a = 0 , si b divide a a , entonces b a . Pero cuando a yb son de signo cualesquiera, ese resultado no es cierto.

c) Si a divide a b y b divide a a, entonces a = b o a = b; (a = 0 , b = 0) .Prueba.

Como por hiptesis a divide a b por la propiedad b) |a | |b| y como tambin b divide a a denuevo por la propiedad b) |b| |a |, luego esto es cierto solamente en el caso que |a | = |b|.

d) Si a divide a b y si b divide a c, entonces a divide a c.

Prueba.Por hiptesis podemos decir que b = ak 1 y c = bk2 ; con k1 y k2 enteros, luegoc = bk2 =c = ( ak 1 )k2 y como el producto de dos enteros, es otro entero, entonces c = a (k1 k2 ) dedonde se deduce que a divide a c.

e) Si a divide a b y c, entonces a divide a b + c, b c, y de manera general divide a todo entero dela forma bx + cy, con x e y enteros.Prueba.

Por hiptesis podemos decir que b = ak 1 y c = ak 2 ; con k1 y k2 enteros. Si d = bx + cy, con x e y

enteros, entonces:d = ak 1 x + ak 2 y = d = a (k1 x + k2 y); puesto que (k1 x + k2 y) es un entero, podemos concluirque a divide a d.

5


6/72

Si hacemos x = y = 1 , entonces d toma la forma b + c y como a divide a d, podemos concluir quea divide a b + c.

De al misma forma haciendo x = 1 y y = 1, puede concluirse que a divide a b c.

f ) Si a divide a b, entonces ac divide a bc, para cualquier entero c.

Prueba.

Como Si a divide a b, esto de acuerdo a la denicin signica que b = ak 1 , luegobc = ak 1 c =bc = ac (k1 ) y se tiene el resultado.

UNA PROPIEDAD NOTABLE DEL CONJUNTO N .

Los subconjuntos de N poseen la propiedad siguiente: Todo subconjunto E de enteros

estrictamente positivos posee un mnimo.Por ejemplo si E es el conjunto de nmeros de la forma 2n + 5 , con n 0, n Z el elementomnimo de E es el 5.Esta propiedad no es cierta en todo Z . Veamos por ejemplo que si tomamos los nmeros menoresque 20 notamos que no hay elemento mnimo.

COMENTARIO

Para trabajar la hiptesis b divide a a escribimos a = bq con q Z , ya que una igualdadfacilita los clculos.Observacin: Podemos ver de lo anterior que b no nulo divide a se traduce en la expresinab

= q con q entero. Esto es evidentemente equivalente a escribir a = bq .

Lo esencial en las dos formas de escribir esta expresin es dejar claro que q debe ser entero.

Para interpretar una igualdad entre nmeros enteros, pensemos que la hiptesis p = mq con m y q enteros, signica que m divide a p y tambin q divide a p.

EJEMPLOS RESUELTOS. Como utilizar la divisibilidad para encontrar los divisores comunes ados nmeros enteros:

Ejemplo 1. Si k es un nmero natural, a = 9k + 2 y b = 12k + 1 . Pruebe que los nicos divisorespositivos posibles a los enteros a y b son 1 y 5.

Solucin

6


7/72

Sea d un divisor comn de a y b. (Dos enteros siempre tienen por lo menos un divisor comn: el 1.Por esta razn es posible comenzar dndonos un nmero d divisor comn de a y b, sin justicar laexistencia de tal divisor). Para encontrar los valores posibles de d, un mtodo consiste en utilizarla propiedad e) que establece que si d divide a a y b tambin divide a todo entero de la forma

ua + vb con u y v enteros cualesquiera. As d divide a u (9k + 2) + v(12k + 1) .Este mtodo se consigue dando valores a u y v con el n de eliminar k . As por ejemplo escogiendou = 4 y v = 3 tenemos que d divide a 36k + 8 36k 3 lo cual vale 5. Luego los valores posiblesde d son 1 y 5.

Observacin: La eleccin de u = 4 y v = 3 que nos condujo a 36k y 36k , es la mejor por que 36es el mnimo comn mltiplo de 9 y 12.Si hubisemos elegido u = 12 y v = 9 se introduce un factor 3 adicionalEjemplo 2. Sea k un nmero natural, a = 13k + 1 y b = 26k + 4 . Probar que los divisorespositivos y comunes a a y b son 1, 2, 3 y 6.Solucin:

De nuevo por la propiedad e) como en el ejemplo anterior, d divide a u (13k + 1) + v(26k + 4) .En este caso 26 es mltiplo de 13 haciendo u = 2 y v = 1 , tendramos qued |26k + 2 + ( 26k) + 4 d|6 , es decir, d puede tomar los valores de 1, 2, 3 y 6.

2. La Divisin EuclidianaUno de los procesos algortmicos, que en matemtica mayor dicultad representa en el proceso

de aprendizaje temprano de la matemtica, es el de la divisin, el cual aunque hemos aprendido,en muchos casos no tenemos idea de cual es el proceso matemtico que est inmerso en el. En estecaso se dar por descontado que tal algoritmo en la manera tradicional, es conocido y se tratar deir un poco mas all, dada la importancia de este proceso en teora de nmeros.

2.1. La Divisin Euclidiana en NSi queremos dividir a un nmero b entre otro nmero a , bsicamente lo que tratamos de hacer

es aproximar de manera lo mejor posible a b por un mltiplo de a, la diferencia entre b y esemltiplo de a es lo que llamaremos el resto de la divisin, que ser nulo exactamente en el caso deque b sea mltiplo de a . Precisemos un poco acerca de todo esto.

Siendo a un nmero natural, la secuencia 0, a, 2a, 3a, ... de mltiplos no negativos de a esestrictamente creciente; luego, alguno de ellos ser mayor que b y siempre podemos elegirlo de talmanera que el anterior no supere a b (Por el principio de buena ordenacin de los nmerosnaturales). Esto es, existe exactamente un entero no negativo q tal que:

qa b < (q + 1) a

7


8/72

Utilizando un lenguaje un poco mas informal, observemos que no hemos hecho otra cosa queubicar a b entre dos mltiplos consecutivos de a . El siguiente esquema ilustra tal situacin:

Puesto que dos mltiplos consecutivos de a dieren en a , es claro entonces que la diferencia b qa ,que designaremos por r , es menor que a . En resumen, quedan determinados dos enteros q y rvericando las dos condiciones siguientes:

b = qa + r

0 r < aLa segunda condicin es a la que nos referamos cuando hablbamos de manera lo mejor posible.Concretamente, qa es el mltiplo de a mas cercano a b entre los que son menores o iguales que b.

Para nalizar , veamos que q y r son los nicos enteros que verican las dos condicionesanteriores. Supongamos para ello que p y s son otro par de nmeros que satisfacen las doscondiciones anteriores, es decir que b = pa + s , siendo s alguno de los nmeros 0, 1, 2,...,a 1. Sifuera por ejemplo que p > q (el caso p < q es similar), restando las dos igualdades tenemos:

0 = ( p q )a + ( s r ) = ( p q )a = r s .En consecuencia, r s es positivo y adems es mltiplo de a , pero por otro lado, la condicin delresiduo nos establece que r s r < a , lo cual es posible solamente si r s = 0 =r = s y esto asu vez establece la igualdad entre p y q .Acabamos de demostrar un teorema muy importante en la teora de nmero:

Teorema. Dados dos nmeros naturales a y b, existe un nico par de enteros q y r (que llamaremos el cociente y el resto de la divisin entera de a por b, respectivamente) satisfaciendolas dos siguientes condiciones:

a = bq + r y 0 r < bDenicin: Efectuar la divisin euclidiana en N de un nmero natural a por el nmero natural b,b = 0 consiste en encontrar los pares de naturales (q, r ) tales que a = bq + r y 0 r < b .Nota: El residuo o resto es estrictamente menor que el divisor.

Ejemplo. La divisin euclidiana de 114 por 8 es 114 = 8 14 + 2 , 0 2 < 8.

Ejemplo. Encontrar un nmero natural que al dividirse por 23 nos de resto 1 y que al dividirsepor 17 nos da el mismo cociente y por residuo 13.

8


9/72

Solucin

Sea n el nmero natural buscado, luego por la primera condicin del problema n puede escribirse:n = 23q + 1 y por la segunda condicin: n = 17q + 13 , lo cual nos da un sistema de dos ecuacionescon dos incgnitas, el cual es resoluble, por ejemplo utilizando el mtodo de igualacin, luego:

23q + 1 = 17 q + 13

23q 17q = 13 16q = 12

q = 2

Y sustituyendo este valor en cualquiera de las dos ecuaciones originales: n = 23(2) + 1 y de estoresulta n = 47 , que nos da el nmero buscado, el cual es nico en N .

Ejemplo. Encuentre todos los nmeros naturales N tales que n + 1 | n 2 + 1 .Solucin.

Este problema nos brinda la posibilidad de utilizar el algoritmo de la divisin en un contexto muyinteresante, tratando de construir el divisor; veamos:

n + 1 = n 1 + 2 = n + 1 = ( n + 1)( n 1)+2 , luego por la propiedad e) n + 1 debe dividir ala suma, esto obliga a que n + 1 divida a 2, y los nicos divisores de este nmero son el 1 y elmismo (mas adelante se denir de manera formal el concepto de nmero primo) es decirn + 1 = 1 o n + 1 = 2 y de aqu se deduce que n solamente puede valer 1.

Observacin: Decir que b divide a a , es equivalente a decir que la divisin euclidiana de a por b elresto es nulo.

Ejercicio: Utiliza la idea del ltimo ejemplo, para resolver: Si 7 | (3x + 2) pruebe que7 | (15x 2 11x 14).

2.2. La Divisin Euclidiana en ZLa divisin euclidiana se generaliza a dos nmeros enteros cualesquiera, a travs del siguiente

resultado:

a y b son dos nmeros enteros cualesquiera y b es no nulo. Entonces existe un nico entero q y un nico entero positivo r , tales que a = bq + r y 0 r < |b|.Para comprender ms.

Que condicin debe cumplir la igualdad a = bq + r , entre dos nmeros naturales para quenecesariamente pueda ser traducida en la divisin euclidiana de a por b?La condicin 0 r < b es indispensable para que la igualdad a = bq + r sea equivalente a ladivisin euclidiana.

9


10/72

Comentario: una consecuencia fundamental del primer teorema es la siguiente:

Si b es un nmero estrictamente positivo, se puede expresar cualquier nmero natural en funcinde b y de sus restos posibles de su divisin euclidiana por b

En efecto, los posibles restos de dividir por b cualquier nmero son 0, 1, 2,...,b 1 as todo nmeronatural n puede escribirse n = bq + r con r = 0 1 2,..., b 1.As por ejemplo todo nmero natural n puede escribirse como 6 p 6 p + 1 6 p + 2 6 p + 3 6 p + 4 6 p + 5 con p un nmero natural.

Todo nmero natural n puede escribirse como 2 p (Que le diremos par) como 2 p + 1 (quellamaremos impar) con p un nmero natural.

Ejemplo 1. Si a = 37 , b = 11 escribimos 37 = 11 3 + 4 que es el mismo caso de la divisineuclidiana en N , luego podemos escribir 37 = (11) (3) + 4 (Ntese que q = 3 y r = 4 ,r < |11|)

Ejemplo 2. Si a = 37, b = 11 de nuevo escribimos 37 = 11 3 + 4 que es el mismo caso de ladivisin euclidiana en N , luego podemos escribir 37 = (11) (3) 4 , pero hemos denido elresto como un nmero positivo menor que 11, para lo cual nos valemos de reescribir en la forma:37 = (11) (3) 4 + 11 11 y esto, operando y agrupando convenientemente se convierte en:37 = (11) (4) + 7 . (Ntese que q = 4 y r = 7 , r < |11|).Ejemplo 3. Si a = 37, b = 11 escribimos 37 = 11 3 + 4 que es el mismo caso del ejemplo 2,37 = ( 11) 4 + 7 . (Ntese que q = 4 y r = 7 , r < |11|).Ejemplo 4. Veamos una ilustracin de como utilizar el comentario del teorema 1 efectuado arriba. Demostrar que para todo nmero natural n , n (n + 1)(2 n + 1) es divisible por 3.

Demostracin

Sea a = n (n + 1)(2 n + 1) vamos a demostrar que a tiene la forma 3q con q entero, utilizaremos elhecho de que todo natural es de la forma 3 p 3 p + 1 3 p + 2 , esto reduce a vericar tres casospara valores de n, es decir si n = 3 p 3 p + 1 3 p + 2 .

Veamos el primer caso:

Si n = 3 p entonces a = 3 p(3 p + 1)(6 p + 1) = 3 q 1 con q 1 = (3 p + 1)(6 p + 1) .

Si n = 3 p + 1 entonces a = (3 p + 1)(3 p + 4)(6 p + 3) = 3 q 2 con q 2 = (3 p + 1)(3 p + 4)(2 p + 1) .

Y nalmente, si n = 3 p + 2 entonces a = (3 p + 2)(3 p + 3)(6 p + 5) = 3 q 3 conq 3 = (3 p + 2)( p + 1)(6 p + 5) . Lo que completa la prueba

Ejemplo 5. Cules son los posibles restos de dividir un cuadrado por 4? y por 8?Solucin.

10


11/72

De nuevo utilizaremos la tcnica descrita en el ejemplo anterior, ahora las formas posibles deescribir un nmero natural n cuando se divide por 4 son 4 p, 4 p + 1 , 4 p + 2 y 4 p + 3 , pero comoestamos interesados en saber los residuos de dividir por 4 a un cuadrado, n tiene la forma n , denuevo veamos los casos:

Si n = 4 p = n = 16 p , deja residuo 0.

Si n = 4 p + 1 = n = 16 p + 8 p + 1 , deja residuo 1.

Si n = 4 p + 2 = n = 16 p + 16 p + 4 = 4(4 p + 4 p + 1) , deja residuo 0.

Si n = 4 p + 3 = n = 16 p + 24 p + 9 = 4(4 p + 6 p + 2) + 1 , deja residuo 1. Luego los nicos

residuos son 0 y 1

Utiliza la misma tcnica para responder la pregunta: y por 8?.

Ejemplo 6. La sucesin (U n ) est denida para todo entero n por U n = 3 2 n 2n . Demostrar quepara todo n , U n es divisible por 7.Demostracin.Recordemos un poco el mdulo anterior, especicamente el teorema del binomio:

32 n 2n = 9 n 2n = (7 + 2) n 2n

Pero (7 + 2) n = nk =0

nk 7

k 2n k , de esta expresin es claro que cuando k = 0 , que es elprimer trmino de la suma, este valdr 2n el cual se anula en la expresin original y todos los demstendrn siempre un factor 7, ms explcitamente:

(7 + 2) n 2n = 2 n + nk =1

nk 7

k 2n k 2n = nk =1

nk 7

k 2n k , lo que completa laprueba.

APLICACIN

Qu da de la semana fue el 15 de abril de 1707?. (Fecha de nacimiento de Euler)Para contestar esta pregunta es necesario recordar que en nuestro calendario un ao normal

consta de 52 semanas y 1 da, osea 365 das. Un ao bisiesto consta de un da ms, agregado al mesde febrero, osea consta de 366 das. Un ao que no es secular (o sea que no corresponde a un siglo)es bisiesto si y slo si es divisible por 4. Los aos seculares tales como 1600, 1700, 1800, 1900,... sonbisiestos si y slo si, son divisibles por 400. Por consiguiente, los aos 1600 y 2000 son bisiestos,pero no lo son los aos 1700, 1800 y 1900.

La observacin fundamental para determinar en que da de la semana cay una fecha dada esque dos fechas dadas caen en el mismo da de la semana s, y slo s, el nmero de das del intervaloque forman esas dos fechas tienen resto 1 en la divisin por 7.

As por ejemplo, si el 1 de enero fue lunes y el ao no es bisiesto, del 1 de enero al 31 de diciembrehay 365 das; esto es 365 = 52

7+1 . Por lo tanto, ambas fechas caen el mismo da de la semana. Si

el ao fuese bisiesto sera 366 = 52 7 + 2 , y en consecuencia el 31 de diciembre caera el siguienteda de la semana al que corresponde al 1 de enero.Con esta breve explicacin es posible calcular el da de la semana que le correspondi al natalicio

de Euler. La informacin bsica se obtiene de un calendario 2010 que tenemos a mano.

11


12/72

Aos transcurridos de 1707 a 2010: 2010-1707=303 aos

Aos bisiestos intermedios: estos van de 1708 a 2008, osea 2008-1708=300, pero 1800 y 1900no fueron bisiestos, por tanto el nmero de aos bisiestos intermedios fue3004 + 1 2 = 74Del 15 de abril de 1707 al 15 de abril de 2010 han transcurrido 303 aos ms 1 da.Por tanto el nmero total de das fue: 303 365 + 74 + 1 = 110670 = 15810 7

Dado que el 15 de abril de 2010 fue jueves, se puede concluir que el 15 de abril de 1707 fue viernes,As el gran matemtico Leonhard Paul Euler naci un viernes. (Recordemos que en este conteo, elda conocido es el 15 de abril de 2010 que es jueves, si empezamos el conteo a partir de este dapero hacia atrs, vemos que va as: jueves, mircoles, martes, lunes, domingo, sbado y viernes quesera el mltiplo de 7, y si seguimos esta secuencia 15810 veces obtenemos el da buscado).

Sistemas de Numeracin1 Introduccin

Proponer un sistema de numeracin es dar un mtodo que permite escribir todos los nmerosenteros con un nmero nito de smbolos. Nuestro sistema usual de numeracin es el decimal, estepermite escribir todos los nmeros enteros utilizando diez cifras (dgitos) que son 0, 1, 2, 3, 4, 5, 6,7, 8, 9.

Comentario : casi todas las antiguas civilizaciones de China, Mesopotamia, Egipto, Amricadel Sur (mayas, aztecas ,...), tuvieron su sistema de numeracin. Estos sistemas no permiten unclculo fcil de las sumas, productos, cocientes. En el sistema de numeracin Romano, los resultadosde las operaciones debe ser aprendidos por medio de ejemplos de clculo, 11x53, es decir, XI.LIIIen nmeros romanos; esto porque, no existe ninguna regla fcil (no tiene ninguna base) para llegara 583, es decir, DLXXXIII.

Nuestro sistema decimal tiene la gran ventaja de hacer todas las operaciones simples y estomediante la creacin de la cifra cero, que fue transmitida por los rabes en Occidente alrededordel ao 700, as, cada dgito tiene un valor diferente segn la posicin en la representacin de unnmero.

2 Otros sistemas de numeracinEn nuestro sistema decimal, todo entero es escrito a n 10n + a n 1 10n 1 + . . . + a 1 10 + a 0 , donde

cada a i es un nmero estrictamente menor que 10 (por lo tanto de una cifra). As,3612 = 3 103 + 6 102 + 1 10 + 2 .Dejamos como ejercicio probar que: si elegimos un entero a positivo, todo entero m es escrito

de manera nica m = u 1 a n + u n 1 a n 1 + . . . + u 1 a + u 0 , donde cada u i es un entero positivo menorque a .

Decimos que esta representacin es la escritura de m en el sistema de base a , y que los nmerosu i son las cifras en dicho sistema. Se escribe de forma compacta: m = un u n 1 u n 2 . . . u 1 u 0 m = u n u n 1 u n 2 . . . u 1 u 0 .

12


13/72

(la barra indica que no es el producto de los nmeros).

Ejemplos:

1. Sistema de base dos o binaria : la base es dos, las cifras son 0,1. Todo nmero es escritocon estas dos cifras 0 y 1. Ejemplos: cero 0, uno 1, dos 10, tres 11, cuatro 100.

2. Sistema base ocho u octal : la base es ocho, las cifras son 0, 1, 2, 3, 4, 5, 6, 7. Ejemplos:cero 0, uno 1, dos 2, tres 3, cuatro 4, cinco 5, seis 6, siete 7, ocho 10, nueve 11.

3. Sistema base doce o duodecimal : la base es doce. las cifras son 1, 2, 3, 4, 5, 6, 7, 8, 9,, .Hay que aadir dos smbolos y a las cifras habituales, por diez, por once, porque elnmero doce se escribe 10 en este sistema, el nmero trece se escribe 11...

Comentario : el sistema binario es perfectamente adaptado en la tecnologa actual, calculadoras ocomputadoras donde se emplea elementos que pueden tomar uno de los dos estados fsicos apagadoy encendido, apagado lo representamos con 0 y encendido con 1.

El hecho que el tamao en la escritura de los nmeros en base dos va aumentando rpidamente,ha llevado a los informticos a hacer uso intenso del sistema hexadecimal (base 16). Por ejemplo,en el sistema de codicacin ASCII, la letra A es codicada en base 2 por 1000001 mientras que enhexadecimal su cdigo es 41.

3 Problemas de cambios de baseEscribir en el sistema decimal un nmero escrito en un sistema de base a.Ejemplo : el nmero N se escribe 10011001 en el sistema binario. Cul su escritura en el sistema

decimal?Aplicando los resultados del apartado anterior, a partir de la ltima cifra de la derecha son las

unidades. N = 1 27 + 0 26 + 0 25 + 1 24 + 1 23 + 0 22 + 0 2 + 1 , luego N , en decimales el nmero 1 + 22 + 2 4 + 2 7 , es decir 153.Ejercicios : En cada caso, dar la escritura decimal de N .

1. La escritura de N en base 2 es 111000110.2. La escritura de N en base 8 es 76152

3. La escritura de N en base 12 es 7645.

Escribir en un sistema de base a un nmero escrito en el sistema decimal.Ejemplo . El nmero N = 2183 est escrito en el sistema decimal. Cul es su escritura en el

sistema base ocho?.Aplicando los resultados del apartado anterior, escribamos N en su forma de base ocho: N =

8n u n + . . . + 8 u 1 + u 0 , cada uno de los nmeros u i son cifras de 0 a 7. Vemos que N = 8N + u 0 ,donde u 0 es el resto de la divisin eucldea de N por 8, es decir, 2183 = 8 272 + 7 , donde u 0 = 7 .Para lograr la forma que deseamos, hay que dividir a 272 por 8, lo que da: 272 = 8 34 + 0 , asque, N = 8

(8

34 + 0) + 7 = 8 2

34 + 8

0 + 7 y u 1 = 0 .

(Tenga en cuenta que se sustituye 272 por 8 34 + 0 , y no por 8 34, porque llevara a unresultado falso). La divisin de 34 por 8 es 34 = 8 4 + 2 , as que: N = 8 2 (8 4+2)+8 0+ 7 =83 4 + 8 2 2 + 8 0 + 7 . La escritura de N en base ocho en entonces 4207.Ejercicios:

13


14/72

1. Escribir en base doce, los nmeros once, trece, diecinueve, ciento veinte y cinco.

2. El nmero N = 6215 est escrito en el sistema decimal. Cul es su escritura en base ocho?

3. El nmero N = 13615 est escrito en el sistema decimal. Cul es su escritura en base siete?En base doce?

Escribir en el sistema base a nmero N escrito en base b .En primer lugar hay que escribir a N en el sistema decimal, y luego pasar la escritura en decimal

a base b. El nmero N = 5012 est escrito en base 7. Cul es su escritura en base dos?.

4 Bsqueda de la base de un sistemaEjemplo : el nmero N se escribe 23 en el sistema decimal y se escribe 27 en un sistema base a .

Podemos encontrar a?. Observemos en primer lugar que a es mayor que 7 porque 7 es un dgitodel sistema de base a . Justicar la igualdad 23 = 2 a + 7 . Deducir que a es el nmero ocho.

Ejercicios.

1. El nmero N se escribe 136 en decimal y se escribe 253 en base a . Se puede encontrar a ?

2. El nmero N se escribe 303 en decimal y se escribe 523 en base a . Se puede encontrar a ?

14


15/72

3.

Ejercicios1. Escriba todos los divisores en Z de los nmeros 20, 28 y 75.2. a y b son enteros, b = 0 . Qu condicin debe cumplir el nmero ab para que sea un entero?.

3. n es un entero natural mayor o igual a 2 y A = n 4 1.a ) Demostrar que n 1, n + 1 y n 2 + 1 son divisores de A .b) Deducir otros divisores de A .

4. Encuentre todos los divisores en N de 21. Encuentre todos los pares de nmeros naturales(a, b ) tales que a 2 b2 = 21 .

5. Encuentre todos los pares de nmeros naturales (x, y ) tales que x 2 2xy = 15 .

6. k es un natural, a = 3k + 5 y b = 2k + 1 . Pruebe que los posibles divisores positivos comunesde a y b son 1 y 7.

7. Encuentre todos los enteros n tales que n + 8 es un mltiplo de n .

8. Explique porque es imposible encontrar u y v en Z tales que 6u 9v = 2 .9. Encuentre todos los enteros n que divididos por 4 tengan cociente igual a su resto.

10. Encuentre un natural que dividido por 23 de como resto 1 y que dividido por 17 d el mismocociente con un resto de 13.

11. b es un natural no nulo. La divisin eucldea de 990 por b, da como cociente 39.

a ) Escriba la relacin que traduce esta divisin.b) Pruebe que 39b 990 < 40b. Deduzca b y r .

12. Demuestre las siguientes propiedades:

a ) La suma de dos nmeros impares consecutivos es mltiplo de 4.b) La suma de tres nmeros impares consecutivos es divisible por 3 pero no por 6.c ) El producto de dos nmeros pares consecutivos es divisible por 8.

13. Las edades de tres personas son nmeros consecutivos. Si se dividen dichos nmeros por 9,dos de ellos tienen cociente 6 y el restante 7 Que edades tienen?

14. Supongamos que al dividir por 12 catorce nmeros enteros consecutivos se obtienen trescocientes diferentes Cules son los restos de dividir por 12 el menor y mayor de dichosnmeros?

15. Dos nmeros enteros m y n (m < n ) dieren en 110. El resto de dividir m por 9 es mayor queel de dividir n por 9, y ninguno de los dos es mltiplo de 9. Cules son esos restos?

15


16/72

16. Sean a, b y c enteros tales que a2 + b2 + c2 = n con n no mltiplo de 3. Demuestre que almenos uno de los tres nmeros a , b y c es mltiplo de 3.

17. El cociente de un entero cualquiera x al dividirlo por 3 es 7. Cules son los restos posibles?Deduzca cuales son los valores posibles para x .

18. La suma de dos nmeros enteros a y b es 444. La divisin eucldea de a por b tiene comocociente 4 y como resto 24. Determine a y b.

19. La diferencia de dos nmeros enteros a y b es a b = 996 . La divisin eucldea de a por btiene como cociente 4 y como resto 60. Encontrar a y b.20. a es un entero cualquiera. Demostrar que a a 2 1 es un mltiplo de 2 y de 3.21. n es un entero. Demostrar que para cualquier n , 3n 2 + 5 n + 1 es impar y deducir que nunca

es divisible por n (n + 1) .

22. a y b son dos enteros cualquiera. Demostrar que si a2 + b2 es divisible por 7, entonces a y bson divisibles por 7.

23. Encuentre a , b y c tal que ab + bc + ac = abc, con 0 < a < b < c .

24. a es un entero, a 1, y A = a 2 + ( a 1)22 . Demostrar que el resto de dividir A por 4a 2 es

(2a 1)2 .

25. n es un entero. Demostrar que si n > 6, el nmero 6n tiene por lo menos 8 divisores.

26. p es un entero estrictamente positivo. Cuntos son los naturales que estn estrictamenteentre dos mltiplos de p? Deducir que entre p naturales consecutivos cualesquiera, hay por lomenos uno mltiplo de p.

27. Si n es un entero natural tal que n 1, y denimos An = ( n + 1) ( n + 2) (2n 1)(2n ).Pruebe por recurrencia que A n es divisible por 2n .28. Demostrar que si p es impar, la suma de p nmeros consecutivos es un mltiplo de p.

29. Para cualquier entero no nulo, denimos: M = 9n + 1 y N = 9n 1. Probar que 81n 2 1 esdivisible por 4 cuando n es impar y slo en este caso.30. Si n 2 y k es positivo, entonces (n 1)2 divide a n k 1 si y slo si n 1 divide a k .31. Para todo entero positivo n , el nmero A n = 5 n + 2 3n 1 + 1 es mltiplo de 8.32. Cul es el mayor entero positivo n tal que (n + 10) |(n 3 + 100) ?33. Si m y n son dos nmeros impares, entonces

a ) 8 divide a m 2 n 2 .b) 8 divide a m 4 + n 4 2.

34. n es un natural. Demuestre que para cualquier n , los nmeros n 3 n y n (n + 1)(2 n + 1) sondivisibles por 2 y por 3.

16


17/72

35. Encuentre todos los pares de enteros (x, y ) tales que x 2 y2 = 35 .36. Encuentre todos los pares de enteros tales que la suma es un mltiplo de su producto.

37. Encuentre todos los enteros tales que: xyz = 4 ( x + y + z), donde 0 < x

y

z .

38. Sean a 1 , a 2 , . . . , a n nmero enteros tales que a 1 a 2 a n = n y a 1 + a 2 + . . . + a n = 0 . Demostrarque 4|n .39. Si a n = 6 n + 8 n , determinar el resto al dividir a 1991 entre 49.

40. Sea a1 , a 2 , . . . , a n una permutacin arbitraria de los nmeros 1, 2, . . . , n . Probar que, si n esimpar, el producto (a 1 1)(a 2 2) (a n n ) es un nmero par.

41. Probar las siguientes propiedades

a ) Demostrar por recurrencia que para cualquier natural n , 23 n 1 es divisible por 7.b) Deducir que 23 n +1 2 es un mltiplo de 7 y que 23 n +2 4 es un mltiplo de 7.c ) Determine los restos de la divisin por 7 de las potencias de 2.

42. La sucesin (u n ) es denida para todo natural n por u n = 5n 3 + n .

a ) Verique que: u n +1 u n = 3[5n (n + 1) + 2] .b) Demostrar que para todo entero n , 5n (n + 1) + 2 es nmero par.c ) Demostrar por recurrencia que para todo entero n , u n es divisible por 6.

43. En una divisin eucldea el dividendo tiene p cifras y el divisor q cifras. De cuntas cifras esel cociente?

44. a y b son dos enteros. En la divisin eucldea de a por b, el cociente es no nulo. Pruebe que aes mayor que el doble del resto.

45. En la divisin eucldea entre dos enteros positivos, el dividendo es 1517 y el cociente 75. Qupuede decirse del divisor y el resto?

46. El dividendo en una divisin es menor a 300. El cociente es 72 y el resto es 12. Buscamos eldivisor y el dividendo. Explique por qu no hay una solucin.

47. Efectuamos la divisin eucldea de n por 4 y llamamos al cociente q y r al resto.

a ) Escriba la relacin que traduce esta divisin.b) Dado n , le asociamos su resto r y por tanto nos da una sucesin.

1) Mostrar que dicha sucesin es peridica.2) Represente grcamente esta sucesin cuando n toma los valores que estn en

[

12, 11].

48. Sean a y b naturales. Efectuamos la divisin eucldea de a por b, luego aumentamos el divi-dendo en 52 y el divisor en 4. El cociente y le divisor no cambian. Calcule el cociente.

17


18/72

49. La diferencia entre dos naturales es 538. Si dividimos uno por el otro, el cociente es 13 y elresto es 34. Cules son los nmeros?. La suma de dos naturales es 2096. Si dividimos unopor el otro, el cociente es 5 y el resto es 206. Cules son los nmeros?.

50. a y b son dos enteros. En la divisin eucldea de a por b, el resto r es mayor o igual a sucociente q . Demostrar que si dividimos a por b + 1 , obtenemos el mismo cociente.

51. a y b son dos enteros positivos. En la divisin eucldea de a por b, el cociente es q y el restor . Se agrega a a un nmero cualquiera h .

a ) Represente en un eje a, bq, b(q + 1) .b) Para que valores de h el cociente de a + h por b sigue siendo igual a q .c ) Aplicaciones numricas:

1) a = 61 , b = 17 .2) a = 240 , b = 39 .

52. a y b son dos enteros tales que 0 < b 2 < a . Sea q el cociente y r el resto en la divisin eucldeade a por b.

a ) Escriba la relacin que traduce las hiptesis.b) Demuestre que b c.c ) Demuestre que en la divisin de a por c, el cociente es b y el resto no cambia.d ) Encuentre un contraejemplo que muestre que si a < b 2 , puede suceder que el cociente de

a por c no sea b.

53. El nmero que se escribe 68425 en el sistema decimal. Escriba este nmero en el sistema base2, base 8 y en base 12.

54. El desarrollo decimal del producto de dos nmeros termina en 7 y uno de ellos tiene resto 4

al dividirlo por 5. Qu resto tiene el otro?55. Si elegimos un entero a positivo, todo entero m es escrito de manera nica m = un a n +

u n 1 a n 1 + . . . + u 1 a + u 0 , donde cada u i es un entero positivo menor que a .

56. Encontrar que da es la fecha indicada:

a ) 23 de febrero de 1855 (muri Gauss).b) 15 de abril de 1707 (naci Euler).c ) 24 de marzo de 1980 (muri Arnulfo Romero).

18


19/72

Parte IIMCM, MCD

1. Mximo Comn Divisor1.1. El Mximo Comn Divisor (MCD)

El objetivo de esta seccin es investigar los divisores positivos comunes a dos enteros positivosa y b.

Por convencin, en esta seccin y las siguientes, cuando se hable de divisores de un nmeronatural, se referir siempre a los divisores positivos.

Divisores comunes a dos enteros positivos.

Para todo nmero natural a , denotamos D(a ) al conjunto de los divisores de a .Ejemplo.

D(6) =

{1, 2, 3, 6

};

D(15) =

{1, 3, 5, 15

};

D(19) =

{1, 19

}.

Ejemplo. D(a ) solamente contiene nmeros naturales menores o iguales que a . Siempre que a > 1,D(a ) contiene siempre a 1 y a a. El elemento ms grande de D(a ) es a y el ms pequeo es 1. Elconjunto D(1) solamente contiene un elemento: el nmero 1.

Para todo par de nmeros naturales a y b, denotamosD(a, b ) al conjunto de divisores comunesde a y b.As, D(a, b ) = D(a ) D(b) . Es claro que D(a, b ) = D(b, a ).Ejemplo. D(6, 15) = D(6) D(15) = {1, 3}; D(15, 19) = D(15) D(19) = {1}.Ejemplo. D(a, b ) es un conjunto no vaco, siempre contiene al 1, y los nmeros que contiene sonmenores o iguales a a y b. Por lo tanto D(a, b ) posee un elemento mayor que se llama el MximoComn Divisor de a y b.Ejemplo. El mximo comn divisor de a y b se abrevia MCD.Ejemplo. El MCD de 6 y 15 es 3; el de 15 y 19 es 1.Observacin. Para conocer el conjunto de divisores negativos de a , es suciente tomar los negativosde los elementos de D(a ).As, el conjunto de los divisores en Z de 6 es {6, 3, 2, 1, 1, 2, 3, 6}.1.2. Resultados inmediatos.

1. Cualquiera que sea el nmero natural c, D(c, 0) = D(c).En efecto, todo entero divide a 0, entonces los divisores comunes a 0 y c son los divisores dec.

2. Si b divide a a , entonces b es el MCD de a y b.En efecto, en este caso, todo divisor de b es un divisor de a . Entonces D(a, b ) = D(b) y comob es el elemento mayor de D(b) es tambin el elemento mayor de D(a, b ).Ejemplo. D(6, 12) = {1, 2, 3, 6}= D(6) ; 6 es el MCD de 6 y 12.

19


20/72

3. Si a = b es claro que D(a, b ) = D(a ).Para mayor comprensin.

Cmo programar en tu calculadora un algoritmo para obtener los divisores de un nmeronatural?Dado un natural n, el algoritmo ms simple consiste en examinar con la ayuda de un bucle FOR todos los enteros k de 1 a n . Si k divide a n entonces lo mostramos. El algoritmo puedeser escrito as:

Algoritmo Comentarios Familia Casio Familia TI1. Leer n .

2. Correr el bucle FOR:Para todo k de 1 an

Si k divide a n en-tonces mostrar k .

3. Fin del bucle FOR.

1. La mquina demanda elvalor de n .

2. k va a tomar sucesiva-mente todos los valoresde 1 a n . k divide a n puedeprogramarse vericandoque la parte entera de n

kdebe es igual a n

k.

N:?NFor 1 K to NIf Int(N/K)=N/KThen KEnd If Next

Input N, NFor(K,1,N)If Int(N/K)=N/KDisp KEnd

Ejercicios resueltos.

Ejercicio 1. Demostrar que D(a, b ) = D(b, a b).1. a y b son dos enteros naturales, a b. Demuestre que el conjunto de divisores comunes de ay b es el mismo conjunto de divisores comunes de b y a b.2. Aplique varias veces este resultado para demostrar que los divisores comunes de 168 y 264

son los divisores de 24. Deduzca el MCD de 168 y 264.

20


21/72

Solucin Comentada1. Debe demostrarse que los dos conjun-tos D(a, b ) y D(a b, b) son iguales.Para ello, se demostrar que todo n-mero d de D(a, b ) est en D(a b, b), yluego, que todo nmero d de D(a b, b)est en D(a, b ).Supongamos que d est en D(a, b ) en-tonces d divide a a y b. De aqu resultaque d divide a a b entonces d est enD(a b, b).Recprocamente, si d est enD(a b, b),divide a a b y divide a b, y tambin ddivide a la suma de estos nmeros, porlo que d divide a a y b y d

D(a, b ).Resulta entonces que D(a, b )= D(a b, b).

2. Del numeral 1 se deduce que:

D(168, 264) = D(96, 168)Repitiendo este proceso se obtiene:

D(96, 168) = D(72, 96) = D(24, 72) = D(24, 48)

= D(24, 24) = D(24)Los divisores comunes de 168 y 264 son los divisoresde 24. El mayor es entonces 24.Un poco de historia: Es por este mtodo de sustrac-ciones y no por el de divisiones sucesivas (el cual seexplica e la siguiente seccin) que Euclides, en su libroLos Elementos, calcula el MCD de dos nmeros. Estemtodo conocido por el nombre de Antiferesis, quesignica accin de restar alternadamente, parece queya era conocido por los Pitagricos.De hecho, Euclides utiliz los nmeros nicamente co-mo segmentos de recta (para los griegos de esa poca,el nmero es una medida), lo cual le permiti tratar losnmeros de forma general an sin conocer los valoresprecisos de estos.

2. Mximo Comn Divisor (continuacin)

2.1. Investigacin del MCD. Algoritmo de Euclides.En la subseccin 1.2 vimos resultados que permiten deducir el MCD de a y b cuando a = b,

cuando a = 0 o b = 0 y cuando b divide a a . En la bsqueda ms general del MCD se puede suponer0 < b < a .1. Resultado preliminar

Efectuando la divisin euclidiana de a por b, a = bq + r con 0 r < b .Entonces los divisores comunes de a y b son los divisores comunes de b y r , por lo que se puedededucir que D (a, b ) = D (b, r ). En particular si r = 0 , D (a, b ) = D (b, 0) = D (b).Demostracin. Primero demostramos que todo divisor c de a y b divide tambin a b y r .Solo falta probar que l divide a r . Tenemos que r = a bq , luego c divide a a y b, c divide a r(Captulo 1, subseccin 1.3, propiedad 5) y tambin a b.Recprocamente, demostramos que todo divisor d de b y r divide tambin a a y b. Slo falta

probar que d divide a a. Como a = bq + r , entonces como d divide a by r entonce d divide a a ytambin a b.

21


22/72

En conclusin los divisores comunes a a y b son los divisores comunes a b y r , de esta formaD (a, b ) = D (b, r ).2. Algoritmo de Euclides (cuando b no divide a a)

Demostracin. As la bsqueda de D (a, b ) se reduce a la bsqueda de D (b, r ), que es estricta-mente un par de nmeros "menor" en el sentido que b < a y r < b . Siendo r diferente de cero(porque b no divide a a) podemos dividir b por r , obtener un residuo r 1 y reemplazar (b, r ) por(r, r 1 ) y D (a, b ) = D (b, r ) = D (r 1 , r ). Y as sucesivamente hasta que se obtenga un residuo igual acero.

Ciertamente que al nal encontramos un residuo que sea nulo puesto que los residuos sucesivosr , r 1 , r 2 , . . . son enteros positivos que van decreciendo estrictamente. Uno obtiene de esta maneralas igualdades: D (a, b )= D (b, r )= D (r, r 1 )= D (r 1 , r 2 )= . . .= D (r n , 0).

Y tenemos que D (r n , 0) = D (r n ).Como D (a, b ) = D (r n ) y ya que r n es el divisor ms grande de D (r n ), r n es el mayor divisor de

D (a, b )y por lo tanto el MCD de a y b.

Consecuencia practica: Cuando b no divida a a, el MCD de a y b es el ltimo residuo no nulo

que se obtiene en el algoritmo.

2.2. Un resultado importanteTeorema 1. Todos los divisores comunes a dos enteros positivos a y b tambin son divisores

del MCD g, es decir D (a, b ) = D (g).

Demostracin. En efecto, en vista que D (a, b ) = D (r n ) y r n es el MCD.

Observacin. El teorema nos dice en particular que todo divisor de a y b es un divisor de suMCD.

22


23/72

Cmo utilizar el algoritmo?Calcular el MCD de dos nmeros a = 138807 , b = 52089 y utilizando el algoritmo de Euclides.Al dividir a por b:

138807 = 2 52089b + 34629rAl dividir b por r :

52089 = 1 34629r + 17460r 1Al dividir r por r 1 :

34629 = 1 17460r 1 + 17169r 2Al dividir r 1 por r 2 :

17460 = 1 17169r 2 + 291r 3Al dividir r 2 por r 3 :

17169 = 59

291

r 3+ 0

r 4

El ltimo residuo distinto de cero es r 3 = 291 , por lo que r 3 es el MCD de a y b.Observacin: El hecho de saber el MCD de 138 807 y 52 089 permite conocer todos sus divisorescomunes: los divisores comunes a 291 los cuales son 1, 3, 97 y 291.Cuando calculamos el MCD "a mano", podemos adoptar el sistema en el cual escribimos las divi-siones sucesivas una despus de otra, los cocientes los ponemos en la lnea superior (porque no sonutilizados) y los residuos son puestos en la tercera linea.

2 1 1 1 59138 807 52 089 34 629 17 460 17 169 29134 629 17 460 17 169 291 0

Ejercicios resueltosEjercicio 2. Utilizando la denicin del MCDSean a y b dos enteros positivos, a = 630 .El MCD de a y b es igual a 105 y 600 < b < 1100.Encontrar b.

23


24/72

SolucinPuesto que b es un mltiplo de 105, escribimos b = 105k con k entero positivo.La condicin 600 < b < 1100 se traduce por:

600 < 105k < 1100De donde los valores posibles de k son 6, 7, 8, 9, 10, 11, resta encontrar los valores que satisfaganlas condiciones.

k = 6 da b = 6 105 = 630 pero entonces b = a y 105 no puede ser el MCD.k = 7 da b = 7 105 = 735 . Si calculamos el MCD de a y b encontramos 105.k = 8 da b = 8 105. a = 6 105 y 105 no es el mximo comn divisor puesto que 2 105divide tambin a a y b.k = 9 da b = 9 105 y 3 105divide a a y b por lo que 105 no es el MCD.k = 10 da b = 10 105 y 2 105 divide a a y bpor lo que 105 no es el MCD.

El nico valor que satisface es por lo tanto es k = 7 donde b = 735 .

3. Teorema de BezoutLos nmeros tales su MCD es igual a 1 juegan un papel importante. En particular, porque

permiten una caracterizacin prctica del MCD.

3.1. DenicinDenicin: Dos nmeros naturales se llaman primos entre s, si su MCD es igual a 1.

Se dice incluso que no tienen otro divisor comn que no sea 1.Ejemplo : 8 y 15 son primos entre s.Observacin : La denicin se extiende a nmeros enteros. Dos enteros son primos entre si, cuandolos nicos divisores comunes son 1 y -1.

3.2. Caracterizacin: El Teorema de BezoutTeorema 2. Sean a y b dos nmeros naturales no nulos. Decir que: a y b son primos entre s

es equivale a decir que existen dos nmeros enteros u y v, tales que, au + bv = 1 .Demostracin

1. Supongamos que existen dos enteros u y v, tales que au + bv = 1 , y probamos que a y b sonprimos entre si.El MCD g de a y b, divide a y b, por ende divide a todo nmero de la forma au + bv con u yv enteros. Pero por hiptesis existen enteros u y v tales que au + bv = 1 , por consiguiente, gdivide 1, de donde g = 1 , y a y b son primos entre si.

2. Supongamos que a y b son primos entre si y probemos que 1 se escribe como au + bv. Consi-deremos el conjunto E de todos los nmeros au + bv con u y v en Z .

24


25/72

E contiene a a porque, a = a (1)+ b(0) , por ende E contiene enteros estrictamente positivos yentre ellos hay uno mas pequeo que todos los dems. Denotemos por m a dicho entero, asm = au 1 + bv1 con u1 Z y v1 Z . Demostremos que m divide a a y a b; de donde resultaque m = 1 y que au 1 + bv1 = 1 .La divisin de a por m , con m = au 1 + bv1 , nos da: a = ( au 1 + bv1 )q + r , de donder = a(1qu 1 ) + b(qv1 ) = au + bv con u y v en Z .Puesto que r est en E y dado que, 0 r < m y siendo m el entero mas pequeo de E positivo, necesariamente r = 0 y en consecuencia m divide a. De manera anloga se pruebaque m divide a b.

Ejemplos :8 7 + 11 (5) = 1 ; 8 y 11 son primos entre si.Dos naturales consecutivos y mayores a 1 son primos entre si , ya que n 1 + ( n 1) (1) = 1 .

Ejercicio 3: Probar que dos nmeros son primos entre si.

Si n es un entero natural. Demuestre que a = 2n + 1 y b = 3n + 2 son primos entre si.Solucin comentada.Tratemos de encontrar dos enteros u y v, talesque para todos n , (2n +1) u +(3 n +2) v = 1 . Laidea para eliminar n elegiendo u = 3 y v = 2nos da resultado 1.

Ponemos entonces, u = 3 y v = 2 para queel resultado sea +1 . Esto da: 3a + 2b = 1 .Ejercicios: 12 y 13, 21.Ejercicio 4: Resultados que es preferible conocer o saber demostrar.

1. Demostrar que si un natural a es primo con dos enteros b y c, tambin es primo con suproducto.

2. Deducir que si a y b son primos entre si, entonces an y b p son primos entre si, para todonatural n 1, para todo natural p 1.

Solucin comentada.1. a es primo con cada uno de los nmeros

enteros b y c. Segn el Teorema de Be-zout, existen enteros u,v,u , v, tal que,au + bv = 1 y au + cv = 1 . Multi-plicando, miembro a miembro, las dosigualdades se obtiene: a(auu + cuv +bvu) + ( bc)(vv) = 1 , que es de la formaax +( bc)y = 1 con x, y y enteros. En con-secuencia, segn el teorema de Bezout, aes primo con bc.

2. Como consecuencia del numeral anterior,con c = b, se obtiene que a primo conb b = b2 .

As a es primo con b y b2 , y por ende con b3 . Ypor induccin se establece que a es primo conb p . Como b p es primo con a, tambin es pri-mo con a2 . Luego, b p es primo con a y primocon a2 , por lo que es primo con a3 , y por re-currencia se concluiye que b p es primo con ancualquiera que sea n . Ejercicio 25.

Ejemplo 5. Otros resultados interesantes.Sean a y b dos naturales primos entre si.

25


26/72

1. Pruebar que a + b es primo con a y con b.

2. Deducir que a + b es primo con ab , y que a 2 + b2 es primo con ab .

Solucin comentada.

Ya que a y b son primos entre si, se puedeescribir au + bv = 1 con u y v en Z . Sumandoun cero conveniente que nos permita introducira + b, obtenemos: au + bubu + bv = 1 , esdecir, (a + b)u + b(v u ) = 1 , lo que pruebaque a + b y b son primos entre si. Demuestredel mismo modo que a + b es primo con a .

De lo demostrado anteriormente, a + b es primocon ab. Se deduce (ver el ejercicio resuelto 4)que (a + b)2 es primo con ab (para introducira 2 + b2 ). De donde se deduce que existen u yv tales que, u(a + b)2 + vab = 1 con u y v enZ . As que, u (a 2 + b2 ) + 2 abu + vab = 1 luego:u (a 2 + b2 ) + (2 u + v)ab = 1 , lo que demuestraque a2 + b2 y ab son primos entre si.

26


27/72

4. Caractersticas y Propiedades del MCD4.1. Caractersticas y Propiedades del MCD

Teorema 3. Sean a, b y g enteros estrictamente positivos. Las tres proposiciones siguientes son equivalentes.

(1) g es el MCD de a y de b(2) g es un divisor de a y b y los enteros positivos a

g y b

g son primos entre s.

(3) g es un divisor de a y b y existen enteros u y v tales que au + bv = g .Demostracin. 1. Probemos que (1) implica (2). Supongamos que g es el MCD de a y de b.

Luego g divide a a y b de donde los nmeros ag

= a y bg

= b son naturales. Probemos que sonprimos entre s. Si d es un divisor comn de a y b , entonces a = dp, b = dq , donde p y q sonnaturales.

Por lo tanto a = dgp y b = dgq , de donde dg sera un divisor comn de a y b. Ahora bin, g esel mayor de estos divisores as que d = 1 , y entonces a y b son primos entre s.

2. Probemos que (2) implica (3). Supongamos que d es un divisor de a y b y que los enterosnaturales a

d y b

d son primos entre s. Entonces por el teorema de Bezout podemos escribir a

gu +

bg

v =

1 con u y v en Z , por tato au + bv = g.3. Probemos que (3) implica (1). Supongamos que g es un divisor de a y b y que existen dos

enteros u y v tales que au + bv = g.Sea g el MCD de a y de b. Ya que g divide a a y a b, tambin divide a g (seccin 1.4 de este

captulo).Sin embargo g divide tambin a au + bv, es decir divide g. Por lo tanto g = g .

Nota: Hemos demostradoque las tres proposiciones son equivalentes entre s yaque las implicaciones probadas forman un argumento cclico. As, por ejemplo (1)

es equivalente a (2), porque (1) implica (2) y (2) implica (3) y (3) implica (1). Porlo tanto (1) equivale a (2).

4.2. Resultado: Propiedad multiplicativa del MCDSi g es el MCD de dos naturales a y b, entonces para cualquier entero c, c > 0, gc es el MCD deac y de bc .

Demostracin. Comog divide a a y b, entonces gc divide a ac y bc. Para demostrar que gc es elMCD de ac y bc, es suciente demostrar que, basado en el teorema previo, que gc se puede escribirde la forma gc = ( ac )u + ( bc)v. Ahora g = au + bv, con u y v en Z de donde gc = ( ac )u + ( bc)v.

De la misma forma se demuestra que si c divide a a y b, por lo que divide tambin a g (teorema

1), entonces gc es el MCD de

ac y

bc .

Cmo utiliza el teorema 3?

27


28/72

A menudo es til traducir la hiptesis "g es el MCD de a y b" por "escribamos a = ga yb = gb con a y b primos entre s" ( ejercicio resuelto 6 ).

Si se tienen las igualdades a = ca ,b = cb y se puede demostrar que a y b son primos entres, entonces se podemos armar que c es el MCD de a y b ( ejercicio resuelto 7 ).

A veces puede ser til traducir el prrafo: "g divide a a y b" por "existen u y v enteros talesque au + bv = g" ( ejercicio resuelto 8 ).

Ejercicio 6. Utilizando las caractersticas del MCDEncontrar dos naturales tales que a + b = 112 y MCD(a, b ) = 14 .SolucinEl MCD de a y b es 14 entonces a = 14a y b = 14b con a y b enteros primos entre s. Reemplazandoen la igualdad a + b = 112 obtenemos 14(a + b ) = 112 que equivale a a + b = 8 .Como a y b sonprimos entre s, la soluciones son a = 1 , b = 7 o a = 3 , b = 5 o a = 5 , b = 3 o a = 7 , b = 1 .Multiplicando por 14 encontramos que los pares (14; 98), (42; 70), (70; 42), (98; 14). Resta probarque en efecto son las soluciones de la ecuacin. Compruebe que esta de acuerdo con la solucin( ejercicio resueltos 17, 18 y 20 ).

Ejercicio 7. Utilizando las caractersticas del MCDSean p y n dos enteros, p > 1 y n > 1; a = pn y b = p(n 1).Demostrar que el MCD de a y b es igual a su diferencia.Solucin.Notamos que p = a b.Por otro lado, p es un divisor comn de a y de b y los cocientes de a y b por p son los enteros n y(n 1), primos entre s.De acuerdo a el teorema 3, p es el MCD de a y b. ( ejercicio resuelto 21 )

Ejercicio 8. Un resultado generalSea g el MCD de a y b y sea c un entero primo con b.Demostrar que g es el MCD de ac y de b.Solucin.Como g es un divisor de b, divide evidentemente a ac y b.Traduzcamos las hiptesis "g es el MCD de a y b " luego "existen u y v enteros tales que g = au + bv"."b y c primos entere s" donde "existen u y v enteros tales que 1 = bu + cv ". Multiplicandomiembro a miembro ambas igualdades y ordenando para que aparezcan ac y b obtenemos:

(ac )(uv ) + b(auu + bvu + cvv ) = g

donde g divide a ac y b por lo que, de acuerdo al teorema de Bezout, g es el MCD de ac y b.

5. Aplicaciones5.1. Teorema de Gauss

Teorema. Sean a,b y c enteros estrictamente positivos tales que a divide al producto bc y a esprimo relativo con b . Entonces a divide a c.

28


29/72

Demostracin. Como a y b son primos entre s, existen dos enteros u y v tales que au + bv = 1(teorema de Bezout). Por lo que acu + bcv = c. Como a divide claramente a acu y por hiptesisdivide a bc, entonces divide a bcv. Por lo tanto a divide a la suma acu + bcv, es decir, divide a c.

Nota. El teorema de Gauss se puede enunciar diciendo que si un natural divide a un productode dos factores y es primo relativo con uno de ellos, entonces divide al otro.

Corolario. Si un natural n es divisible por dos naturales a y b primos entre s , entonces es divisible por el producto de ellos.

Demostracin . Por hiptesis, podemos escribir n = ap y n = bq donde p y q son enteros naturales.Como ap = bq y ya que b divide a ap y es primo relativo a a entonces divide a p. Luego p = bp y p es natural, de donde n = abp lo cual prueba el corolario.

Este resultado se extiende fcilmente para el caso de varios factores: si n es divisible por masde un par de nmeros primos entre s, entonces n es divisible por el producto.

Ejemplos:

Si un nmero es divisible por 3 y 8, entonces es divisible por 24. Por lo que para probar que

un nmero es divisible por 24, solo es necesario que sea divisible por 3 y 8.Si un nmero es divisible por 3, 5 y 8 entonces es divisible por 3 5 8 = 120 , ya que 3, 5 y8 son primos entre s. Por lo que para probar que un nmero es divisible por 120 es sucienteprobar que es divisible por 3, 5 y 8.

5.2. Fracciones irreduciblesLlamamos fracciones a los nmeros de la forma a

b tales que a y b son enteros con b = 0 . (En lo

que sigue consideramos que las fracciones son positivas.)Denicin. Cuando a y b son primos entre s, entonces la fraccin a

b es irreducible.

Teorema. Cualquier fraccin es igual a una fraccin irreducible.

Demostracin. Consideremos una fraccin cd . Denotemos por g el MCD de c y d. Luego c = gc y

d = gd con c y d primos entre s. As mediante la simplicacin por g , cd

= cd

con cd

irreduciblepuesto que c y d son primos entre s.

Cmo explotar el hecho que una fraccin cd

sea igual a una fraccin irreducible ab

?Podemos armar que existe un entero positivo k tal que c = ka y d = kb tal que k es el MCD de cy d.En efecto, escribamos c

d =

ab

, bc = ad y cmo ab

es irreducible, a y b son primos entre s.Tenemos que a divide a bc y a es primo con b, donde a divide a c (teorema de Gauss). Por lo quec = ka . Sustituyendo en la igualdad bc = ad , obtenemos bka = ad donde d = kb.Como k es un divisor comn de c y d y los cocientes a y b son primos entre s.Por lo tanto, k es el MCD de c y de d (teorema 3).

Ejercicios resueltos

29


30/72


31/72

2. Todos los mltiplos comunes de a y b son un mltiplos de m .Demostracin. Sea g el MCD de a y b donde a = ga y b = gb con a y b primos entre s. Sea

M un mltiplo comn de a y b. Por lo que resulta que M = ap y M = bq donde p y q son enteros.Como M = ga p = gb q entonces, a p = b q [1]. La igualdad [1] prueba que a divide a b q . Como ay b son primos entre s, de acuerdo con el teorema de Gauss, a divide a q . Por lo que resulta queq = ka y teniendo en cuenta [1] y p = kb . Luego todo mltiplo comn a a y a b se puede escribiren la forma M = kga b . Recprocamente, demostremos que todo nmero que se puede escribir enla forma M = kga b es un mltiplo comn de a y b. M = k(ga )b = kb a . De la misma formaM = k(gb )a = ka b.

Por lo tanto los mltiplos comunes a a y b son mltiplos de ga b . El mnimo de todos estos esexactamente el MCM m = ga b . As que mg = ga gb = ab y cualquier mltiplo de a y b es mltiplode m .

6.3. CaracterizacionesTeorema.

Sean a y b enteros positivos. Decir que "m es el MCM de a y b" es equivalente

a decir que "m es un mltiplo de a y b y que los enteros naturales ma

y mb

son primos entre s ".Demostracin.

1. Sea m el MCM de a y b. Vimos que m = ga b = ab = a b. Los cocientes respectivos de mpor a y b no son otros que los nmeros b y a que son primos entre s.

2. Recprocamente sea M un mltiplo comn de a y b tal que los naturales M a

y M b

son primosentre s. Hemos visto que M = kga b luego los cocientes respectivos por a y b son kb y ka .

Como k es un divisor comn de estos dos nmeros y como por hiptesis que son primos entres, k = 1 . As M = ga b que es el MCM de a y b.

Cmo utilizar el hecho que m sea el MCM de a y de b?Sea m y g el MCM y el MCD de a y b respectivamente.La formula mg = ab es fcil de memorizar pero en la prctica es til escribir m = ga b donde los

enteros a y b son los cocientes respectivos de a y b por su MCD. El hecho que a y b son primosentre s puede ser til en algunas ocasiones (ejercicio resuelto 11 ).Cmo conocer el MCM de ac y bc a partir del MCM de a y b ?La siguiente propiedad es llamada "propiedad multiplicativa de del MCM ". Si m es el MCMde dos enteros positivos a y b, entonces para cualquier numero natural c diferente de cero, mc esel MCM de ac y bc .En efecto, sea g es el MCD de a y b entonces sabemos que

ac bcgc

= ab

g c = mc

Ahora bien m = abg

es el MCM de a y b.

El MCD de ac y bc es gc.El MCM de ac y bc es mc .

Ejercicios resueltos

31


32/72

Ejercicio 11. Encontrar dos nmeros sabiendo su relacin entre su MCD y MCM.Encontrar dos enteros a y b tales que la diferencia entre su MCM y MCD es igual a 187.Solucin.El enunciado del problema no pide hallar todos los enteros demanda nicamente dos de ellos.

Podemos restringirnos a enteros positivos.Llamemos a y b los dos nmeros naturales buscados.Sea m el MCM y g el MCD de a y de b.As:

a = ga , b = gb

con a y b primos entre s:m =

abg

= ga b .

Con g(a b 1) = 187 .As g es un divisor de 187 al igual que a b 1.Los divisores de 187 son 1, 11, 17 y 187; de donde se obtienen los posibles resultados:

g 1 11 17 187a b 188 18 12 2

Escogiendo g = 1 a b = 188 y a y b primos entre s solucionara la pregunta.Si escogemos a = 4 y b = 47 , 4 y 47 son primos entre s. De esta forma a = 4 y b = 47 , quecumplen con los requerimientos del problema.

Ideas y Reexiones

Ideas para recordarDivisin y divisin euclidiana

En la divisin euclidiana de a por b , el resto es positivo o nulo y estrictamente inferiora |b|.Cuando se divide todos los entero por un entero b jo, slo existen un nmero| b | de restosposibles :0 , 1, 2, . . . |b | 1. Ejemplo:Si b = 4 , todo entero se puede escribir de una de las formas: 4q o 4q + 1 o 4q + 2 o 4q + 3 .

La divisibilidad es transitiva: si a divide a b y b divide a c entonces a divide a c.

Si c divide a a, entonces c divide a todos los nmeros au , y si c divide a a y b , entonces cdivide a todos los nmeros au + bv.

MCD y MCMLos divisores comunes de a y b son los divisores de su MCD.

32


33/72

Decir que dos nmeros son primos entre s es decir que su MCD es igual a 1, o que 1 es sunico divisor comn.

El MCD g de a y b es tambin el divisor comn de a y b tal que ag

y bg

son primos entre s.

El MCD g de a y b tambin es un divisor comn a a y b escrito en la forma au + bv con u yv en Z .

Saber si la fraccin ab

es irreducible es tambin saber si a y b son primos entre s.

El MCM de a y b es fcil de encontrar a partir de su MCD puesto que:

MCMMCD = ab.El MCM de a y b, u, es tambin el mltiplo comn de a y b tal que u

a y u

b son primos entre

s.

SugerenciasPiense las relaciones de divisibilidad en trminos de igualdades.Ejemplo: Conocido que b divide a a , podemos escribir a = bq con q entero (e incluso q > 0 sia > 0 y b > 0).

Recprocamente, trate de interpretar las igualdades en trminos de divisores (o de mltiplos).Ejemplos:

1. Dos enteros x y y tales que 3x + 27 = y, concluimos que 3 divide divide a y.2. Dos enteros a, b, c son tales que 4a + 5 b = c. Por lo que deducimos que si d divide a a y

b entonces d divide a c.

Esencial: Recuerde que si d divide a a y b, entonces d divide a cualquier nmero de la formaau + bv, y divide a cualquier suma o diferencia de nmeros de esta forma.Ejemplo: Si d divide a ab y a + b entonces d divide a a2 . En efecto, d divide tambin aa(a + b) = a 2 + ab y ab por lo que divide a a 2 + ab ab. De igual manera divide a b2 .Una manera de demostrar que a divide a b es escribir la divisin euclidiana de b por a y acontinuacin demostrar que el residuo es nulo.

Para demostrar que a y b son primos entre s sin calcular su MCD, se puede suponer que ddivide a a y b y probar que d = 1 a travs de una hiptesis propuesta.

Para demostrar que n divide a un entero a , se puede escribir n = n 1 n 2 con n 1 y n 2 primosentre s, y enseguida probar que n 1 y n 2 dividen a a .

Errores a evitar

Una igualdad a = bq no signica que b divide a a sin estar seguro que q es un entero.La ecuacin a = bq + r no siempre reeja una divisin euclidiana. En efecto, es indispensableaadir la condicin 0 r < b .

33


34/72

Algoritmo para calcular los coecientes de las relaciones deBezout

Sean a y b dos enteros naturales, a > b > 0, y g su MCD. Entonces existen u y v enteros talesque au + bv = g. El propsito de este taller es hallar un algoritmo para calcular u y v.

1. Determinar u y v a travs de un ejemplo numricoMtodo.Podemos utilizar el algoritmo de Euclides en calcular restos sucesivos en funcin de a y b.

Sabemos que el ltimo resto no nulo es el MCD. En el desarrollo de estos clculos llegamos a unaetapa en la escritura de la forma au + bv que es igual al MCD.

Tomemos a = 47 y b = 3547 = 35 1 + 12 o35 = 12 2 + 1112 = 11 1 + 111 = 11

1 + 0

a = b + 12 as queb = ( a b) 2 + 11a b = (2a +3 b)1+1

12 = a b11 = 2a + 3 b1 = 3a 4bHemos obtenido el MCD como una combinacin linear de a y b.

2. Generalizaciones1. Anlisis de la situacinEn la presentacin del algoritmo de Euclides (En Captulo 1.3) vimos el clculo de restos sucesi-

vos r i hasta que el resto se convierte en nulo. Para homogenizar la notacin, es conveniente atribuirr 0 = a y r 1 = b.

A continuacin, la relacin r i = r i +1 q i +1 + r i +1 [1] permite obtener el resto r i +2 a partir desus dos precedentes r i +1 y r i .

En consecuencia (r i ) es una secuencia denida por la relacin de recurrencia [1] donde los dosprimeros trminos r 0 = a y r 1 = b.

La situacin se puede abreviar de la siguiente forma:r 0 = a ; r 1 = b

divisin 1 r 0 = r 1 q 1 + r 2 (o a = bq 1 + r 2 )divisin 2 r 1 = r 2 q 2 + r 3

. . .divisin i + 1 r i = r i +1 q i +1 + r i +2 [1]

. . .divisin n 1 r n 2 = r n 1 q n 1 + r ndivisin n r n 1 = r n q n + r n +1 con r n +1 = 0

Solucin de la ecuacin au + bv = c

1. Presentacin del problemaSean a,b, y c nmeros enteros, la ecuacin ax + by = c con x y y nmeros desconocidos en Z se

llama ecuacin diofntica .

34


35/72

Las ecuaciones diofnticas son ecuaciones algbricas con varios trminos desconocido cuyos tr-minos desconocidos son enteros o racionales donde se buscan las soluciones enteras .

A menudo son ecuaciones delicadas para resolver. Es fcil encontrar las soluciones reales de3x + 4 y = 0 que las soluciones enteras.

2. Estudio de un caso particularEn el presente apartado, nos centraremos en la ecuacin au + bv = g cuando g es el MCD de a

y b.

1. Buscar la solucin particular (u 0 , v0 ) de la ecuacin au + bv = g.Notamos (u, v ) una solucin alternativa a la ecuacin y denotamos por a = a

g y b = b

g.

a ) Justiquemos la igualdad a (u u 0 )+ b (u u 0 ) = 0 , a continuacin utilizamos el teoremade Gauss para demostrar que existe un entero relativo k tal que u = u 0 kb y v = v0 + ka .b) Recprocamente probamos que si u = u0 kb y v = v0 + ka con k entero, entoncesau

+bv

= g

.2. Aplicacin

a ) El MCD de 114 y 30 es 6.Encontrar todas las parejas (u, v ) enteras tales que 114u + 30 v = 6 .

b) Interprete grcamente los resultados.

3. Caso generalSupongamos que c es un entero cualquiera y a y b enteros donde a > b > 0.

1. a) Pruebe que si c no es un mltiplo del MCD de a y b entonces la ecuacin ax + by = c notiene soluciones.b) Supongamos que c es un mltiplo del MCD de a y b (c = c g). Resolver la ecuacinax + by = c.

2. Aplicacin.

a ) En un plano cartesiano, dibujar la lnea recta d de la ecuacin 47x + 47 y = 1 .Buscar los puntos en d donde las coordenadas son enteras.

b) La misma pregunta para la lnea recta determinada por la ecuacin 33810x+4116 y = 588 .

EjerciciosPara resolver los ejercicios de esta parte, basta con aplicar directamente los teoremas presentados

en esta seccin. El objetivo es doble: comprender mejor el curso y reconocer, en situaciones simples,en las condiciones de aplicacin de un teorema.

35


36/72

Mximo Comn Divisor.1. En casa caso, encuentre el conjunto de divisores D (a ) y D (b) de los naturales a y b. En cada

caso, determine el Mximo Comn Divisor.

a ) a = 24 ; b = 18 .b) a = 150 ; b = 240 .c ) a = 60 ; b = 84 .d ) a = 150 ; b = 77 .

2. Si a y b son dos nmeros naturales, a 2b. Demuestre que el conjunto de divisores comunesde a y b es el mismo que el conjunto de los divisores comunes de b y a 2b.3. Utilice el algoritmo de Euclides para encontrar el MCD de los nmeros siguientes:

a ) 360 y 2100.b) 468 y 312.

c ) 400 y 840.

4. Utilice el algoritmo de Euclides para encontrar el MCD de los nmeros siguientes y en cadacaso, determine el conjunto de divisores comunes de estos nmeros.

a ) 144 y 840.b) 202 y 138.c ) 147 y 490.

5. Encuentre el conjunto de todos los divisores comunes de a y b.

a ) a = 300 ; b = 350 .

b) a = 168 ; b = 2160 .c ) a = 308 ; b = 364 .

6. Si se divide 4 294 y 3 521 por un mismo entero positivo, y se obtiene respectivamente 10 y11 como residuo. Cul es este entero? Sugerencia: Todo divisor comn de dos enteros es undivisor de su MCD.

7. Sea b es un natural tal que 260 < b < 300. El MCD de a = 600 y de b es 12. Encuentre b.

Teorema De Bezout.

8. Son los nmeros a y b son primos entre si?

a ) a = 42 ; b = 65 .b) a = 147 ; b = 350 .c ) a = 442 ; b = 693 .

36


37/72

9. Encuentre todas las parejas de nmeros naturales primos entre si y cuya suma sea 12.

10. Sean a y b dos enteros, a = 18 . Encuentre todos los valores de b sabiendo que b es primo cona y 20 < b < 30.

11. Sea n un nmero natural cualquiera; a = 3n + 4 y b = 2n + 3 . Pruebe que si d divide a a y b,entonces d divide a 1. Qu se puede deducir para a y b?

12. Sea n es un entero natural; a = 2n + 1 ; b = 3n + 2 . Encuentre una relacin entre a y b,independiente de n . Deduzca que a y b son primos entre s.

13. Sea n es un entero natural; a = 7n + 4 ; b = 5n + 3 . Encuentre una relacin entre a y bindependiente de n . Deduzca que a y b son primos entre si.

14. Utilice el algoritmo de Euclides para encontrar una pareja (x, y ) de enteros tales que 89x +41y = 1 .

15. Utilice el algoritmo de Euclides para encontrar una pareja (x, y ) de enteros tales que 59x +27y = 1 .

Caractersticas y Propiedades del MCD.

16. Explique el porqu en cada uno de los casos siguientes, se puede encontrar muy rpidamenteel mximo comn divisor de a y de b.

a ) a = 5 12; b = 11 12.b) a = 3 15; b = 8 15.c ) a = 22 26; b = 15 26.d ) a = 12 20; b = 35 20.e ) a = 32 12; b = 75 12. f ) a = 100 24; b = 63 24.

17. Encuentre dos nmeros naturales a y b cuyo MCD es 4, tal que a + b = 48 .

18. Encuentre dos nmeros enteros naturales a y b cuyo MCD es 8, tal que a + b = 144 .

19. Encontrar las soluciones del sistema:

xy = 7875MCD(x, y ) = 15

Si (u, v ) denota una solucin del sistema y g el MCD de u y de v; u y v son los enterosu =

ug

y v = vg

.

a ) Qu se puede decir de u y v ?b) Calcule u v y deduzca los valores posibles de (u , v ). Deduzca los valores posibles de

(u, v ). Verique que estas son las soluciones del sistema dado.

37


38/72

20. Sean a y b dos nmeros naturales. Encuentre a y b sabiendo que ab = 1734 y que el MCD dea y de b es 17.

21. Sea n un entero natural; a = 2n 2 y b = n (2n + 1) . Justique que 2n y 2n + 1 son primos entresi. Deducir que n es el MCD de a y b.

Aplicaciones.

22. En cada caso, encuentre todas las parejas de nmeros naturales (x, y ) que cumplan las con-diciones:

a ) 6y = 11 x y 0 x < 25.b) 7y = 3x y 0 x < 15.

23. Encuentre todas las parejas de nmeros naturales (x, y ) tales que: 4(x + 3) = 3 y.

24. Encuentre todas las parejas de nmeros naturales (x, y ) tales que: 3(x 2) = 5( y + 3) .25. Sean a y b dos nmeros naturales primos entre si, tales que a2 + a = 7b3 .

a ) Demuestre que a y b3 son primos entre si.b) Demuestre que a divide a 7. Encuentre los valores de a y b vericando las hiptesis del

texto.

26. Pruebe que la fraccin n2n + 1

, n

N , es irreducible.

27. El objetivo de este ejercicio es el de encontrar aquellos valores del natural n, n > 4, tal quela fraccin n + 17

n 4 sea un entero.

a ) Demuestre que decir que n

4 divide a n + 17 es equivalente a decir que n

4 divide

a 21.b) Determine todos los valores de n para que la fraccin dada sea un entero.

28. Sea n es un natural y a = n (n + 1)( n + 5) . Pruebe que a es divisible por 6.

29. Sea n es un natural y a = 5( n 2 + n )2 . Pruebe que a es divisible por 20.

30. Sea n es un natural, n > 2.

a ) Demuestre que el MCD de n + 13 y de n 2 es igual a MCD de n 2 y de 15.b) Cules son los valores de n para que la fraccin n + 13

n 2 sea irreducible?

38


39/72

Mnimo Comn Mltiplo.

31. En cada uno de los casos, encuentre el MCM de los nmeros a y b dados:

a ) a = 24 ; b = 56 .b) a = 180 ; b = 450 .c ) a = 308 ; b = 4004 .d ) a = 120 ; b = 300 .e ) a = 72 y b = 108 . f ) a = 175 y b = 490 .

32. En cada uno de los casos, encuentre el MCD de los nmeros a y b dados y deduzca su MCM:

a ) a = 24 ; b = 56 .b) a = 300 ; b = 750 .

c ) a = 1386 ; b = 546 .d ) a = 30 ; b = 36 .e ) a = 260 y b = 400 . f ) a = 123 y b = 82 .

33. Cul es el mas pequeo natural que dividido por 140 y por 252 da 40 como residuo?

34. Resolver para x y y el sistema: xy = 360

MCM(x, y ) = 60Se denota por (u, v ) una solucin del sistema y calcule el MCD g de u y de v.

1. Si u = gu y v = gv , qu se puede decir de u y v ?2. Calcule el producto u v . Cules son los valores posibles de (u , v )?. Deduzca los valoresposibles de (u, v ). Verique que estas son las soluciones del sistema dado.

PARA APRENDER A INVESTIGARLos ejercicios en esta parte son de dicultad media en su mayor parte, no se resuelven losejercicios. La investigacin quiere mostrar cmo se puede organizar una bsqueda y seguir unrazonamiento.

35. Saber si una fraccin es irreducible. Objetivo: Encontrar los valores del natural n para

saber si la fraccin n 3 + n2n + 1 es irreducible.

39


40/72

a ) Comprenda el problema. Por denicin, una fraccin ab

es irreducible cuando a yb son primos entre si. El problema es, pues, encontrar los valores de n para los cuales2n + 1 y n 3 + n son primos entre si. Por tanto, vamos a buscar los divisores comunesposibles de 2n + 1 y n 3 + n .1) En general, se denota por d a un divisor comn y se utiliza cuantas veces sea necesario

el hecho que si d divide a y b, d divide al nmero au + bv. El problema esta en elegirbien u y v con el n de obtener informacin sobre d.

2) En general, tambin en la bsqueda de los divisores de un nmero A, es til si esposible, factorar A , ya que si A = BC , el conocimiento de los divisores de nmerosB y C puede conducir al conocimiento de los divisores de A.

Aqu: n 3 + n = n (n 2 + 1) . Denotemos por d, un factor comn de los nmeros 2n + 1 yn (n 2 + 1) y veamos si d puede tener un divisor comn con n , y tambin con n 2 + 1 .1) Para elllo, denote por d a un divisor comn de d y n . Teniendo en cuenta que si d

divide a 2n + 1 , pruebe que d = 1 .2) Qu decir entonces de d y n? Por qu puede decir que d es un divisor comn de

n 2+ 1 y 2

n+ 1 ?3) Pruebe que d divide a n (n2) y justique que d divide a n2. Deduzca d = 1 o d = 5 .

b) Hemos demostrado que si d es un divisor comn a 2n + 1 y de n 3 + n , entonces d = 1o d = 5 . El caso d = 1 corresponde a una fraccin irreducible. El caso d = 5 es la nicaposibilidad dado que la fraccin es reducible. Supongamos entonces d = 5 y veamos sipodemos sacar conclusiones sobre n.1) Observando los resultados de las preguntas anteriores, justique que si d = 5 enton-

ces, n 2 = 5q , luego n = 5q + 2 con q entero.2) Pruebe recprocamente que si n = 5q + 2 , entonces, la fraccin es reducible.3) Concluya.

c ) Redacte una solucin.

Divisores Comunes. Mximo Comn Divisor. Nmeros Primos entres.

36. Demuestre que para todo entero k , 2k + 1 y 9k + 4 son primos entre si.

37. Sea n es un nmero natural. Encuentre el MCD de n + 1 y n (2n + 1)

38. Para todo nmero natural n , mayor o igual a 5, se consideran los nmeros: a = n 3 n 2 12n yb = 2n 2 7n4.

a ) Demuestre, despus de la factorizar, que a y b son naturales divisibles por n 4.b) Sea a = 2n + 1 y b = n + 3 . Denote con d al MCD de a y b.

1) Encuentre una relacin entre a y b independiente de n .2) Demuestre que d es un divisor de 5.3) Demuestre que los nmeros a y b son mltiplos de 5, s y solamente s n2 es mltiplo

de 5.

40


41/72

c ) Demuestre que 2n + 1 y n son primos entre s.d ) Determinar los valores de n y en funcin de n , el MCD de a y b . Verique los resultados

obtenidos en los casos particulares n = 11 y n = 12 .

39. Sean a y b son dos enteros; A = 11 a + 2 b y B = 18a + 5 b.a ) Demuestre que si uno de dos nmeros A o B es divisible por 19, lo mismo ocurre para

el otro.b) Si a y b son primos entre si, A y B no pueden tener otros divisores comunes que no sean

1 y 19.

40. Sea a es un entero estrictamente positivo. Si m = 20a + 357 y n = 15a + 187 , y g el MCD dem y de n. Demuestre los cuatro enunciados siguientes:

a ) g divide a 323.b) g es mltiplo de 17 equivale a que a es un mltiplo de 17.c ) "g es un mltiplo de 19 equivale a que" existe un entero k tal que, a = 19k + 4 .d ) 289 es el menor entero a tal que g = 323 .

41. Sean a y b dos enteros estrictamente positivos. Sean m = 15a + 4 b y n = 11 a + 2 b. Demuestrelos dos enunciados siguientes:

a ) m es un mltiplo de 7, lo que equivale a n es un mltiplo de 7.b) Cuando a y b son primos entre si, el MCD de m y de n es un divisor de 14.

Aplicaciones del Teorema de Gauss

42. Si n esta un los entero pruebe que n (2n + 1)(7 n + 1) es divisible por 6.

43. Sea n es un nmero natural. Se detone a = n (n 2 + 5) .a ) Demuestre que a es divisible por 2.b) Explique porqu todo nmero natural n puede ser escrito bajo la forma 3k o 3k + 1 o

3k + 2 , siendo k un nmero natural. Verique que para cualquier n , a es divisible por 3.c ) Qu se puede deducir de las armaciones precedentes?

44. Sea n un entero. Pruebe que:

a ) n(n + 1)( n + 2)( n + 3) es divisible por 24;b) n(n + 1)( n + 2)( n + 3)( n + 4) es divisible por 120.

45. Sea n un nmero natural. Pruebe que (n 2 1)(n 2 )(n 2 + 1) es divisible por 60.

46. Sean n y p enteros estrictamente positivos.

a ) Demuestre que n (n 4 1) es divisible por 30.

41


42/72

b) Demuestre que la ltima cifra en la escritura decimal de n p y n p+4 es la misma cifra. [2]equivale a n p+4 n p es divisible por 10.

47. Sean x y y son enteros y (E) es la ecuacin 2x5y = 1 .

a ) D una solucin particular (x 0 , y0 ) de esta ecuacin.b) Verique que (E) equivale a 2(xx 0 ) = 5( yy0 )c ) Encuentre la solucin general de esta ecuacin.

48. Sean x y y enteros y (E) es la ecuacin: 3x + 4 y = 1

a ) D una solucin particular (x 0 , y0 ) de esta ecuacin.b) Verique que (E) equivale a 3(xx 0 ) = 4( y0 y)c ) Encuentre la solucin general de esta ecuacin.

49.

a ) Verique que, sea cual sea el valor del natural n , n 2 + n y 2n + 1 son primos entre si.b) Sea n un natural. Demuestre que si n es solucin de la ecuacin 21(n 2 + n ) = 4[(2 n +1) 3 40(2n + 1)] , entonces 2n + 1 un divisor de 21. Complete la resolucin de esta ecuacin

en N .

50.

a ) Aplique el algoritmo de Euclides a los dos enteros a = 41 y b = 27 . Deduzca una solucinparticular en de la ecuacin 41x27y = 1 .

b) Deduzca de la pregunta anterior una solucin particular en de la ecuacin 41x27y = 5 .c ) Resuelva la ecuacin 41x27y = 5 .d ) Pruebe que existen al menos dos enteros relativos k y n tal que 13k23n = 1 . Determine

con la ayuda del algoritmo de Euclides dos de estos enteros.e ) Resuelva en la ecuacin 156x + 276 y = 24 .

MCD, MCM

51. El MCM de dos nmeros es 216. Uno de los nmeros es 72. Cul es el otro?

52. Resuelva los siguiemtes sistemas: xy = 1512MCM(x, y ) = 252 y xy = 300

MCM(x, y ) = 60 .

1. Encuentre todos los divisores (naturales) de 108.2. Encuentre todas las parejas (x, y ) de enteros naturales donde el MCD d y el MCM m sontales que: m 3d = 108 y 10 < d < 15.

53. Determine todas las parejas (a, b ) de nmeros naturales donde el MCM m y el MCD d vericanla relacin 8m = 105d + 30 .

42


43/72

54. Resuelva la ecuacin: MCD(x, y ) 9MCM(x, y ) = 13 .55. Sean a y b son enteros tales que a > b > 0, g es su MCD y m su MCM.

a ) Determine g y m cuando a = n (2n

1) y b = ( n1)(2 n1), con n es entero positivo.

b) Sea p = ag y q = bg . Exprese en funcin de p y q los nmeros a y b tales que m (a + b) = abg

(1)c ) Entre los nmeros a y b que se relacionan por (1), encuentre a aquellos que satisfacen

g = ab (2) .d ) Demuestre que los nmeros enteros a y b que satisfacen a la vez a (1) y (2), son tales que:

(ab)2 = a + b (3) Los nmeros enteros a y b que satisfacen a (3) tambin satisfacenellos las relaciones (1) y (2)?

e ) Denote por r al resultado de la divisin de a por b y se supone que a y b satisfacen a larelacin (3). Calcule a y b en funcin de r , para r = 0 . Aplquelo cuando r = 11 .

Fracciones56. Sea n es un entero cualquiera; a = n 3 2n + 5 y b = n + 1 .

a ) Compruebe que para todo entero n : a = ( n 2 n 1)b + 6 .b) Demuestre que el MCD(a, b ) = MCD(b, 6).c ) Para cada valor de n se tiene que el MCD(a,b) = 3?

d ) Determine n para que el nmero ab sea un entero.

57. Sea n es un entero cualquiera. Suponga que A = n1 y B = n 2 3n + 6 .a ) Demuestre que el MCD de A y B es igual al MCD de A y 4.

b) Determine de acuerdo a los valores del entero n , el MCD de A y B .c ) Para cuales valores del entero n , n = 1 , n

2 3n + 6n 1

es un entero?

58. Pruebe que si la suma de dos fracciones irreducibles es igual a un entero, entonces los deno-minadores son iguales.

59. n es un entero, n > 1; suponga a = n2 + 1

n (n 2 + 1).

a ) Pruebe que el conjunto de divisores comunes del numerador y el denominador de a es elconjunto de divisores comunes de n 2 1 y 2.

b) Deduzca que si n es par, entonces la fraccin es irreducible, y que si n es impar entoncesel MCD del numerador y del denominador es igual a 2.

43


44/72

Parte IIILas Congruencias.

Actividad 1. El lenguaje de las Congruencias.Introduccin a las congruencias

Desde la antigedad, se sabe que ciertos problemas se resuelven analizando los residuos de ladivisin euclidiana. Uno de los problemas ms frecuentes es el clculo de la hora:

Example 1. Si en este momento son las 8:00AM, qu hora ser dentro de 97 horas?Para resolver este problema, se observa que cada 24 horas ser nuevamente las 8:00AM, as, lo

importante es descomponer 97 en tantos bloques de 24 horas como se pueda y analizar qu sucedecon las horas sobrantes; dado que 97 = 24 4 + 1 , cuando se hayan cumplido 96 = 24 4 horas,ser nuevamente las 8:00AM, por lo que luego de 97 horas ser las 9:00AM.

Es importante notar que problemas como el anterior versan sobre la Divisin Euclidiana, peroel cociente no es lo realmente importante sino que el residuo y el divisor. En el ejemplo anteriorinteresa analizar la posicin que ocupa un nmero a partir de un mltiplo de 24 y no cuntas dashan transcurrido; por comodidad y siempre que sea posible, se preere trabajar con el mltiplo quesea l

Date post:	02-Jun-2018
Category:	Documents
Upload:	herberson-salazar
View:	225 times
Download:	0 times

Documento Teoria Del Numero

Documents