teoría de números

q0a-

Teora de nmerosfpara princiPiantes]

Luis R. JimnezB'Jorge E' Gordillo A'

Gustavo N' Rubiano O'PRopPsoRPs

Universidad Nacional de ColombiaFacultad de Ciencias

Sede Bogot

.{tIu.^rov,*l "

vi, 284 p. : 3 il.ISBN 958-70L-372-7Q4241.

1. Teora de nmerosLuis R. Jimnez B.,Jorge E. Gordillo 4.,Gustavo N. Rubiano O.

Tpone DE NMERos [eae pRrNcrprANTEs], 2A. EDrcrN.Universidad Nacional de Colombia, Sede Bogot.Facultad d Ciencias . 2004

Mamtoverlos SuBJEcr CLASSTFTcATToN 2000: 11-01.

@ Ed,i,ci,n en castellano: Luis R. Jimnez B., Jorge E. Gordillo A.,Gustavo N. Rubiano O.Universidad Nacional de Colombia.

Primera impresin, 2004

Impresin:Pro-Offset Editorial Ltda.Bogot, D. C.COLOMBIA

Indice General

Prlogo

1 Nmeros Naturales

1.1 Axiomas de Peano

tx

1

1

2

o

7

10

13

26

25

27

1.2 Adicin de nmeros naturales

1.3 Multiplicacin de nmeros naturales

L.4 Orden entre nmeros naturales

1.5 Construccin de los nmeros enteros

1.6 Formas equivalentes aI principio de induccihltnatemtica

Divisibilidad

2.L Propiedades br4sicas

i2.2 Mximo Comn Divisor MCD

vl ruorce GENERAL

2.3

,A

2.5

2.6

2.7

2.8

Algoritmo de Euclides

Propiedades del Mximo Comn Divisor

29

33

Mnimo Comn Mltiplo y generalizaciones 39

Teoremafundamentaldelaar i tmt ica . . . . . 46

Algunas propiedades de los nmeros primos 51

Algunasecuacionesdiofnt icas . . . . , 58

Funciones Aritmticas 64

3.1 La funcin parte entera 64

3.2 Las funciones nmero y suma de divisores 70

3.3 Nmeros perfectos, de Mersenne y de Fermat . . . . . 74

3.4 La funcin de Euler 78

3.5 Funciones multiplicativas 86

3.6 La frmula de inversin de Mbius 90

Congruencias 98

4.I Definicin y propiedades bsicas 98

4.2 Cr i ter iosdeDivis ib i l idad. . . . .104

4.3 Ar i tmt icamdulon . . . . .106

4.4 Los Teoremas de Euler y Fermat . . . . LL4

4.5 Congruenciasl ineales . . .L2I

4.6 EcuacionesDiofnt icasl ineales . . . . . I25

4.7 Sistemas de congruencias lineales . . I27

4.8 El Teorema chino del residuo . . 131

INDICE GENERAL

4.9 Congruenciasdegradosuper ior . . . . .L37

4.10 Congruencias con mdulo una potencia de un primo . . . . . I40

4.11 TeoremasdelagrangeyWilson . . . . . I47

Residuos cuadrticos 153

5.1 Congruencias de segundo grado con mdulo primo . . 153

5.2 Ley de la reciprocidad cuadrtica . . 160

5.3 El smbolo de Jacobi . . . L67

5.4 Potenciasmdulonyracesprimit ivas . . . . . 172,5.5 Algebra y teora de nmeros . . . 180

Criptografa I94

6.1 Nocionesbsicas . . . . .L94

6.2 Cifrados monogrficos . . 195

6.3 Ci f radoenBloques . . . : . . . .206

6.4 Ci f radosExponenciales. . . .213

6.4.L Algoritmo para calcular P'mdulo p. . . . . 2L4

6.5 Sistemas de Clave Pblica . . . . 2LT

6.5.1 SistemaRSA . . .2L9

6.5.2 SistemadeRabin . . . . .22L

6.5.3 Sistema de Ia mochila . . 225

Flacciones continuas ' 23O

7.I Raccionescont inuasf in i tas . . . .23I

7.2 Convergentes . . .235

I

vlll INDICE GENERAL

7.3 Racciones continuas infinitas . . 242

7.4 FYaccionescont inuasper idicas . . . . .248

7.5 Aproximacindenmerosirracionales . . . . .253

Nmeros primos menores que 1-0.000 267

Respuestas y sugerencias 262

Bibliografa 280

Prlogo

La segunda edicin de este libro mantiene el mismo espritu conque fueconcebida la primera; es decir, se trata de un texto bsico de iniciacin alestudio de Ia Teora de Nmeros. La principal caracterstica de esta nuevaedicin es la adicin de un captulo sobre Criptografa, que muestra una delas principales aplicaciones de la teora desarrollada.

Tambin se ha hecho una revisin cuidadosa de los temas tratados yde las correspondientes secciones de ejercicios, se han adicionado algunassecciones y se ha actualizado la bibliografa. Esperamos que estos cambioshagan el material ms til y atractivo para los estudiantes.

Finalmente queremos expresar nuestra gratitud a todas las personas queleyeron la primera edicin, y nos hicieron llegar sus valiosos comentarios ysugerencias que tuvimos en cuenta para la preparacin de la presente edicin.En especial, manifestamos nuestro agradecimiento a los profesores Paz Mo-rillo (E-UPB-TL; Barcelona) por Mathemati,cal Reui,eus IMR 2000j:11001],y Gabriel D. Villa-Salvador (Cinvestav, Mxico D. F.) por Zentralblatt lZbl0956.1101] quienes gentilmente evaluaron la edicin original y nos motivaronpara realizar esta nueva versin.

ix

INDICE GENERAL

Prlogo a la primera edicin

En la formacin de toda persona que se dedique a la enseanza o al estudiode las matemticas, o cualquier nivel, no puede faltar un curso de Teorade nmeros. Esta hermosa teora, ha sido llamada por K. F. Gauss, lareina de las matemticas. La simplicidad de su objeto, Ia elegancia y ladiversidad de sus mtodos, la formulacin sencilla de numerosos problemasno resueltos, hacen de esta disciplina una de las reas ms fascinantes deluniverso matemtico.

En este libro se ofrece una introduccin breve y eficiente de los temas,que a nuestro modo de ver son fundamentales para iniciarse en el estudiode esta teora. A lo largo de sus captulos estudiamos detalladamente lossiguientes, tpicos: nmeros naturales y enteros, divisibilidad y nmerosprimos, funciones numricas, congruencias y fracciones continuas.

En el estudio de todos los temas, presentamos numerosos ejemplos y pro-ponemos una buena cantidad de ejercicios, la mayora de ellos con respuestaso sugerencias, que permiten al estudiante avarrzar con mayor seguridad enla asimilacin de los contenidos.

Con este libro, creemos llenar la necesidad de un texto claro, sencillo yeconmico, dirigido principalmente a los estudiantes de las carreras y licen-ciaturas de matemticas ofrecidas por nuestras universidades.

Luis Rafael Jimnez BecerraJorge Enrique Gordillo Ardila

Gustavo Nevardo Rubiano Ortegn

Depa.rtamento de MatemticasUniversidad Nacional de Colombia

Ciudad Universitaria, Bogot, Colombia.mj inenez9S@yahoo. con

gnrubianoo@ural . edu. coJunio de 2004

cnprulo L

Nmeros Naturales

1.1 Axiomas de Peano

El conjunto de los nmeros naturales se puede caracteriza mediante lossiguientes axiomas, introducidos por el matemtico italiano Giuseppe Peanoen 1899:

-

A-1 Hay un elemento especial O e N.\

A-2 Para todo n

N existe un nico elemento n+ N llamado el sucesoroe n.

A-3 Para todo r e N, n+ 10.I- A-4 Si n,r

N y n* : r* entonces n -

rn.

A-5 Si ^ 9 es un subconjunto de N tal que:

I t . oe ^ 9,2. n+

^9 siempre que ? ^9, entonces .9: N.

CAPTULO 1. NMEROS NATURALES

En Ia formulacin de los axiomas de Peano se supone de antemano laexistencia del conjunto N. El axioma A-3 establece Ia existencia de un pri-mer nmero natural que es 0. El axioma A-4 indica que nmeros naturalesdiferentes tienen sucesores diferentes.

El axioma A-5 se conoce como EI Pri.nci,pi,o de Induccin Matemd,tica-abreviadamente, PIM-. En las aplicaciones de este principio Ia hiptesisn

S, a partir de la cual se demuestra que n+ S, se denomina Hiptesi,sde Inducci,n.

1.2 Adicin de nmeros naturales

1-.L Definicin. Las siguientes ecuaciones definen Ia adicin en N. Paratodo rn,n

N:

m*0:rrrI r -L

nL+n, : \ rn+n), .

' Como todo nmero natural distinto de cero es el sucesor de un nmeronatural la adicin resulta bien definida.

L.2 Teorerna. La adi,cin de ruimeros naturales es asoc'iatiua, es d,ec'i,r:Para todo n, rn, /c

N

(n+m)lk:n*(m+k).

Demostracin. Usaremos el axioma A-5 -PlM-.

Sea ^ 9: {k N I (" +m)+k:n+(m-f k) para, todo n,rn N};

1. 0

,S puesto que

(n+m) +0 :nlTn: n+ (m+0) (def. suma)

2. Supongamos que k e S, es decir que para todo n, rn N

(n+m)l l t , :n+(m*k).

1.2. ADICTN DE NMEROS NATURALES

Entonces,

(n + m) + k+ - [@ + m) + k]+ (def. suma): [n * (m + k)]+ (hip. induccin): n * (m + k)+ (def. suma): n i (m + k+) (def. suma)

Iuego &+ S y por A-b, ,g: N.

Para demostrar la conmutatividad, probamos primero:

1.3 Lema. Para todo rn

N, 0 * m: m.

Demostracin. SeaS:{m N | O_tm:*} .

1. 0 e,S, puesto que 0 * 0 : 0 por definicin de suma.

2. Supongamos que m e S, es decir, que 0 * rn: rn. Entonces:

0 + rn+ : (0 + rn)+ (def. suma): m* (hip. induccin)

Luego m+

S y, por A-5, ,S : N.

1.4 Lema. Para todo nr,n

N, rnt * n: (m -f n)+.

Demostrac' in. SeaS:{n N I m+ +n:(rn+n)+ paratodornN}.

1. 0

,S, puesto que para todo rn e N

' m+ * o : m* (def. suma).

: (rn + 0)* (def. suma)

2. Supongamos que n e S, es decir, que para todo rn e N

m+ +n: (rn+n)+.

tr


Entonces para todo rn

N, tenemosm++- =i,[iii. ,'.l;niilll ,".,

As, n+ e ,9 y, por A-5, ^9: N.

LJ

1.5 Teorema. La adi,c,in d,e nmeros naturales es conrnutatiua: nara tod,om,nN, rn*n:nlrn.

Demostracin. Sea S -- {"e N I rn * n : n * mpara todo rn e N}.

1. 0

^9, puesto q\e n'L*0 : m : 0 + m.

2. Supongamos que n e S. Entonces, para todo rn

N,

m + nt : (m * n)+ (def. suma): (n -f m)+ (hip. induccin): nt + m (Lema 1.4).

As, n+

,S y, por A-5, ,S: N. !

1.6 Teorema. S'i n,rn y k son nmeros naturales tales que m -f k : TL * k,entonces rn: n,

Demostracin. Sea

,9:{ke Nl s i mIk:TL|-kentonces'rr l : rL paratodorn,ne N}.

1. 0

S, pues si n y rn son naturales tales que ml\ : TL-l0 pordefinicin de suma concluimos qtJe rm: n.

2. Supongamos que k e S y sean n,rn eN tales que

, r - .1- ' - lr r l+ K' : n+ K'

1.3. MULTIPLICACION DE NUMEROS NATURALES

Entonces,(m + k)+ : (n + k)+ (def. suma)

lrrego. por A-4, m*k:rLJ_ k y, por la hiptesis de induccir\rn:rL.

-{. k+ ,S y .9: N, por A-5. tr

1.3 Multiplicacin de nmeros naturales

Las siguientes ecuaciones definen la multiplicacin en N. Patra todom.nN,

m0:0,'IrLrLt : Tnn -t rn.

Como todo nmero natural distinto de cero es el sucesor de otro nmeronatural, Ia operacin resulta bien definida.

1.7 Teorema. La multiplicaci,n es d,i,stributi,ua con respecto a la adi,ci,n,es dec'ir: para todo rrl,n,k

N, rn(n + k) : mn + nxk.

Demostrac'in. Sea

,9 : {k e N I rn,(n + lc) : mn * mk paratodo rn,r NI}.

1. 0

,9. En efecto,

m(n * 0) : ^n

(def. suma): mn l0 (def. suma): mn I m0 (def. multiplicacin).

2. Supongamos que k e S..

Para todo m,n

N, tenemos

m(n * k*) : m(n + k)+ (def. suma): n'L(n I k) + m (def. multiplicacin): (mn -f mk) + m (hip. induccin): rnn + (mk * m) (Teorema 1.2): rnn -f mk+ (def. multiplicacin)


As, k+

S y, por A-5, ^9: N.

L.8 Teorema. La multiplicaci,n de nmeros naturales es asoc,iatiua: po,ratodo n,m,k e N (nzn)k : m(nk).

Demostrac'in. Sea

S : {k e N (rzn)k : m(nk) para todo r, rn NI}

1. 0

,9. En efecto, la definicin de multiplicacin nos permite afirmarque

(mn)0: 0 y tambin qtrc m(n}) : m0 : 0

2. Supongamos que k e S. Para todo rn,n

N tenemos:

(mn)k+ : (mn)k * mn (def. multiplicacin): m(nk) -f mn (hip. induccin): m(nk + n) (Teorema 1.7): m(nk+) (def. multiplicacin);

luego k+ S y, por A-5,

^9: N. !

1.9 Teorema. La mult'iplzcaci,n de nmeros naturales es conmutatiua. Esd,eci,r: Para todo m,n

N, rmn: TLm.

Para demostrar el Teorema L.9 es necesario probar antes los lemas siguientes:

1.1-0 Lema. Para todo m

N, enernos 0m:0.

L.11 Lema. Para todo m,n

N, tenemos m*n: mn I n.

Tanto la demostracin de los Lemas 1.10, 1.11 como la del reorema 1.9 lasdejamos como ejercicio al lector.

n

] . .4. ORDEN ENTRE NMEROS NATURALES

Ejercicios 1. 1 ,

L. Demostrar que todo nmero natural diferente de cero es de la formanr para algn n

N.

2. Demostrar que para todo n

N, nt : n * 0+.

3. Si rn y r son nmeros naturales tales que mln: 0, probar eue ?7) : 0y n:0.4. Demostrar que sim,n

N entoncesml-n Ny rnr

N.5. Probar que si n)n'L e N son tales que rnrl:0 entonces m:0, o n : 0.6. Demostrar los lemas 1.10 y 1.11 y el Teorema 1.g.

1.4 Orden entre nmeros naturales

1.12 Definicin. Dados nL)n . N decimos que:

m I nsi existe p

NI tal que n - m I p.

Veamos que la relacin ( define un orden sobre N. En efecto.

L. La relacin ( es reflexiva.Para todo rn

N, m 1 mpuesto que rn : rrl1-0 con 0 g N.2. La relacin ( es antisimtrica.

Si n,m son nmeros naturales tales que m 1 n y n < rn, entoncesexisten p,e e N tales que n : Tr l - fpy m: n+q. Luego, rn:(*+p)Iq:*+(p*q). Por 1o tanto, p+q:0 y, en consecuencia,p: q:0, lo que impl ica m: n.

3. La relacin es transitiva.Sim,n,r

N son tales que rn lnJn3\ entonces rL: r rL+pyr: n*q donde p,e

N, y por lo tanto , : (*+p)+e: m+(p+q)donde p-l q e N, luego m4r.


Como es usual, definimos n'L

1.4. ORDEN ENTRE NMEROS NATURALES

caso 1. n' < n' En este caso r : nl, *p+ donde p

N y por lo tanto,

nt :n*0+: (m+p+)+0+= rh* (r+ + o+=mt(r++o+= rrl r (p+)+

luego rn < nt.

Caso 2. rrL: n. En este caso n* : Tr -l 0* : m* 0+, es decir rn I n+ .caso 3. n < n'1. En este caso rn : Trrp+ donde p

N. si p : 0 entoncesm: n *0+ : n*. Si p * 0 entonces rn: n*pt : n+(p+0+) :(n + 0+) t p: nt * p, luego n+ < rn.

Hemos visto entonces que para todo rn

N, se cumple alguna de lasrelaciones f f i 1ni ,n :n*rTt* 1m, en consecuenciari

Sypor A-5,S: N.

El lema demuestra que solamente se puede tener una de las afirmacionesffi 1 fr, rn : n) n < n'L y as se termina la demostracin del teorema. n

otras propiedades del orden en N sern enunciadas en los siguientesejercicios.

Ejercicios 1.2

Demostrar cada una de las siguientes afirmaciones:

1. Si n

N y n+0 entonces n) L.2. Para todo n

N, n 1n+.

3. Si rn,n N con n-L 1 n y n < rentonces nL < r.

10 CAPTULO 1. NMEROS NATURALES

4. Si r

N con m1n entonces para todop N, rn+p

1.5. CONSTRUCCIN DE LOS NMEROS ENTEROS 11

1. Si r, U, z e Z entonces (n + A) * z : r + (y + z),2. S\ r ,y e Zentonces r + A : A + r .

3. Para todo r Z,r*0 : 0 I r : r .

4. Paratodor Z,existeAe- Z ta lque ly:Q.

Las pruebas de los enunciados 1 a 4 se dejan como ejercicios al lector. Elelemento y de la propiedad (4),se denomina eI opuesto de r y se denota(-z). Usualmente escribimos r - A en vez de r + (-U).

MuluplrcAcrN DE NMERos ENTERos

Definimos la multiplicacin en Z mediante las siguientes reglas:

1. Si r, g

N usamos Ia multiplicacin definida en N.

2. Para todo r e Z, defrnimos r0:0r:0.

3. Si rn, n son naturales diferentes de cero, definimos:

(a) (-m)n: n(-rn) : -(mn).() ( - - ) ( -n) : mn.

Nuevamente observamos que dados z, g distintos de cero donde al menosuno de ellos no es natural, alguna de las alternativas (a) o (b) define suproducto.

A continuacin enunciamos las propiedades fundamentales de la mul-tiplicacin de enteros.

1. Si z, a,z eZ entonces (ny)z: n(Az).2. Si r,A e Z entonces nA : Afr.

3. Para todo r 2, nI : r .

4. Para todo r, y, z

Z, r(a + z) : nA + nz.5. Si u, g

Z con n f 0, A l0 entonces ry + 0.


6. Si z, y,z Q.Z, z f 0 son tales que rz: UZ entonces r:U.

Las demostraciones de las afirmaciones anteriores son ejercicio para el lector.

ORopN EN Los NIrpnos ENTERos

La relacin definida por

r lAsiysolosiA-reN

es una relacin de orden total sobre Z.

o Si r < A y r * a escribimos r < A.

c Si 0 < r decimos que z es w entero posi'tiao. Denotamos pot Z+ elconjunto de los enteros positivos.

o Tambin usamos r > 0 para decir que ,t es positivo.

o Los enteros u que satisfacen (-") > 0 se denom\nan negat'iuos.

o .Tambin escribimos r 10 para decir que z es negativo.

EI orden definido sobre Z tiene Ias siguientes propiedades:

1. Si r , A e Z+ entonces r+A eZ+ y ry V'+.

2. S\ r,A Z entonces una y solo una de las siguientes afirmaciones esverdadera r 1 A, r : U, A < fr.

3. Si ; , AZsontalesquen (3rentoncespara todo z,r Iz1A+z'

4. Sir ,A,z,uZsontalesque r lAy z< u;entonces r lz lg+w-

5. Si z, A Zson tales que r < A y z ) 0 entonces rz 1 yz.

6. Si z, A eZson tales que z < A y z ( 0 entonces yz 1 rz-

EI lector debe verificar que la relacin ( es en efecto una relacin de ordentotal y demostrar adems las propiedades enunciadas.

1.6. FORMAS EQUIVALENTES AL PRINCIPIO DE INDUCCIN MATEMTICA 13

1.6 Formas equivalentes al principio de induccin ma-temtica

Al enunciar los axiomas de Peano, indicamos que el axioma A-5 se conocecon el nombre de Principio de Induccin Matemticay seguidamente vimossu fuerza en la demostracin de varios resultados sobre las operaciones connmeros naturales. Nos proponemos ahora presentar algunas formas equi-valentes y mostrar su aplicacin en la prueba de enunciados matemticos.En esta seccin nos referiremos al axioma A-5 como el PlMl.

1-.1-5 Teorema (Principio de buena ordenacin (abreviadamenteP BO) ). Todo subconjunto no u aco S de nmero s naturales po see un rnnimo.Es deci,r, eristenx

S -TTL: min,S- tal que para todo s -,S; m 1s"

Demostracin. Ulilizamos el PlM1. Sea

T : {n N I n ( s paratodo s e,S}.Como S +g tenemos que 7lN, yaque si s/ ^9entonces st+I (7.

Adems0e TyporPlMLexistemeT talquen' ,*L f ?. Necesa-riamente m e S, pues como m I s para todo s ,S, si m (,S se tendraque rn < s para todo s ,5 por lo tanto ml | ( s para todo s

,S y enconsecuencia m*l e T que es contradictorio. Por lo tanto rn : min,S. n

Como una aplicacin al PBO demostraremos un resultado fundamentaldel sistema de los nmeros enteros denominado el Algoritmo de la di,uisin.

1.16 Teorema (Algoritmo de laEntonces eristen enteros n'i,cos q,r

a:bq*r

divisin). Sean a,b enteros con b > 0.tales que

con 01r 0yas a-ab

,S. Luego S#a.

Ahora por el PBO, ,9 tiene un mnimo r y en consecuencia existe unentero q tal que

a-bq--r con 01r.


De otra parte, puesto e r : min 5, entonces

r - b : (" - bq) - b - o - (q+ 1)b < 0,y por tanto r < b.

2 Unic idad. Supongamosque:bq*r:bq'+r ' con0 ( r 1by01rt o} y sea T: {k N lk > a}- ,S. Luego T + s ypor elPBO tiene un mnimo rn.

Adems, puesto que a ,9 entonces m > a y para todo k tal que

a 1 k 1 m,Ia minimalidad de r nos garantiza qtte k e S, y por Ia condicin2 concluimos que rn

. S lo cual es una contradiccin. n

Antes de presentar alguna aplicacin de PlM2 veamos algunas definicio-nes.


1.18 Definicin. Sean o, b nmeros enteros con a, diferente de cero. De-cimos que diaid,e b si existe un entero c tal que b : ac. En tal casoescribimos a I b. Decimos tambin que a es un diuisor de b o que b es unmlti,plo de a.

Para indicar que no divide a b escribimos a { . Es fcil verificar quepara todo entero k, 7 | k y si k + 0,.k I k.1.1-9 Definicin. Un entero positivo p > 1 se denomina un nmero primo sitiene exactamente dos divisores positivos a saber: 1 y p. Un entero positivomayor que 1 que no es primo se denomina compuesto.

1.20 Teorerna. Todo entero rno'Aor o i'gual que 2, o es prirno o es un pro-ducto de nmeros primos.

Demostrac'i,n. Sea,S el conjunto de todos los nmeros naturales que sonprimos o que pueden escribirse como producto de primos.

Claramente S S {k N I k >2} y adems tenemos:

1. 2 e S porque 2 es.un nmero primo.

Supongamos que ?z > 2 y que k ,9 para todo k tal que 2 1 k < n.Veamos que 7? e S. Si n es primo entonces n S. Si n no es primo'existen r y tales que n : rt cor2 1 r < n y 2 < t < r y porhiptesis ellos o son primos o productos de primos. En consecuencia nes producto de primos y as n ,S. El PlM2 nos afirma entonces queS:{kN I k>_21.

Como otra aplicacin de este principio vamos a estudiar Ia representacinde todo entero positivo en base b, con b un nmero natural mayor que 1.

1.21 Teorerna. Sea > 1. Todo nmero natural > 0 se representa dernanera n'ica en la fonna:

tr , : cnbn + cn-tb"-\ + . . . + cb I co

donden)-0, c-+0 y 0 !c 1b paratod,o' i :0,1,2, . . . ,n.

2.


Demostracin. l- Existencia. Sea ^ 9 el conjunto de enteros positivos que pue-den escribirse en la forma mencionada. Es evidente que 1 e ,s. supongamosquer> lyquetodoenteroktalque r 1}, lo cual prueba ra existenciade Ia representacin.

2 unicidad. supongamos que tiene dos representaciones a saber,

a:cnbn +cn-t f - r +. . .+ ctb*co:d,rnb^ td,*- tn-t +. . . id,-tdodonde cn + 0, d* 10, 0 < ci< y 0 S d

1..6. FORMAS EQUTVALENTES AL PRINCIPIO DE INDUCCIN MATEMTICA 17

El teorema anterior nos permite construir sistemas de smbolos pararepresentar los nmeros enteros positivos, as: Escogemos smbolos pararepresentar los dgitos es decir, los enteros no negativos menores que b yreemplazamos el nmero,

cnb" + cn-Lbn-r +. . . + c1b I co

por el smboloCnCn-t ' ' ' CICO.

El sistema que usamos comnmente tiene base b : 10 y se denomina elsistema d,eci,mal. En este sistema el smbolo 8375 representa el nmero

(8)(10)3 + (3)(10)2 + (7)(10)r + 5.

Si escogisemos b : 8, el nmero cuya representacin decimal es 8375 estrepresentado por 20267 puesto que

8375 : (2X8)n + (0)(8)3 + (2)(s)2 + (6)(8)r + 7.EI nmero b en el teorema se denominala base d,el si,stema. Cuando usamosuna base diferente a 10, para indicar cuI, la escribimos como subndice, aspor ejemplo:

SBZ5: (20267)8.Cuando Ia base es mayor que 10 es necesario inventar smbolos para losdgitos 7I,12,. . ., (b - 1). Por ejemplo cuando la base es L6 -sistemaheradec'imal- se establece:

l0: A, IL: B, 72: C, 13: D, 14: E, 15 : F.

Por ejemplo:(a0)ro : (4)(16)1 * 0 : 64.

(7F)rc: (7)(16)1 * F: (7)(16) -r15:r27.(F'F ' ) ro: ( r ) (16)1 * F: (15)(16) * 15:255.

El sistema hexadecimal es especialmente usado en computadores al igual queel sistema en base 2, este ltimo por la facilidad para describir situacionesfsicas del tipo'ser o no ser', 'estar o no estar'.

Los clculos y reglas para las operaciones de adicin y multiplicacin' $n esencialmente los mismos en cualquier sistema, ya que solo dependen


del carcter posicional de la notacin y no de la base utilizada; por ejemplolas tablas de adicin y multiplicacin en base 5 son:

01234

I23410

1

2341011

2

344t0

10 1111 12t2 13

01234

01234

0001020304

0241113

003411 1314 2222 31

Hallemos ahora (232)5G4I)5 usando las tablas:232

x 141232

2033232443L2

es decir (232)5(L4I)5: (44312)5.

Por una aplicacin repetida del Algoritmo de Ia Divisin podemos fcil-mente encontrar la representacin en base b de cualquier entero positivo a.Si dividimos entre b, el cociente nuevamente entre b y as hasta obtenerun cociente menor que b tenemos:

a:bqr+rr , 0 l r r


Escribiendo adems

en:0blrk+r, 01r11b

de las ecuaciones anteriores resulta inmediatamente que,

a: bqt I r ta: b(bqz -l rz) + rr : b2qz -f br2 7,

o : birr*, * bk-rrr+ "' + br2 | 11,y por lo tanto,

a:(r . . . r t )u.I.22 Ejernplo. Hallemos la representacin de 756 en base 8:

756364

Luego 756:(1364)s.

Volviendo a las diferentes versiones del PIM tenemos la siguiente versinsimplificada del Teorema 1.17.

L.23 Teorema (PlM3). Sea a un nmero natural fi,jo y

U:{keZ I k>o}.SeaSCU talque:

aes

Para cadaf l ) a,

t .

2.

894746

sine S entonces n*1S.

,20 CAPTULO 1. NMEROS NATURALES

Entonces S : U.

Demostrac'in. Sea n > a y supongamos que k e S para todo k tal quea1k ( n. Enpart icular set iene entonces que n-1

^9 ypor lacondicin2 de la hiptesis del teorema se sigue que ??

,S y por PlM2, S:(J. tr

Finalmente veamos que PlM3 implica PlM1.

I.24 Teorerna. PlM3 implica PlMl.

Demostrac'irz. Supongamos^9 G Ntalque (i) 0 e ,S, y (ii) Si n S entoncesn i L ,S. Tenemos que probar que ,9 : N.

Sean,

T:{rN | (x:a*sparaalgnse ,5},, U:{reN lu >a}.

Entonces T EU, y adems,

1. ae Tpues a:a*0y0e ,S.

2. Si n) a es tal que n eT entonces rL : a*s con s ,9 y por lo tanto

n*l : (a*s) * 1 : a* (s + 1) e ?, puesto que s* I ^9.

En consecuencia por el PlM3, T : U.

Ahora, si n e N entonces n * a ) o y como U : T, n* a 7; es decir,existe s e,S tal que nj :a* s y por lo tanto n : s, luego N g S y porlo tanto ,S: N. n

Si revisamos los resultados expresados en los teoremas L.I,I.L7, L.23 y1.24 tenemos la siguiente cadena de implicaciones:

PlMl _, PBO

1lIJ

PlM3


Es decir todas las proposiciones son equivalente y nos referiremos a cual-quiera de ellas como el Pri,nci,pio de Inducci,n Matemtica.

Ejercicios 1.3

En los ejercicios 1 a 6 demuestre que la proposicin es cierta para todo n ) r.

1. 1 + 2 +B +.. . * n : n(n + L)12.2. 12 +22 +. . . * n2 : ( r l6)n(n+ 1)(2n + 1).3. 13 + 23 +. . . * n3 : (L l \n2(n + I )2.4. Sir l lentonces

| * r * 12 +. . . I rn : ' : ' "* ' .L-r5. 13 + 23 +' . . + (n- 1)3 < t . r t +23 +. . . *n3.6. 22n+r - 9n2 * Sn - 2 es divisible por b4.

7. Definimos ros nmeros Fn de Fermat mediante la formula,

Fn : 22n * 1 para n : 0r1, . . . .Pruebe que para todo n ) I , FsF1.. .Fn_t t 2: Fn.

Para representar la surTto, ay]- az+. . .*a, de n nmeros reales uti,liza_mos el smbolo DT:ta que defi,ni,mos 'ind,ucti,uamente d,e la siguienteforma:

1

Doo: o 'i : l

y suponiendo que ya hemos d,efi,nido D!:ta para algn n ) I fijo,defini,mosnl l /n \

Io, : l f " ,

l *o,"*r .=- \ f /


Demostrar por induccin:

8. DT:t@ * b) : D,?:ta +D,?:rb9. lit@a) : cD,?:ra'

i"*,:(,,) (r)tj : r

t0. lir@ - a-t) : an - a0 (Propiedad telescpica)'

11. Demostrax que

Para representar el prod,ucto de n nmeros reales a!a2r... ran ut'i l i-zanlos el srnbolollT:ta que se define de manera andloga al de suma.


12. flir@b):0L-1' ") (lIT:tb).

13. f!ir@a) : cn l[!:t a.

14."

'o\ an . ITT l - | : - gr la i f0para' i :0,1, . . . ,n.il \at-t / ao

El smbolo nl (Ied,o ene factorial) se defi,ne inductiuamente como s'igue:0! :1 A paran) l , n! :n(n - 1)! . Se obserua f 'c i lmente que

nt. : I ' 2 ' 3. . . . (n - L) ' n.

Adem,s s,in es un ruimero natural y k es un entero arb,itrario d,efi,ni,mosel coeficiente binomial mediante:

(r , \ ( r r rn l r ' , s i o1k

16 FORMAS EQUIVALENTES AL PRINCIPIO DE INDUCCIN MATEMTICA 23

Demostrar la formula del tringulo de Pascal

( n )* l : ) :1"1t)\k-1l \k/ \ k /

pataneNytodoenterok.


Los coeficientes binomiales son nmeros naturales.

Si a y b son nmeros reales diferentes de cero, para todo entero positivon se tiene:

a' / \

(a -t b)" : t (".) ""-n'

(Teorema d,et bi,nornio)l=o\*/

Si b es un entero positivo fijo, todo entero n 2 0 puede escribirse en laforma n : bqf r con g y r enteros no negativos y 0 1 r 1 b./ A\T( f r )" > npara todo entero n)-7.Ley asoc'iat'iua generali,zada. Sean 41, a2..., a' nmeros reales conn ) 3. Demuestre que dos maneras cualesquiera de sumar estosnmeros tomados en ese orden, producen eI mismo resultado.

Encontrar el error si Io hay- en la siguiente demostracin. Si no loencuentra, compare con la realidad.

Teorema. Todos los caballos son del m'ismo color.

Demostrac'in. Sea P", la proposicin: "Todos Ios caballos en un con-junto de n caballos, son del mismo color."

(a) & es verdadera.lb) Supongamos que P es verdadera y supongamos eu c1, c2, cs,

..., ck+L son los k + 1 caballos en un conjunto de k* 1 caballos.Con*sideramos {c1, c2tcz. . . ,ck}. Por la hiptesis de induccin todosestos caballos son del mismo color. En el conjunto anterior reempla-cemos ck por c-r1 entonces en el conjunto resultante {"r,"2,c3t...,c-t.cn+t\ todos los k caballos son del mismo color. Ahora cr y ck:on del mismo color y tambin cL y ct+r, entonces todos los k + 1caballos son del mismo color. Luego Pn+t es verdadera y por el PIM

-

concluye Ia afirmacin del teorema. n

16.

17.

18.

19.

20.

2r.

,A^A CAPITULO 1. NUMEROS NATURALES

22. Demostrar que no hay nmeros naturales entre 0 y 1.Sugerenc'ia: Uttlizar el PBO y propiedades de orden de N.

23. Demostrar que el PIM es equivalente a la siguiente afirmacin:Sea

Zy sea,9 un subconjunto de {k eV,lk ) a} tai que,(a) ae S.(b) n+ 1

,9 cadavez que n ,9.

Entonces,9: {k e Zlk> a}.Se define inductivamente la sucesin de Fi,bonacci mediante:

'LLL : ' tL2: 1 Y 1trn*2 : Un+7 * Un Si n ) l .

24. Demostrar que para todo entero positivo n,

f t l - \2

/ - \n1u.:+l l+4) _l+) |" /5

1\ 2 ) \ 2 ))Sugerenc'ia: Comprobar primero que los dos nmros o : \S ,.

I - \ /5b: --; son races de la ecuacin n2 : r 17.

r+\ /EI numero ,

es llamado Ia proporcxon aurea.

25. Si establecemo, ,o : 0, entonces para tod.o entero m )- 0y todo enteror)0set iene,

Unlrn1-l : UnLrn * Un1Urn1.

26. Para todo entero n) 7y todo entero m) I se t iene qneunlurnn.27. Construir tablas para Ia adicin y multiplicacin en base g y calcular

(4685)e(3483)e.28. Expresar (a00803)e en el sistema de base 5 sin pasar por la base 10.29. En un sistema numrico con base b, un nmero se escribe (34)6 y su

cuadrado se escribe como (1552)a. Cul es el valor de b?.30. En qu base los nmeros 479,698 y 907 estn en progresin aritmtica?

cnprulo 2

I

Divisibi l idad

2.1 Propiedades bsicas

\a en el captulo anterior dimos significad;; h expresin ,,a divide a b,, quescribimos as, "a I b,, .

Aun cuando algunas propiedades ya las enunciamos y probamos, recopi-lames stas y otras propiedades en el siguiente teorema.2'1 Teorema. suponganxos que a,b y c son nmeros enteros. Entonces:

1. Siaf 0 entonces al \ , a la, a l (_a).2. 71a, (- t ) l o.3. Sialbentoncesalbc.

4. Si, a I b a b I c entonces a I c.5. Si a lb,y olc entonces paratod,o f ,A

2, al (br+c.-\

25 q'l

26 CAPITULO 2. DIVISIBILIDAD

6. Si, al b a b f 0 entonces I al< | l.7. Si a lb A b I a entonces o, : b o a : (-b).

Demostracin. (5) si a I b y a I c entonces existen enteros r y tales queb: ar y c: as) luego cualesquiera sean u, gr enteros tenemos

br -l cy : (ar)r + (as)y : a(rc * sA),luegoal(br+c.

(6) como a l existe cz tal que b: ac. puesto qtrcbl0 entoncesct' 0 y por lo tanto I c l> 1, y en consecuencia I b l : l c l l a l) l a l .

(7) Por (6) tenemos l lSl b lv lb l< l o I lego I a l : lb I y por lo tantoa:boo:(-b). t r2.2 Ejemplo. Para todo entero positivo rn, el producto de rn enteros con-secutivos es divisible por mt.

En efecto, consideremos

(k + 1)(k +2)(k+ 3). . . (k + m).Si /c > 0, tenemos,

.

(k + 1)(k + 2) . . . (k + *) _

kt(k + 1)( / r + 2) . . . (k + m)'rnl. W

(k+m)t _.(n+m\

ktmt. \ rn )luego,

(k + 1)(k + 2) . . . (k + m) : ( r *_*\ *r .' \n 'L/

Si k < 0 se presentan dos alternativas:

1. El producto es 0, en cuyo caso la parte (1) del reorema2.L garantizaque este producto es divisible por m!.

2. EI producto es distinto de 0, en cuyo caso se puede expresar, salvo porun signo, como el producto de enteros positivos consecutivos y se siguedelcaso k>0.

2.2. MXIMO COMN DIVISOR MCD

2.3 Ejemplo. Para todo entero positivo n, (nl)2 divide a (2n)1. En efecto,i 2n)! : I . 2 . Z . . . n(n + r) (n + 2) . . . (n + n) : n! . (n + r)(n + 2) . . . (n + n).Por el ejemplo anterior (n + I)(n + 2) . . .(n + n) : t(n!), por lo tanto

(znl : (n!)t(n!) : t(nt)2 .

2.2 Mximo Comn Divisor MCD

2'4 Definicin. sean o y b enteros no ambos iguales a cero. El conjuntode todos los divisores comunes de a y (un divisor comn de a y s unentero que divide a ambos nmeros o,y b) es un conjunto finito de nmerosenteros cuyo mximo se denomina el Mdri,mo comn Di,ui,sor de a y b.rLonotamos MCD(a, b) o simplemente (a, b).

Puesto que, si r I a entonces.r | (-a), es fcil observar que(a,b) : (o,-b) : ( -a,b) : ( - .a,-b).

2.5 Teorema. sean a y b enterog no ambos i,guares a cero., Et MCD(a,b)o--s el menor entero positiuo que pued,a escrib,irse en la forma ar I bg

"on *, y

enteros.

Demostrac'in. Supongamos que d: (o,) y seaS : {z Z+ | z : ar * by con r ,y e Z}.

S + q puesto el)E 2 : a2 + b2 ,S. Luego por el pBO, ,S posee un mnimo,ilammoslo g que podemos escribir en la forma g : afro * bao.probaremoseue g : d: (o,b). En efecto g es divisor comn de a y b, pues si dividimos4 entre g tenemos:

a:qg*rcon01r


Ahora, si r l0 entonces r ,9 lo cual contradice Ia minimalidad de g, enconsecuencia r :0 y as g I a. Anlogamente se verifica que g I b.

Como d: (o,b) V g es un divisor comn entonces g < d.De otra parte g : atr*bAo y d I o y d I b luego d I g V como ambos

nmeros son positivos d 1 g y en consecuencia d: g. tr

Es importante observar que los enteros r,'y del teorema anterior no son,nicos, en efecto si t eZ y ( ; ,b) - ano* bgr entonces (a, b): a(*o+bt) +b(ys - at).

Tambin se ve claramente que por ser el mnimo de un conjunto, el MCDes nico.

Igualmente es importante observar que el solo hecho de escribir un enteropositivo d, en la forma d,: ar *by no garantiza que d : (a,b). Solamentepodemos afi.rmar que (a, b) | d.

Por ejemplo,

4 : (6)(3) + (2)(-7) y sin embarso (6, 2). :21 42.6 Teorema. Sean a y b enteros no ambos cero. Entonces d,: (a,b) si, ysolamente si, d, sati,sface las s,igui,entes propi,edades:

1. d>0.

2. d laydlb.

3. Si | "

y f lb entonces f I d.

Demostrac'idn. Supongamos que d : (o,b). Tenemos inmediatamente qued>0y que d loy d lb. Ademsd,:ar*by para algn par de enteros r ,gry si

"f | "

v f I b entonces por el Teorema 2.1 f I d.

Recprocamente supongarnos ahora que d satisface (t)r. (Z) y (3) y su-pongamos que

"f es un divisor comn de a y b; entonces por (3) f I d y enconsecuenciu l/ lf l dl: d,luego d es el mayor de los divisores comunes de

?v o'2.7 Teorema. Si, a: bq * r entonces (a,b) : (b,r)

n

2.3. ALGORITMO DE EUCLIDES

Demostrac' in. Supongamos que d: (a,b) y d ' : (b,r) .Como dlay dlbentonces d, l r : a-bq en consecuencia d ld ' . Anlogamente d! la:bq*ry en consecuencia dt I d. Qorno d, y d,t son positivos entonces d,: d! . tr

2.3 Algoritmo de Euclides

An cuando hemos presentado criterios para decidir si un entero positivo eso no el mximo comn divisor de dos enteros, no hemos presentado an unprocedimiento eficiente que nos permita encontrar el MCD de dos enterosdados a y b. Solucionamos ahora esta dificultad al presentar el denominado.4lgori,tmo de Eucli.des. Euclides (365-300 AC) en su libro Elementos, dioeste mtodo para el clculo del MCD.

Si 0 < b 1 a, aplicamos el algoritmo de divisin y escribimos

a:bqr+rr ,0(11

CAPTULO 2. DIVISIBILIDAD

Puesto que (a, b) : (a,-) : (-o,b) : (-a,_) el algoritmo anterior per_mite encontrar el MCD de cualquier par de enteros.

Tambin las ecuaciones precedentes nos permiten encontrar enteros r yg tales que (a, b) : ar + bU.2.8 Ejemplo. Encontrar (687, -284) y expresarlo como combinacin lineaide 687 y -234.

Aplicando el Algoritmo de Euclides, tenemos,

687: (234)(2) +2792]4: (219)(1) + 152!s

-

(15)(14) +'915:(e)(1)+6e:(6)(1)+36:(-3.)(2)+0.

Por lo tanto, (687, -2J4) : (682, 2J4) : g.Adems, empezando con la penltima ecuacin obtenemos.

3:9-66:15-99:279 - (15)(14)

L5 :234 - 2792Ig:687 - (2)(2J4),

y reemplazando los residuos sucesivamente tenemos,

3:9-6-B-[15-e] : (2)(e)_15:2127e

- (14)(lb)l - '1b : (2)(2Le) * (2e)(1b): (2)(2re) _2e[234_2re]: (31)(21e) _ (2s)(234)

31 [687 _ (2) (234)] _ (2s) (234)- (31)(6s7) - (e1)(234),

luego(687, _234) : 3 : (31)(687) + (e1)(_234).

2.3. ALGORITMO DE EUCLIDES

El procedimiento que presentamos a continuacin, conocido como algoritmoertend,'ido de Eucli.des, se puede programar fcilmente en un computador ypermite hallar eI MCD de dos enteros y escribirlo como combinacin linealde ellos.

Sean 0 < b < a enteros, y supongamos que tenemos las ecuaciones:

a:bq1I11, 0 < rr < bb:r1q2I12, 0112111

n:r2qs+ryj 01rs


que es la ecuacin con Ia cual comenzamos el algoritmos de Euclides.

Supongamos que (2.1) es cierta parai < j donde 2 < j ( k. por lasfrmulas de recurrencia tenemos:

ani+t * bA+t : a(r-t - A+t) * b(g-t - Aa+i: (an-r + bA-i - @* r ba)q+t: rj_r - rjej+1..

Adems, puesto que rj-1 : rj qj+r I , j*, obtelemos ar j+r * bA+t : r j+ty, por eI PlM, Ia relacin (2.1) es cierta para i : L,2,. . . ,1c.

2.L0 Ejemplo. Encontremos (1001, 275) y escribmoslo como combinacinlineal de ellos.

1001 : (275)(3) +776275: (176X1) + 99 |176:(e9X1)+77ee:(77)(1)+zz77:(22)(3)+rr22:(Lr)(z)+0.

Usando las frmulas de recurrencia tenemos la siguiente tabla,'

012345

31113

011-3

-1 42-7-3 1111 -40

por lo tanto,

(1001,275) :11 : (1001)(11) + (275)(_40).

2 4, PROPIEDADES DEL MXIMO COMN DIVISOR

2.4 Propiedades del Mximo'Comn Divisor

Hemos mostrado que si d : (a, b) entonces existen z, gr enteros tales qued : ar * by. El siguiente teorema muestra el nico caso en el que se da Iaequivalencia de las dos afirmaciones.

2.11 Teorerna. Sean a y b enteros no ambos nulos. Entonces,

(a,b) :1 si ' y solo si er i ,sten enteros r ,y tales que I : ar lby

Demostrac'in. Si (a,b):1 el Teorema 2.5 garantizala existencia de talesr.g. Recprocamente, si existen r,y tales que 1: arlby entonces (a,b) | t1- por lo tanto, (a,b) :1.

2.L2 Corolar io. Si d, : (a,b), entonces (f t ,*) : t .

in

Demostrac'in. Puesto que d : (a,b) existen enteros r,y tales que d :ar*ba, por Io ru":., al dividir o:t r,;""-ot,

t :: j r+a. n2.13 Definicin. Si a y b son enteros no ambos iguales a cero tales que(a,b) : 1, decimos que o, y b son primos relatiuos. Ms generalmente siaLta2t. . . ,&n son enteros tales que para todo i y para todo j con i , f j , 1 1i , j

34 CAPITULO2. DIVISIBILIDAD

Demostrac, in. Siplaentonces (a,p) :1, yporel teoremap lb. t r2.16 Corolar io. Sip es pr imo Uplapz.. .ant entoncespla para algni , I 1 i , 1n.

Demostrac'in. La demostracin es por induccin.

2.17 Corolar io. Si p,pt,p2,. . . )pn son nmeros pr imos y

P I PtPz.. 'Pn,

entonces p: pi para algn i, I 1 i 1 n.

Demostracin. La demostracin es por induccin.

2.18 Teorema. .9C (a,b) : L A (o,c) : 1 entonces (a,bc) :1.

Demostrac'in. Puesto que (a,b) : t y (a,c): l tenemos que,I : an - fba y tambin I : ar I cs

corr r) U, r, s enteros y por lo tanto '

1 : (ar I by)(ar -f cs): a(rar I rsc I byr) + bc(ys)

y en consecuencia (a,bc) :1.2.19 Corolar io. Si , (a,b) : I para, i : 'L,2,. . . ,n entonces

(a,b1b2.. .b, . ) : L.

Demostrac'in. La demostracin es por induccin.

Si n : 1 es claro que (a, br) : 1.Supongamos como hiptesis que, s i (a,b):1para i : I ,2, . . . ,k

entonces (a,bft2 ... b - 1 y asumamos adems, que (a, b) : 1 parai :7r2r. . . rk, Ie + l .

Apl icando el teorema con (a, btbz.. .bn): I y (a,br+r) : 1 se sigue elresultado. rr

tr

!

n

2.4. PROPIEDADES DEL MXIMO COMN DIVISOR

Una aplicacin de este corolario Ia observamos en el siguiente ejemplo.

2.20 Ejemplo. Si p es un nmero primo entonces p | () para todo /c :r ,2, . . . , (p - l ) .

En efecto,(p\ p(p - t ) . . . (p - (k - 1))\ ' / : H

'

Como k


Demostrac'in. Basta probar el resultado para /c > 0. Supongamos qued : (a,b) entonces kd, I ka y kd I kb y por Io tanto kd | (ka,kb).

Por otra parte, d,: ar lby para algn par de enteros r,y ltego kd,:kar * kby y por lo tanto (ka,kb) | kd, luego kd: k(a,b) : (ka,kb). n

2.24 Ejernplo. Si (a,b) : 1 entonces (3a - b,4a + b) : I o 7.

Supongamos que d: (3o -b,4a * b), entonces d | 3a-b y d | 4a-fb;por lo tanto,

dl l (3a - b) + (4a+b) l :7qv

d | [(-a)(sa - b) + 3(4a + b)] : 7b;Iuego

d | (7a,7b) : 77o,b) : (7)(7) : 7,y f inalmente d,: I o d: 7.

2.25 Ejemplo (Los nmeros de Fibonacci). Los nmeros de Fibona-cc'l , descubiertos por Leonardo Fibonaccil (1170-1240) se definen por lascondiciones siguientes:

' t t r t : l , U2:1y para n ) 2, Unl I : Un l 'L ln- t .

Veamos, por induccin, que para n ) I, (un,un*r): 1. Si n : t, (ut,uz) :(1,11 : 1.

.

Supongamos que (un,un+t) : 1 y sea d : (un+t,un+2), entoncesdlun+t y dlun+z:r ln-rr*unY por lotanto d I [ ( r"+r un)-un+r] : un.

As, d l r, y d I un+t. Luego d | (u",un+L) : 1, y claramente d, : I.Entonces por PlM, para todo n ) I, (un,un1) : L

2.26 Ejemplo. Sean rn,n errteros positivos primos relativos. Veamos que

(m*n-I) lq-mtn!

es un entero. -

'Fiboncci fue quien introdujo al mundo occidental los nmeros indu-arbigos, quehoy usamos, despus de viajarrcon su padre a Bougie, una ciudad entre Argel y T\rnez.

2.4. PROPIEDADES DEL MAXIMO COMN DIVISOR

Si utilizamos el ejemplo 2.2 de este captulo tenemos'

^ - * tQ" + L)Q" + 2) " ' 0" +

" )

-

t ' (n - . I ) l -

tq:G n! n

para algn entero t. Similarmente'

nt(n* 1)(n, + 2)--9-)-- s(rn - 1) ! -

s

't - mlnl. nXl n'L

para algn entero s.

Por lo tanto 1:9 " ,

decir tm: sr l ' As ,ml tny como (rn 'n) :7n n'L s n-Lr

entonces rn I s es decir s :'trr con r entero y q: *: ^

:' '

Ejercicios 2,1

1. Probar que si a lb y c I d entonces aclbd'

2. Probar que el producto de tres enteros consecutivos es divisible por 6'

Si adems el primero es par eI producto es mltiplo de 24'

3. Probar que 100 I (1110 - 1).

4. Probar que para todo r > 1, 30 | n' - n'

. Probar que si n : rscon r > 0 y s ) 0 entonces (r!)" I n'!'

6. Sean ny nL enteros positivos y a> 1' Probar que,

(o" - 1) l (o* - 1) s i solo s in lm'

T.Probarquetodocuadradoperfectoesdelaforma4ko klFlparaalguo entero k'

3. Probar que si a y b son-impares entonces a2 +b2 no es un cuadradoperfecto.

37


9. Use l PBO para probar que todo entero mayor que uno tiene un factorprimo.

10. Hallar el MCD de cada par de nmeros y expresarlo como combinacinlineal de ellos.

382 y 26, -275 y 726, IL37 y 4L9, -2947

y - 3997.

11. Usar el algoritmo extendido de Euclides para encontrar enteros talesque:

7426r * 343a -- 3 630r I I32y : l)g36z

* 6669 : 13 400Ir * 2689Y : [.

12. Probar que si (a,b) : c entonces (a2,b2 : 2.13. Probar que si (a,b): l entonces (a- lb,ab):1.14. Probar que si (a,b) : I y c l b entonces (a,c) :1.15. ProbLr que si (a,b): l entonces (2aIb,a+2b):1o 3.16. Probar que si (b,c) :1 entonces (a,bc) : (a,b)(a,c)17. Probar que si (a,b) : 1 entonces para todo n y m enteros positivos,

(an,bn) : 1.18. Probar que si d I nm y (n,m) : 1 entonces d : d,1d,2 donde dt | ?,

dzlny(dt ,dz): I .19. Probar que no existen enteros z,gr tales que

r lY:200 Y (r ,Y):7 '

20. Probar que existe un nmero infinito de pares de enteros :x)y qnesatisfacen r * y : 203 y (r, : 7.

21. Probar que si ad - bc: *1 entonces Ia fraccin (a + b)l@ * d) esirreducible.

22. Eval:urar (ob,pa) y (a -l b,pa) si p es primo, (o,p') : p y (b,p3) : p2.n. (E Si p es un primo impar y (a,b): 1 probar que

, , aP+W(alb,-) : l o p.' a*b

2.5. MNIMO COMN MLTIPLO Y GENERALIZACIONES

24. Probar que para todo entero posit ivo n,(un+B,un):1o igal 2.

25. Probar que si m: efr * r entonces (u*,u".) : (u.u"-).

26. Probar que (u,r, urr):u@,rn) para todo par de enteros positivos n,rn'

27. Para todo par d9 entero positivos rn y n probar que

unlu, . ,s iysolosinlm.

28. rh Probar que,

si a es parsi es impar.

2g,) f r Sea,9 : : 1* + + " ' + +donde n > 7' Probar que,9 no es unentero.

' Sugerenci,: Sea k el mayor entero tal que 2k 1n y sea P el productode todos los nmeros impares menores o iguales a n. Probar que

2k-1 .P ' ,9 es una suma cuyos trminos a excepcin de 2k-r P +son enteros.

2.5 Mnimo Comn Mltiplo y generalizaciones

2.27 Definicin. El menor mltiplo comn positivo de dos enteros a yb no nulos se denomina el Mnimo Comn MIti'plo de a y b y se denotaMCM(a, b) o simplemente [o, b].

Puesto que dados a y b enteros cualesquiera no nulos, los nmeros ab y-ab son ambos mltiplos comunes de a 7r de b y uno de ellos es positivo,entonces el PBO garantiza la existencia y unicidad de [4, b]. En Io que siguecuando mencionemos el [4, b] supondremos o y b diferentes de cero.

Es inmediato deducir de Ia definicin que,

2.28 Teorema.solo s'i,

la,b) : [-o,b] : la, -b] : [-a, -b).Sean a,b son enteros no nulos. Entonces * : lo,bl si' y

39

Sean a, m,n enteros positivos con

(o ' ' +7, a2^ * r l : {1[2

n + rrl.

40 CAPTULO 2. DIVISIBILIDAD

(i) zn > 0.( i i ) a, lmyblm.

( i i i ) Si r es un entero ta l que alny b ln entonces mln.

Demostrac'in. supongamos que ^: lo,]. Entonces r satisface (i) y (ii).

Paraprobar ( i i i ) supongamos nz talque alnyblny div idamosrzentte m, entonces

n: ef f i * r donde 0 1r 1m.

Si r ) 0 entonces r sera un mltiplo comn de a y , positivo y menor quern, lo que niega la minimalidad de m. Luego r :0 y por tanto m I n.

Supongamos ahora que zn satisface (i), (ii), (iii) y supongamos que r esun mltiplo comn de a y b. Entonces por (iii) rn I n y en consecuencia*: l*l

2,5. MNIMo coMN MLTIPLo Y GENERALIZACIoNES

Reemplazando tenemos rL : ar : a(Bt) : (aB)t - Imt, es decir m I n-; :e completa la demostracin.

2"3O Ejemplo. Ya obtuvimos que (687, -234): 3, por lo tanto,

1687,-2341: K{54 : gryqq:53586.'2-31 Corolario. Sean a y b enteros no nulos. Entonces a y b son prmos-:;;i los si. y solamente si, [a,b] : I ab l.

-

2.32 Ejemplo. Si se sabe que (a,, b) : 1g y la,b) : 1572 encontremos a y b.Si ta.b) :18 entonces a: I8A y b:188 donde (A,B): 1. Por el

- Terrema 2.29, (18)(1512): (LS)2AB luego AB :84,y salvo por el orden-1. posibilidades son,

-1:4 B:?L, A:72 B:7, A:28 B:3, A:84 B:! .

-L.. los nmeros buscados son, salvo por el orden,

47

a:72 b:378a:504 b:54

a:216 b:L26a:75L2 : 18.

fl 4E-3! Ejemplo. sean y enteros positivos. EI nmero de mltiplos de btr -"a sucesin a,2a,3a, . . . ,ba es precisamente (a, ).Flepresentemos por N dicho nmero. si ko es uno de los mltiplos de b

' iL; sucesin, entonces la,b]lka y por lo tanto existe entero tal que,

ko: lo,bl t= ( ab. \ t' - \ ( " ,u) ) "rr i'-,-de O : ( +),

"o-o k ( b tenemos ( (o,b) ypor lo tanto;

\ (' 0,) ,/N < (o, b). (2.2)

lq .c:a par-te. si 1 ( t 1 (a,b) entonces f-+) t 1 b y as\ (a,)/ -

( bt \ / at \ ,\GDi o: \@a)o


es un elemento de Ia sucesin que es mltiplo de b, en consecuencia

ll > (a, b). (2.3)De (2.2) y (2.3), N : (o,b) como queramos demostrar.

Las nociones de mximo comn divisor y mnimo comn mltiplo pue-den extenderse de manera natural a ms de dos nmeros. As por ejem-plo, si a1.ra2,...,dn son enteros no todos nulos, ellos tienen un mximocomn divisor que representamos por MCD(arta2t...,an) o simplemente(ar,a2,...,an). En forma anloga a los casos correspondientes para dosenteros se pueden demostrar Ios siguientes teoremas.

2.34 Teorema. Sean a1ra2r. . . r(Ln nmeros enteros no todos nulos.Si, d, : (ot ,oz,. . . ,an) entonces d es el rnenor entero posi, t iuo que puedeescri,bi,rse en la forma

atr t I o '2r2 * " ' annn con trL)fr2, . . . ) rn enteros.

Demostrac'in. Ejercicio n2.35 Teorema. Sean a1,a2. . . )an enteros no todos nulos. Entoncesd: (ot,a2. . . ,an) s, i y solo si , d sat isface:

( i ) d>0,( i i ) d I at , d l a2; . . . ,d I on,

( i i Si f estalquef lar . . . , f lan,entoncesf ld.

D emo strac'in. Ejercicio

Los enteros et,&2,. . . ,en se denominan pr imos relat iuos si su MCD es1, o sea si (41,. . . ,an):1; en este caso tambin los denominamos pTimosentre s. Es claro que si los enteros ctrLrctr2r...r&n son primos relativos dosa dos, tambin son primos entre s, pero el recproco no siempre es cierto.Por ejemplo (2,4,5) - I y sin embargo (2,4) :2.

El mismo argumento del Teorema2.TL nos permite afirmar que (a1,a2,. . . ra. , . ) : 1 si y solo si existen enteros fr t , r2, . . . , f rn, tales que atr t l " ' Ianfrn: l ,

2.5. MNIMo coMN MLTIPLo Y GENERALIZACIONES 43

De otra parte, si a1, a2, . . . , an son enteros todos diferentes de cero ellosposeen un mnimo comn mltiplo que notamos MCM(a1, a2 . .., arr) o sim-plemente lot,or,...,an]. Tambin tenemos el siguiente teorema cuya de-mostracin es enteramente anloga a la del Teorema 2.28.

2.36 Teorerna. Sean ar,a2,...,an enteros diferentes de cero. Entonces:

- : fot ,&2. . . ,ar ] s i y solo s i m sat isface:

i i ) m)0,i i ) a1 | TrL) a2 | ^

, . . . ,an 1m,

i i i ) Sin es ta l que o,r l r , ozlr , . . . ,anIn entoncesmIn.

D e mo strac'in. Ejercicio

Para efectos del clculo del MCD y el MCM de ms de dos enteros po-iemos hacer uso de la formulas de recurrencia que nos proporcionan los=-cuientes teoremas.

2.37 Teorerna. Si al cL2 . . . , an son enteros no nulos donde n ) ,3 entonces,

(ot ,oz, . . . ,an) : ( (ar , . . . ,an_1),an)

J"-mostrac,in. Supongamos que

d : (or ,a2t. . . ,ar) y d, ' : ( (at , . . . ,an-1) i ,an).

Cirno d I oo para cada ' i : I , . . . ,2 entonces d | (or, . . . , an-r) y tambini q-n.Por lo tanto d I d ' . Por otra parte, d ' l (or, . . . , an-7) y dl lanluego1 ai para cada i - 1, . . . )ny en consecuenciadt l d. Por lo tanto d,: dt .

tr

-{nlogamente se demuestra el resultado siguiente.2-3t Teorema. ,5i er, a2, . . . , an son. enteros no nulos, con n ) '3. Entonces

fot , oz, . . . ,an) : [ [ar , . . . , an-tJ,anf.

n

i,e-,: :trucin. Ejercicio.

CAPTULO 2. DIVISIBILIDAD

2.39 Ejemplo. Encontremos (3081 882,}pf/..) V expresmoslo como combi-nacin lineal de los enteros dados.

882 : (308)(2) +266308: (266)(r)+42266: (42)(6) + L4a2: g4)(B)

luego (308,882) : 14.Ahora,

?s67 : (r4)(2n) ft,;s: (T)(2)

luego (14,2961) : 7 y enconsecuencia

(308,882,2967) : (L4,296L) :7.

Adems.

, , ! :2e6r- (14)(211) i,,L4:266 - (42)(6) ,'

:266-(308-266)(6): (7)('266) - (6)(308): (7)[882 - (308)(2)] - (6)(308): (7)(882) - (20X308)

luego,

7 :2e6r - [7(882) - (20)(308)](211)7 : 2e6I + (882)(-1 477) + (308)(4220).

Podemos calcular tambin [308,882, 296L]:

[808,882] : P(=8=? - (308)(882) :re4o4.(30s,882) 14Puesto que (19404,296L): 63 tenemos:

[7e404, 2s61] : (19404) (2e61) / (63) : e1 1e88

2.5. MNIMo coMN MLTIPLo Y GENERALIZACIoNEs 40

es decir,

[308,882, 296r] : [ [308,8S2], 29611:119404,296I): 911988.

Ejercic tos 2.2

6.

1. Probar que | b si y solo si fa,b): lbl.2. Probar que si fa,b] : (o,b) y a ) 0, b> 0 entonces :b.3. Probar que (a, b) : (a- lb, [a,b]) .4. Probar que [ka, kb]: l k | [o,b],k + 0.5. Si fr es un mltiplo comn de a y b, probar que

Sea d un entero positivo tal que dl o y d I b. Probar que,

| "

bl lo,blla'): d '

sean d y g enteros positivos. Probar que existen enteros a y talesque (a, b) : dy la,bl - 9 s i y solo s i d l g.Probar que Ia ecuacin ar -l by : c tiene soluciones enteras r,y si ysolo si (a,b) | c.Probar que (a, b) : (a,b,ar * Ay) para todo z, gr enteros.Hallar enteros a y b tales que o I b : 276 y la,b] : 480.Hallar todos los nmeros o y b que satisfacen (a,b) : 24 y la,b] : 1440.

7.

8.

9.

10.

11.

46 CAPITULO 2 DIVISIBILIDAD

'12. Hal lar (20n2 +r9nt4,4nrJ) y 120n2 1_r9nr4,4n*31 donde n esun entero positivo.

13. calcular (4410,1404,8712) y expresarlo como combinacin lineal delos nmeros dados.

14. Hallar (rr2,240,L92,760) y expresarlo como combinacin lineal de losnmeros dados.

15' Hallar enteros r,u, z,t tales que 75r r rrrg -l gTz r r20w :6.

16. si p y q son primos impares diferentes y n:pg, cuntos enteros en elconjunto 2,3,. .. , r son primos relativos con n?

17. Probar que labcl : (ab,ac,bc) la,b,c] .18. Probar que labcl ) (a,b,c) [a,b,c] .19. Dar un ejemplo para ilustrar que (a, b,c)[a,b,c] no siempre es abc.20. Demostrar los teoremas 2.84,2.85,2.J6 y 2.Jg.

2.6 Teorema fundamental de la aritmtica

La propiedad ms importante de los nmeros primos es la posibilidad defactorizar todo entero n t r como producto de ellos y esta factor izacinresulta esencialmente nica. Esta propiedad fue descubierta por los griegoshace ms de dos milenios

2.40 Teorema (F\rndamental de la Aritmtica, TFA). Tod,o enteron > 7 o es prirno, o se pued,e factori,zar como prod,ucto de p,imos. Esteproducto es nico saluo por el orden d,e los factores.

Demostracin. En el Teorema 1.20 ya probamos la primera parte. Bas-ta ahora probar la unicidad de la factorizacin salvo el orden. usargmosinduccin sobre n. Para n : 2 claramente la representacin es nical su-ponganlos ahora que para todo entero k con 2 < k 1 n la representaciirnica y supongamos que,

2 6. TEOREMA FUNDAMENTAL DE LA ARITMETICA

donde pi y qison primos con p1 1 pz < "' 1 p" Y h 1 Qz 1 "' 1 qt.

As ,p1 lqrqz. . .qt i entonces pr:qj paraalgnj por lotanto q1 (p1.Anlogamente q1 lprpr...Ps Y entonces qr: pi para algn i y por 1o tantoh 1 qt. Lo anterior demuestra eue pr : q7 y cancelando tenemos,

L : oror. . .Ps: q2q' . . .qt .PT

Como L a n la hiptesis de induccin garantiza que estas dos represen-PT

taciones e L son idnticas (hemos escogido un orden) y en consecuenciaPt

s : t y para cada i, pi: q. Por el PIM la prueba queda completa. n

2.4L Ejernplo. No existen dos enteros positivos tales que rn2 :2n7.

nL + 7 pues de otra forma tendramos I :'2n2-,lo que es imposible.

n I \, puesto que si n :.7 entonces rn2 .= 2 y si la representacin derTL como producto de primbs es n'L : ptpz . .. pk entonces

z: (ppt)(pzPz) . . .@npn)

que contradice el TFA pues en un miembro hay un nmero par defactores primos y en el otro un nmero impar de tales factores.Sean m : prp2.. .pk y n: qtqz.. . q las factor izaciones de rrL y n enfactores primos. Si m2 :2n2 entonces,

(ppt)(pzpz) ' ' ' (pnpn) : 2(qtqt)(qzaz) ' ' ' (qrqt)

que contradice el TFA porque el factor dos aparece un nmero impar deveces en la factorizacin de la derecha y un nmero par en Ia izquierda.Es decir, NO existen enteros positivos m,n tales que m2 :2n2.

47

1.

2.

Agrupando los primos iguales enobtenemos la siguiente forma,

i , l

. )

Ia factorizacin de n debida al TFA' l

' 'n

k l \ i 1f , r ) i " ' ;(2.4)l-f n'TL: I lA. :

L L- L

donde n ) 0 y pi + p si i I j. Esta escritura la denominamos l formacann'ica, natural o normal del entero n.


En las pruebas de algunos resultados intervienen varios enteros diferen-tes, sin embargo es conveniente adoptar representaciones similares a la formacannica donde en algunos casos aceptamos exponentes cero a fin de utilizarel mismo conjunto de primos en las factorizaciones.

As por ejemplo escribimos,6o :22. 3 . b, 45 :20 .82 '5, 2b :20'Bo . b2

donde en todos Ios casos hemos utilizado los primos 2,3,5 en la factorizacin.

2.42 Teorerna. Sea n: llf:tpT".tta representac'in canni,ca de un enteron A sea d un entero posi,ti.uo. Entonces d I n si, y solo s'i

ka:fn!,

i,:rdonde 0 1 d, 1n para cada i,I < i, < k.

Demostracin. Supongamos que d : lIf:rrfo donde 0 < d ( n entonces,k

T-T..n: | | D' . ""rr ' )

i : r . r - -

K

:f lpPrd;+dt; -1

kk:n p7"-o'lIol'

i . : t i : I: (")(d)

donde c:lI!:tp\-di es un entero. Luego d I n,.

Recprocamente supongamos que d I n. Por definicin, existe un enteroc, positivo en este caso, tal q.:ue n: cd,.

La unicidad de la representacin cannica de n nos garantiza que losprimos que aparecen en la factorizacin de c y d son los mismos que aparecenen la de n. As,

kkk:[nl , j c :n p , , n: [nT,

i : I : I i :7

Ir) -

a al-\

2.6. TEOREMA FUNDAMENTAL DE LA ARITMTICA

j,rnde d, ) 0, c ) 0 V TLi : d, I c y entonces d tiene la forma mencionada.!

El TFA nos proporciona otra manera de calcular el MCD y el MCM dej,-rs o ms enteros. Veamos el caso de dos enteros.

2.-13 Teorerna. Sean a:f[f:tp?n, b: flf:, nln d,onilepi es prirno po,ra:,:"lo i. A a ) 0, b ) 0 para todo i,. Entonces:

(a,b) : Ilot a [a,b] :n rl,'i : I i . :1

it 'nde s : min{,b} A t : n1ax{a,b}.

Demostrac'in. Sea' d : llf:rpi'. Veamos que d satisface las condicionesLt. (2), (3) del Teorema 2.6.

Claramente satisface (1).Adems, como 0 ( s ( a,.t y 0 ( s ( b para cada'i,.por el teorema

arterior d I o y d I b, as d satisface (2).

Finalmente si f I a y f I bentonces l/l : lllrrfo donde 0 . fo < &i yr- t 1 f ( b para cada' i , y entonces l f l ld, .Luego f ldV as d sat isface (3).

En forma similar, usando el Teorema 2.28, se demuestra el correspon-diente resultado para eI MCM . tr

2.44 Ejemplo.

1800:f .22.523780 : 22 .33 .5.7

4'900 : 22 . 52 .72.

Entonces,

(1800,3780,4900) : 22'34' 5 ' 70 : 2o[1800, 3780, 4900] :'23 .33 . 52 ' 72 : 264600.

49


Ejercicios 2.3

1. Sea n : lIf:tpf,o "o,

n ) 0la representacin cannica de n. Demos-trar que r es un cuadrado perfecto si y solamente si ?i es par paracada i ,7 < i , < k.

2. Sean a :l[f:tp?n y b: llf:, plo con a 2 0 y b 20. Demostrar que(a,b):1 s i y solo s i ab:0 para todo i , L

2.7. ALGUNAS PROPIEDADES DE LOS NUMEROS PRIMOS 51

2.7 Algunas propiedades de los nmeros primos

Dada la importancia de los nmeros primos, nos gustara poder determinarrpidamente si un entero positivo es o no un nmero primo.

Desafortunadamente no existen mtodos generales que permitan decidirsi un entero positivo es o no un primo y solo en casos especiales conocemossu naturaleza. En el Apndice A al final del libro se encuentra un listado delos nmeros primos menores que 10.000.

Un mtodo simple y eficiente para enteros positivos relativamente pe-queos es verificar si el entero dado tiene o no divisores primos menores que1. Puesto que si n: ab entonces a < 1/n o b < \n es suficiente determinarsi algn primo menor o igual a J es divisor de n.

2.41 Ejernplo. Veamos si 239 es o no un nmero primo. La raz cuadradade 239 esta entre 15 y 16 pues 152 : 225 y 162 :256, luego basta ver sialguno de los primos 2, 3, 5,7, 71, o 13 son divisores de 239 y como ningunode ellos lo es entonces 239 es primo.

Una tcnica llamada criba de Eratstenes en honor del matemtico grie-go Eratstenes (276-194 A.C.) proporciona un mtodo eficiente aplicable anmeros relativamente pequeos para encontrar todos los primos menores oiguales a un entero n dado.

La tcnica consiste en escribir la lista de todos los enteros desde 2 hastan y comerrzar a tachar todos los mltiplos de 2 mayores que 2; al terminar,el primer nmero no tachado distinto de 2 es 3 que es un nmero primo;luego tachamos todos los mltiplos de 3 mayores de 3; al terminar, el menornmero no tachado mayor que 3 es 5 que es un nmero primo; tachamosenseguida todos los mltiplos de 5 mayores que 5 y continuamos el procesohasta tachar todos los mltiplos de p mayores que p para todo primo p < \n.

Los enteros no tachados al terminar este procedimiento son Ios nmerosprimos menores o iguales a n.

La siguiente tabla muestra la criba para n: 90 (.reO < 10)

52 CAPITULO 2- DIVISIBILIDAD

2345f iTpplo11 1.213 /,4 1.5 /,6 77 1.8ig po p,r p2 2J p42,5 2,6 27 2,8 2s po31 p2 p3 B4 ts5 p637 p8 pe A0 4r A243 A4 A5 A6 47 A8Ae F0 Fr F2 53 F4b5 b6 F7 b8 5e fio61 fr2 fr3 fi4 fi5 fi667 fr8 fr8 I0 7r 1273 /74 15 16 17 187e F0 pL p2 83 p4p5 fr6 fr7 B8 8e po

Observamos entonces que los nmeros primos menores o iguales que 90 son:2, 3, 5, 7, lL) 73, 77, Lg, 23, 29, 31, 37, 4r, 43, 47, 53, 59, 61, 67, 7L, 73, 79,83, 89.

Una observacin detenida de Ia criba permite ver que Ia distribucin deIos primos decrece de manera constante, lo que nos podra inducir a pensarque el nmero de primos es finito. Sin embargo Euclides demostr, que elnmero de primos es infinito.

2.46 Teorerna. El nmero de primos es i,nfini,to.

Demostracin. -Dadapor Euclides-. Supongamos que solo hay un nmerofinito de primos,

PrP2r. . . ,Pn Y sea N:pIp2.. .Pnl I .

Como N ) 1, entonces Il es primo o se expresa como producto de primos.Ya que ll es mayor que cada uno de los primos pi entonces ly' no es primo.Adems ningn primo p divide a ly' pues si p | N entonces

po | (N - PtPz. . .Pn) :1

Io que es imposible.

Esto contradice el TFA y por tanto el nmero de primos es infinito. n

2.7. ALGUNAS PROPIEDADES DE LOS NUMEROS PRIMOS

Observamos tambin en Ia criba que todos Ios nmeros primos diferentes


Demostracin. Los enteros (n + 7) l + 2, (n + 1)! + 3, (n + 1)! * 4, . . . ,(n + L)t + n, (n+ 1) ! + (n + 1) son n enteros consecutivos, adems para cada j,2 < i < (n-17), j l ( (n+ 1)!+ j ) . Luego todos son compuestos. n

Otra observacin sobre las tablas de nmeros primos es Ia existenciade muchas parejas de primos gemelos es decir parejas de la forma p,p + 2donde ambos nmeros son primos. Por ejemplo: 3,5; 5,7; 11,13; 29,3I;1 00000000006 1, 1 000000000063 ; L407 37 488353507, 1407 37 488353509.

Todava no hay respuesta sobre la existencia de finitas o infinitas parejasde primos gemelos.

Si hubiese un nmero finito de primos gemelos la serie I j donde qtoma valores en el conjunto de los primos gemelos seria una suma finita ypor Io tanto convergente. Viggo Brun (1885-1978) demostr en 1921 queefectivamente esta serie es convergente. De otra parte Ia serie ! | dondep toma valores en el conjunto de todos Ios nmeros primos es una seriedivergenteJ La primera prueba de este resultado fue dada por Euler (7707-1783) en 1737 y la prueba que aqu presentamos se debe a J. A. Clarksonquien la di en 1966.

2.50 Teorerna. La seriedr,uergente.

donde pn es el n-szmo nmero primo, es

Demostracin. Supongamos que la serie dada es convergente, entonces existeun entero positivo k tal que

Sea Q : prp2...pk y consideremos los nmeros de la forma 1* nQ corrn : I,2,. . ., cada uno de estos enteros no es divisible por los prirnosPt,p2,...pk y entonces sus factores primos se encuentran entre los primosPk+t,Pk+2,. . . , Por lo tanto para cada r ) l ,

\ -1-p,

311) -

55

l+nQ

f (no + ph) : f @o) + (mltiptos de p): p + (mltiplos de p):Y.p

r- as /(n6 Iph) es compuesto.

n

n

2.7. ALGUNAS pRoptEDADES DE Los ruvenos pRtMos

]'a que cada trmino de la suma del lado izquierdo esta contenido en la sumadel lado derecho. Adems

(-t, *)" =r(i)':,,es decir todas las sumas parciares de ra serie D # son acotadas y porlo tanto ella converge, pero el criterio du

"orrparriZ" po. paso ar lmitemuestra que,

t=-f ^ v \_1zr|*ne r /nson asintticamente iguales, luego

diverge pues I j otrr"r*" .En consecuencia ! A es dirrergente.

un problema planteado con frecuencia es la necesidad de encontrar ex_presiones a partir de las cuales obtengamos nmeros primos mediante laasignacin de enteros positivos a cada una de las variables. por ejemplola frmula n2 + n + 41 -dada por Euler- da un nmero primo po,;J;asignacin que demos a n entre 1 y 39, sin embargo para n': 40 resulta

402 + 40 + 4r : 402 + 2(40)* 1 : (40 + 1)2que obviamente no es primo. Mostramos ahora que ningn polinomio enuna variable con coeficientes enteros es til a este propsiio, es decir:2'51 Teorema. ,9 f (r) es un por'inomzo no constante con coefic,ientes en-teros, entonces f (n) es un nmero cotnpuesto para i,nfini,tos uarores d,el en-tero n.

Demostrac'in. claramente el teorema es cierto si /(n) es compuesto paratodo n ) 1. Supongamos que existe no t ltal que /(no) : pcon p primo.Como lim,,-oo lf (")l: oo existe n tal que si n ) ??1 entonce" If @ll > p.Consideremos h tal que zz0 -f ph > r1 entonces

CAPTULO 2 DIVISIBILIDAD

Nota. un problema que ha concentrado la atencin de los matemticosdesde tiempos inmemoriales, es el d.e encontrar formulas que generen todoslos nmeros primos. sobre este tema hay una literatura extensa y soromencionaremos el hecho notable de que se ha encontrado un polinomio degrado 25 con 26 variables y coeficientes enteros p(nt,. . .,rza) tal que cadavez que rr t . . .

' 26 son enteros no negat ivosy p(q,r2t. . . rza) ) 0 entoncesp(rt,...,rza) es primo, y ms an todos los nmeros primos se obtienencomo valores de este polinomio.

sin embargo, observamos que este polinomio no es una formula mgicapara calcular nmeros primos.

un problema famoso relacionado con los nmeros primos, muy sencillode enunciar pero no resuelto hasta la fecha (como es comn en la teora denmeros), es el conocido como la conjetura de Goldbach . cristian Goldbach(1690-1764) fue un matemtico ruso quien a mediados del siglo XVIII enuna carta a Euler, le pregunt si era cierto o no, que tod.o entero positivo

, mayor que 1 se poda expresar como suma de a lo ms tres nmeros primos.Euler le respondi que el problema era muy difcil y que era equivalente alsiguiente enunciado, conocido hoy da como la conjetura de Goldbach: Todoentero positivo par mayor que 2 se puede expresar como la suma de dos nmerosprimos. En 1997, Jean-Marc Deshouillers, yannik saouter y Hermann Rieleprobaron que la conjetura es verdadera parar todo entero positivo menorque 1014. recientemente, en 2003 el matemtico portugus Tomas oliveiraI*il:i

la validez de la conjetura para los enteros poritirro, menores queo x tu".

Finalmente enunciaremos el denominado Teorema d,e los nmeros 7t,i-rnost vno de los ms famosos de la teora avanzad,a de nmeros, que nosproporciona un estimativo sobre la distribucin de los primos en la sucesinnatural.Definimos primero la funcin n(r) que asigna a cada entero positivo r elnmero de primos menores o iguales a r,

n(1) : g, r (2) :1, n(3) :2, r ( tO) : 4.

como ya hemos observado que la distribucin de los primos es muy irregular,no existe una frmula sencilla que defina r(n). El reorema d,e la nmerosprimos establece una aproximacin asinttica de rh).

ob

2.7. ALGUNAS PROPIEDADES DE LOS NMEROS PRIMOS

2.52 Teorema (de los nmeros primos).

I im : ! \ " ) , :1rr+oo I _g_ I\ Ios )

La afirmacin del teorema fue conjeturada de manera independiente porGauss en 1792 y Legendre en 1798 pero slo hasta 1896 J. Hadamard y C. de.a \ allee Poussin demostraron el Teorema por primera vez utilizando teorade funciones de variable compleja. En 1949 A. Selberg y P. Erds dieron''rna demostracin ms elemental sin usar anlisis complejo pero an muyficil para presentarla en estas notas. En 1997, D. Zagier present unaprueba mas corta, dada por Newmann [13].

Ejercicios 2.4

1. Probar que todo primo de la forma 3k + 1 es de la forma 6t + l.

2. Probar que todo primo diferente de 2 o 3 es de la forma 6k+1, o 6k-L.

3. Probar que todo entero de Ia forma 3k+2 tiene un factor primo de Iamisma forma.

-1. Probar que todo entero de Ia forma 4k + 3 tiene un factor primo de lamisma forma.

5. Demostrar que existen infinitos primos de Ia forma 4k + 3.

6. Si p, q son primos tales que p ) q> 5 entonces 24|p2 - q2.i. Demostrar que 3,5,7 son los nicos primos triples. (Los nicos tales

euep, pi2y pf 4sontodospr imos).

!. Si 2" - 1 es primo probar que n es primo.

ot


9.

10.

11.

Si 2" + 1 es primo, probar que n es una potencia de dos.

Sugerencia: Si k es impar (r + 1) | (rk + t).Seanpy q pr imos di ferentes de 2 y 3. Probar que si p-q es unapotencia de dos entonces p + q es divisible por tres.

Hallar un sucesin de veinte enteros consecutivos y compuestos.

2.8 Algunas ecuacones diofnticas

Una ecuacin de la forma p(rt , rz, . . . , r") : 0 donde p(rt , rz, . . . , err) es unpolinomio con coeficientes enteros y con las variables restringidas a tomarnicamente valores enteros se denomina una Ecuacin Diofntica en honoraI matemtico griego Diofanto de Alejandra (200-284) quien por primeravez las estudi detalladamente en su libro Ari,thmeti,ca.

El ejercicio 8 de Ia seccin 2.2 nos da una condicin necesaria y suficientepara que la ecuacin ar -lby : c tenga una solucin en Z. Estas ecuacionesIas estudiaremos detalladamente en el capitulo 4.

Estudiaremos en esta seccin dos casos pa.rticulares de la ecuacin deFermat,

rn +y8: rn (2.5)Fermat afirm haber demostrado que para n ) 3 esta ecuacin no tienesolucin en Z - {0}, sin emba"rgo su demostracin nunca fue conocida.

Nota. Muchos matemticos estudiaron intensamente este problema, que sedenomin el ltimo Teorema de Ferrnat, dando origen a diferentes teorasmatemticas en su intento por resolverlo. En junio de 1993 el matemticoingls Andrew Wiles anuncio la demostracin del teorema como consecuenciade su prueba de la conjetura de Taniyama-Shimura para curvas elpticassemiestables.

Durante Ia revisin de la demostracin de Wiles surgieron algunos pro-blemas que finalmente fueron resueltos por el mismo Wiles y el matemticoRichard Taylor, quienes en mayo de 1995 publicaron en los Annals of Mat-hemat'ics los resultados que llevaron a la demostracin definitiva del ltimoTeorema de Fermat.

28 ALGUNAS ECUACIONES DIOFNTICAS

Para n:2la ecuacin (2.5) tiene solucin en los enteros positivos, por-"tnrplo I :3, a : 4, z :5. Daremos enseguida una descripcin completa:: la solucin en este caso.

Observamos primero que si (r,A,") es una solucin de (2.5) entoncesi:r.ky,kz) donde k es un entero cualquiera, tambin lo es. En consecuen-- es suficiente encontrar soluciones tales que (r, A,z):1. Estas soluciones

= denominan soluc'iones pri,mi,ti,us. Ms an, es suficiente encontrar solu-- -'nes primitivas de enteros positivos pues las dems se obtienen de estas

*-:diante cambios de signos. Tambin es fcil observar que si (r,g,z) es-:-a solucin primitiva de la ecuacin (2.5), con z : 2, entonces Ios enteros.,7.3 sotr primos relativos dos a dos.

En efecto, si por ejemplo (r,A) : d > 7 y p es un primo tal que p I d,:-:onces p I r yp gr luego p l 12 y p I A2 y por lo tanto p | (*2 + A2) ::- ]- como p es primo p I z, en contradiccin con el hecho (r,g,z) : 1.S-rrilarmente se verifica que (r, z) : (A,z) : L.

Finalmente observemos que exactamente uno de los nmeros r o y de la

---ucin debe ser impar, pues si los dos Io fueran, 12 +A2 sera de Ia forma

l;: -2 y por un ejercicio anterior ningn cuadrado perfecto tiene esa forma.

2.53 Teorerna. Los enteros ,A,2 con rimpar son una soluci,n pri,mi,ti,-; g poszti,ua de la ecuaci,n 12 * A2 : z2 sz y solamente s'i etisten enteros

:, , - , t iuos a y b tales que,

, :o2-b2, a:2ab, z:a2+b2,

i- ' ,de a) b, (a,b) : t con a y b de dist inta pari ,dad,.

-''-,tostrac'in. Un clculo directo muestra que las frmulas dadas propor-- -

nan una solucin primitiva y positiva de Ia ecuacin

12 +Y2: 2'

i.= procamente, supongamos que (2, y,z) es una solucin primitiva y po-.- :- ia. donde r es impar. Como (A,r) :1 entonces (, - A,z - f :1 o 2-, ' t ruesto que g es par y z es impar (" - A,z *A): 1; por lo tanto de la:--;acin

,2:"2-a2:(z-y)(z+g)

59

60 CAPITULO 2, DIVISIBILIDAD

concluimos que (z - a) v Q + a) deben ser nmeros impares y cuadradosperfectos, puesto que son positivos.

Supongamos entonces (r-A) - r2 y ("+: s2 donde r y s son imparesy positivos y definamos

s*ro: -z- ,s-r

t r - - - 2Se observa fci lmente e r: a-by s: al b. Por lo tanto,

z-A:@-b) ' , z lU:@+b)2de donde,

((" - b) '+ (a + b)2)

v-

2((a+b)2 - ("-b) ' )

: a2 +b2

:2ab

,:(o-b)("+b): a2-b2.Puesto que g > 0, ay b tienen el mismo signo y como s : &lb entonces a ybresul tanposi t ivos. Como r:a-b > 0entonces ) bycomo s:*besimpar entonces a y b tienen distinta paridad. Finalmente (a,b) :1 pues si pes un pr imo tal que pl ay p I b entonces pl r , plA, p I z lo que contrad. iceque (2, U, z) : l . n

usando el teorema podemos construir la siguiente tabla pequea de so-,luciones primitivas y positivas de la ecuacin 12 I y2 : 22.

234

4rd

trrJ

66

I2fI

32415

3

157

2II3511

A

L28242040L260

513T725294I3761

Las soluciones enteras y positivas de la ecuaci n 12 +A2 : 22 se conocen tam-bin con el nombre de Ternas Pi,tagri,cas en una clara alusin al conocid.oTeorema de Pitgoras.

2.8. ALGUNAS ECUACIONES DIOFNTICAS 61

Estudiemos ahora la ecuacin

x4 +a4: z2 (2.6)2-54 Teorema. Ly ecua-cin ,a + Aa : z2 no tiene solucin en el conjuntode los nmeros enteros d,i,ferentes d,e cero.

Demostrac'in. Es suficiente probar que no existen soluciones primitivas po_:-itir-as.

Como en el casodela ecuacin (2.5) con r : 2 se ve que si (r,A, r)es unasolucin primitiva de (2.6) entonces los enteros ru,z son primos rerativosdos a dos. supongamos entonces que (2, y,z) es u *l,r"ion primitiva talquez ) 0,a )0, z > 0yz es mnimoaAdems, s inperdergeneral idad,podemos suponer que ,r es impar y g es par. Escribiendo za + oZ:;; ;;i;forma(* ' ) '+ (a') ' :

"r ,por aplicacin del Teorema 2.58 tenemos:

fr2 : e,2 -b2, u2 :2ab, z : a2 +b2donde a> b> 0, ary de paridad opuesta y (a,b):1. Si fuese par y impar, el nmero tr2: o,2 -b2 sera de la forma +te _t:4,(k_ f l ig

"""h > 0. lo que es imposible. Luego a es impar y. es par.

Aplicando nuevamente er reorema 2.5J ara ecuacin x? +b2: 2 tene-mG que

, : u2 _ ,2, b:2uu, a: u2 + u2donde u >^o > 0, (u,u) : L con u y u dedistinta paridad. Como Uz : 2abentonces A2 : uu(u, +or).

Puesto que LL, a y (u2 + u2) son primos relativos dos a dos (prubero),::T:

cada uno de estos nmeros debe ser un cuadrado purfu"it; ,"" po,eJmpro

' tL:12,,n : s2, u2 +a2 : t2donde podemos asumir que r, s y son positivos. Adems tenemos (r, s,t) :l . f >1y

'n+s4:t2J como z : a2 Ib2 : t4 +b2 > 4, entonces z ) t.

62 CAPTULO2 DIVISIBILIDAD

De esta forma hemos encontrado una solucin primitiva y positiva de(2.6) a saber (r, s, ) donde t < z Io que contradice la minimalidad de z, conIo cual queda demostrado el teorema.

Una ligera variacin de la demostracin consiste en construir a partir deuna solucin primitiva y positiva de (2.6) una sucesin (rn,an, zr) de solu-ciones de dicha ecuacin donde la sucesin (zn) es estrictamente decreciente,Io cual es absurdo. Este procedimiento es denominado mtodo del descensoi,nfini,to y es debido a Fermat.

2.55 Corolario. La ecuac'in 14 + A4 : 24 no t'iene soluci,n en el conjuntode los enteros diferentes de cero.

Demostracin. Es suficiente observar que Ia ecuacin puede escribirse en laforma

14+a4:Q2)2y aplicar el,teorema.

n

n

Ejercicios 2.5

1. Probar que si r es una potencia de 2 mayor que 2, la ecuacin an+An :z' tto tiene solucin en el conjunto de los enteros diferentes de cero.

Encontrar todas las ternas pitagricas (r,A,r) tales que 1< z < 30.Probar que Ia conjetura de Fermat es cierta si y solo si para todo primoimpar p, Ia ecuacin rp * Ap : zp no tiene solucin en el conjunto delos enteros diferentes de cero.

Hallar todas las ternas pitagricas que estn en progresin aritmtica.

Probar que (3,4,5) es Ia nica terna pitagrica formada por enterosconsecutivos.

Hallar todas las ternas pitagricas que estn en progresin geomtrica.

Probar que no existen enteros diferentes de cero tales que ,n -An : "'

2.

3.

/1

5.

6.

7.

2.8. ALGUNAS ECUACIONES DIOFNTICAS 63

8. Proba,r que toda solucin primitiva (, , A ,, ,) de Ia ecuac in ra ya : 22es tal que fr,U,2 son primos relativos dos a dos.

9. Probar que el radio del circulo inscrito en un tringulo pitagrico essiempre un entero.Sugerenc'ia; Calcular el ea del trirngulo de dos formas diferentes.

cAPruLo 3

Fu nciones Aritmticas

3.1 La funcin parte entera

3.1- Definicin. Sea z un nmero real. Existe un nico entero que repre-sentamos por [z] que satisface la desigualdad

l r l

3.1, LA FUNCION PARTE ENTERA 65

e) Si, z : ix - lr] entonces 0 1 z 1 1.

f ) Si ,n es un entero y r :n lz con0l z 1I entonceslr l :n.g) Para todo entero n, lr I nl: lr] + n.h) l" l+ [s/] < l"+al < ["] + [s]+t.i)

j ) Si . a :bq]_r con0 ( r ( b "nton"",

lo llu) : q

k) Para tod,o entero positiuo n, ill : fl4lLnr ln )

Demostrac'in. a) Es consecuencia inmediata de la definicin.b) Sinz+1> z entonces m 1r lrly en consecuencia

m > lnl f 1 puesto que r y [r] son enteros.d) Ya que [r] ( z obtenemos [z] < a y por (b), l"l < lal.e) Es consecuencia inmediata de la definicin.f ) Como 012:r-n l l entonces n1r

66 CAPTULO 3. FUNCIONES ARITMTICAS

k) Si div idimos [z] porr obtenemos lx] :qn*r donde 0 ( r( n yporlotanto q : ll"1l"l. De otra parte r : [r] * z con 0 1 z < 1 y entonces* : (qn+ r) * z con 0 1 r * z < n. Por Io tanto (rfn) : q + (r + z)/ncon 0 ( (r + z)/n ( 1 y en consecuencia frln]: q. n

3.3 Ejemplo. Sea r un nmero real cualquiera. Veamos que [z + (L/2)] esel entero ms prximo a n.En efecto, sea n el entero ms prximo a rj donde escogemos el mayorcuando hay dos enteros igualmente prximos. Tenemos entonces n: :L + zcon -(r l2) 1 z 1 (Ll2). Luego r+(Ll2) : n+(r l2)-z con} < ( I l2)-z < |y por (f) del teorema anterior, lx + (Ll2)]: n.3.4 Ejemplo. Sean p y q enteros positivos,Veamos que,

impares y primos relativos.

p-Lq-r

"li"]*,p,li,]:t0(z(Observemos la figura,

y: E,

El nmero + + representa el nmero de puntos con coordenadas enterasen el interior del rectngulo. Sobre la diagonal no hay puntos de esta clase,pues si existieran r y y enteros tales que A : (pl* entonces qA: pir esdecir q lpr y como (q, p):7 entonces qlr lo que es imposible pues r < f i .

De otra parte, para cada eniero r el nmero de puntos en la regintriangular fi1 con primera coordenada r y coordenadas enteras es [f r]. Por

(* P*\

3.1 LA FUNCION PARTE ENTERA 67

lo tanto el nmero de puntos en con coordenadas enteras es

Similarmente, el nmero de puntos con coordenadas enteras en Ia regin R2ES

o


Podemos entonces escribir la siguiente frmula notable para la representa-cin cannica de n!

nt :lIoD-r' l]p

donde p vara sobre todos Ios nmeros primos.

3.6 Ejemplo. El exponente con el cual apareceT en Ia factorizacin cannicade 500! es

l500l7l+ [500/4e] + [500/343] : 7t+ 10 + | : 82.El exponente con el cual 3 aparece en la representacin cannica de 500! es

[500/3] + [500/e] +15001271+ [500/81] +150012431:166+55+18+612:247.

De lo anterior podemos deducir que la mayor potencia de 21 que divide a500! es min(82,247) :32.Cuando los nmeros son grandes la propiedad (k) del Teorema 3.2 permitesimplificar los clculos, ya que con base en ella tenemos

3.7 Ejemplo. Veamosquesi at laz+.. '+ ar:rL donde a)0 entoncesel coeficiente multinomial

aLla2layl . . .ar !

es entero.

Es suficiente probar que todo primo p aparece en el denominador con unexponente menor que aquel con el cual aparece en el numerador.

EI exponente con que p aparece en el numerador es

@Tl

r t3 lf i lnr )

nl

3,]. . LA FUNCIN PARTE ENTERA

El exponente con que p aparece en el denominad.or es

a i , ' l *$ ior l ,_. . .+$ Io ' l?{i,-.'it. .i11'A\LFJ- LFI Lp*r)= i l@t + oz+ "' + o') l : S fr lf rL pk - l - kL l

donde la desigualdad se tiene por la parte h) del reorema 8.2. De esta formaqueda probada nuestra afirmacin.

Ejercicios 3.1

1' sean n y a enteros positivos. probBr q,ru f3] es el nmero de enterosde la sucesin I,2,. .. , n que son divisibles por .2' Sea r un nmero real que no es punto medio de dos enteros probarque

-[-z + ]] es el entero mrs proxim o a r.3. Sean n,y ntimeros reales positivos. probar qr." kl[y] l[rA].4. Hallar todos los nmeros reales que satisfacen:

(") bl + [r]: [zr](b) [" + i] + t" _ +l: [2n].5. Probar que para todo nmero real r, [r] + t, + trl: [2r].Sugerenc, ia: Escr ib i r , : [* ]*z y considerar 0 { z 1LV i Sz


7. Probar que para todo nmero real r j y pata todo entero positivo k,lrl + fr+ *l + l" + 1l+ . . . + " + #l : fkrl.

8' cul es el exponente de 5 en la representacin cannica de 83b!?Cul el de 15?

9. Con cuntos ceros termina la expansin decimal de 120!?

10. Con cuntos ceros termina el desarrollo en base 3 de 100!?Sugerenc'ia; Escribir 100! : 3-b donde (b,3) : 1 y luego expresar b

en la forma b : 3kf r con r : 1 o r :2.

11. probar o* st f?1)' u0/

12. Si ?z es un entero positivo, probar q"" ffi es un nmero par.

13. Para todo entero positivo n, probar que n!(n - 1)! divide a (Zn- Zt14. Sea n : po donde p es primo y un entero positivo. Probar que:

n | (n- 1)! si y solamente si p es impar y a > I, , p - 2 y a > 2.

3.2 Las funciones nmero y suma de divisores

Las funciones que tienen como dominio el conjunto de los enteros positivoscon valores en C se denominan func'iones ari,tmti,cas o func'iones numr,icas.En esta seccin estudiaremos dos de ellas muy conocidas.

Si n es un entero positivo definimos las funciones r(n) y o(n) as:

o r(n) es el nmero de divisores positivos de n.o o(n) es la suma de los divisores positivos de n.

Por ejemplo, r (1) : o(1) :1, r (10) - 4y o(fO) : L+2+ 5* 10:18.Como consecuencia del reorema Fundamental de la Aritmtica obtene-

mos los resultados siguientes.

3.2. LAS FUNCIONES NUMERO Y SUMA DE DIVISORES 71

3.8 Teorema. Si n : fIf:tfrn donde n-) 0 para cada i, es la representa-ci,n canni,ca de un entero positi,uo n, entonces

k te ^n+l 1r(n): f[(", + r; a o(n):I7"#

i : t i : l

Demostracin. Por el Teorema 2.43, d es un divisor positivo de n, si y soloSi, d : l l f : rp! 'donde 0 < d 1n para cad,a i , :1,2, . . . ,k. Por el pr in-cipio fundamental de conteo, podemos construir eiactamente (rr + l)(n, +1) ' ' ' (nn + 1) de tales divisores. Es decir

kt--f ,r (n): l l (u + t 'i :T

De otra pa,rte, si observamos que cada divisor positivo de n aparece una ysolamente :ur;.a vez como sumando en el producto

(1 +pr + p? + . . . + pT') . . ' (1 + pn * p?, + . . . + p?o)concluimos que

ko(n) :f l f t + p + p? + ... + pT),

i : l

y puesto que

r , -po+p?+..-+pT' : f f i ,tenemos tambin que

k ^ntI _ I

o(n\: f I Pi Lt P-L

En el teorema anterior si p es un nmero primo tenemos,

r (p):1+1:2 y o(p):1* e:e#Mis generalmente, si p es primo y es un entero positivo tenemos,

'

'a I7 -1

r(p") : a I r y o(p") : 1 * p * p * " ' I p" p- r


3.9 Ejemplo. Encontremos el menor entero positivo que tiene 21 divisorespositivos.

Como 2l : 3 x 7, el nmero buscado tiene la forma p2q6 con p y qprimos diferentes, o la forma p2o con p primo. Los nmeros mis pequeosque tienen estas formas son:

22 x36:29L6

32 x26:57622o : L048576

Por lo tanto 576 es el nmero buscado.s

Busquemos una frmula para el producto de los divisores positivos deun entero positivo n.

Supongamos que los divisores positivos de r son

dt,dz, . . . ,dr(n)

y su producto esP : d, i ,2. . .d"@). (3.1)

Como los divisores positivos de n son tambin

nnn

' dr ' " ' ' @) (3 '2)

de (3.1) y (3.2) obtenemosP2 - n"@) '

Luego el producto buscado es P: n9

3.10 Definicin. Una funcin aritmtica se llama multiplicatiu si satisfacela condicin:

f (*") : f (m)f (n), para todo m,n enteros positivos tales que (m,n) :1.

Si f (rnn): f (m)f (n) para todom,r enteros positivos, entonces / se Ilamaco mp I et am ent e multip li m,tiu a.

3.L1- Teorerna. Las funciones r A o son multiplicatiaas.

3.2. LAS FUNCIONES NMERO Y SUMA DE DIVISORES 73

Demostraci,n. Supongamos que rrl y n son enteros positivos y primos rela-;ivm. Podemos escribir

T-T n, fT rn;n: I Ip;"" y m: I Ie "i : l j :7

donde los p y los q son primos distintos.

Tenemos,

rkr(mn):f l@i + t) . f l (rzi + 1) : r(m)r(n)

; -1 ; -1

i-, nTi*r_1 k p?o+r_l

o(mn) : l l } - ' i . f I 'o_. ^ : o(m)o(n);J qi -L ;J Pi-r

como queramos probar. fl

\iiguna de estas funciones es completamente multiplicativq, por ejem-plo.

3: r(4) I r (z)r(2) : (2)(2) :4,7 : o(4) I o(z)o(2): (3)(3) : e.

Como ejemplos de funciones completamente multiplicativas podemos citar,a-. definidas por la ecuacin f (r) : nk con k fijo.

Ejercicios 3.2

1- Hallar el nmero de divisores positivos de 4320 y calcular su suma.

2- Probar que si r(n) :2, entonces 7 es un nmero primo.3- Halla el menor entero positivo con 15 divisores positivos.


Hallar el menor entero positivo con 24 divisores positivos.

Si n es un entero positivo mayor que 1, probar que la ecuacin r(r) : 2tiene infinitas soluciones.

6. Si r y n son enteros positivos tales que (^,n) ) 1, probar quer(mn) < r(m)r(n).Resolver la ecuacin o(n) :36.Sugerencia.' Descomponer 36 en factores que se puedan expresar en laforma l+p-lp2 *' ' '-fpk con p primo y usar una frmula conveniente.

Hallar dos enteros positivos ?? que cumplan Ia condicin o(n) :2n.Si n es un entero positivo probar que la ecuacin o(r) : n tiene unnmero finito de soluciones.

Probar que el nmero de divisores positivos de un entero positivo n esimpar si y solo si n es un cuadrado perfecto.

Si rr: lIl:tpT'es la representacin cannica de un entero posi

teoría de números

Documents