[para principiantes] - UIS

1 GUSTAVO RUBIANO Teor a de n umeros [para principiantes] GUSTAVO RUBIANO GUSTAVO RUBIANO Teor a de n umeros [para principiantes] Luis R. Jim enez E. Gordillo N. Rubiano Nacional de ColombiaFacultad de CienciasSede Bogot aGUSTAVO RUBIANO vi, 284 p. : 3 Teor a de n umerosLuis R. Jim enez B.,Jorge E. Gordillo A.,Gustavo N. Rubiano a de n umeros [para principiantes], 2a. edici Nacional de Colombia, Sede Bogot de Ciencias, 2004 Mathematics Subject Classification 2000: Edici on en castellano: Luis R. Jim enez B., Jorge E. Gordillo A.,Gustavo N. Rubiano Nacional de impresi on, 2004 Impresi on:Pro Offset Editorial a, D. RUBIANO Indice GeneralPr ologoix1 N umeros Axiomas de Peano .. Adici on de n umeros naturales .. Multiplicaci on de n umeros naturales .. Orden entre n umeros naturales .. Construcci on de los n umeros enteros .. Formas equivalentes al principio de inducci onmatem atica.

2 132 Propiedades b asicas .. M aximo Com un DivisorMCD.. 27vGUSTAVO RUBIANO vi INDICE Algoritmo de Euclides .. Propiedades del M aximo Com un Divisor .. M nimo Com un M ultiplo y generalizaciones .. Teorema fundamental de la aritm etica .. Algunas propiedades de los n umeros primos .. Algunas ecuaciones diof anticas .. 583 Funciones Aritm La funci on parte entera .. Las funciones n umero y suma de divisores .. N umeros perfectos, de Mersenne y de Fermat .. La funci on de Euler .. Funciones multiplicativas .. La f ormula de inversi on de M obius .. 904 Definici on y propiedades b asicas .. Criterios de Divisibilidad .. Aritm etica m odulon.. Los Teoremas de Euler y Fermat .. Congruencias lineales .. Ecuaciones Diof anticas lineales .. Sistemas de congruencias lineales .. El Teorema chino del residuo .. 131 GUSTAVO RUBIANO INDICE Congruencias de grado superior.

3 Congruencias con m odulo una potencia de un primo .. Teoremas de Lagrange y Wilson .. 1475 Residuos cuadr Congruencias de segundo grado con m odulo primo .. Ley de la reciprocidad cuadr atica .. El s mbolo de Jacobi .. Potencias m odulony ra ces primitivas .. Algebra y teor a de n umeros .. 1806 Criptograf Nociones b asicas .. Cifrados monogr aficos .. Cifrado en Bloques .. Cifrados Exponenciales .. Algoritmo para calcularPem .. Sistemas de Clave P ublica .. Sistema RSA .. Sistema de Rabin .. Sistema de la mochila .. 2257 Fracciones Fracciones continuas finitas .. Convergentes .. 235 GUSTAVO RUBIANO viii INDICE Fracciones continuas infinitas .. Fracciones continuas peri odicas .. Aproximaci on de n umeros irracionales ..253N umeros primos menores que y sugerencias262 Bibliograf a280 GUSTAVO RUBIANO Pr ologoLa segunda edici on de este libro mantiene el mismo esp ritu conque fueconcebida la primera; es decir, se trata de un texto b asico de iniciaci on alestudio de la Teor a de N umeros.

4 La principal caracter stica de esta nuevaedici on es la adici on de un cap tulo sobre Criptograf a, que muestra una delas principales aplicaciones de la teor a en se ha hecho una revisi on cuidadosa de los temas tratados yde las correspondientes secciones de ejercicios, se han adicionado algunassecciones y se ha actualizado la bibliograf a. Esperamos que estos cambioshagan el material m as util y atractivo para los queremos expresar nuestra gratitud a todas las personas queleyeron la primera edici on, y nos hicieron llegar sus valiosos comentarios ysugerencias que tuvimos en cuenta para la preparaci on de lapresente edici especial, manifestamos nuestro agradecimiento a los profesores Paz Mo-rillo (E UPB TL; Barcelona) porMathematical Reviews[MR 2000j:11001],y Gabriel D. Villa Salvador (Cinvestav, M exico D. F.) porZentralblatt[ ] quienes gentilmente evaluaron la edici on original y nos motivaronpara realizar esta nueva versi RUBIANO x INDICE GENERALPr ologo a la primera edici onEn la formaci on de toda persona que se dedique a la ense nanza o al estudiode las matem aticas, o cualquier nivel, no puede faltar un curso de Teor ade n umeros.

5 Esta hermosa teor a, ha sido llamada por K. F. Gauss, lareina de las matem aticas. La simplicidad de su objeto, la elegancia y ladiversidad de sus m etodos, la formulaci on sencilla de numerosos problemasno resueltos, hacen de esta disciplina una de las areas m asfascinantes deluniverso matem este libro se ofrece una introducci on breve y eficiente delos temas,que a nuestro modo de ver son fundamentales para iniciarse enel estudiode esta teor a. A lo largo de sus cap tulos estudiamos detalladamente lossiguientes t opicos: n umeros naturales y enteros, divisibilidad y n umerosprimos, funciones num ericas, congruencias y fracciones el estudio de todos los temas, presentamos numerosos ejemplos y pro-ponemos una buena cantidad de ejercicios, la mayor a de ellos con respuestaso sugerencias, que permiten al estudiante avanzar con mayorseguridad enla asimilaci on de los este libro, creemos llenar la necesidad de un texto claro, sencillo yecon omico, dirigido principalmente a los estudiantes de las carreras y licen-ciaturas de matem aticas ofrecidas por nuestras Rafael Jim enez BecerraJorge Enrique Gordillo ArdilaGustavo Nevardo Rubiano Orteg onDepartamento de Matem aticasUniversidad Nacional de ColombiaCiudad Universitaria, Bogot a, de 2004 GUSTAVO RUBIANO CAP ITULO1N umeros Axiomas de PeanoEl conjunto de los n umeros naturales se puede caracterizarmediante lossiguientes axiomas, introducidos por el matem atico italiano Giuseppe Peanoen 1899.

6 A-1 Hay un elemento especial 0 todon Nexiste un unico elementon+ Nllamado el todon N, n+6= , m Nyn+=m+entoncesn= un subconjunto deNtal que:1. 0 S, + Ssiempre quen S, entoncesS= RUBIANO 2 CAP ITULO 1. N UMEROS NATURALESEn la formulaci on de los axiomas de Peano se supone de antemano laexistencia del conjuntoN. El axiomaA-3establece la existencia de un pri-mer n umero natural que es 0. El axiomaA-4indica que n umeros naturalesdiferentes tienen sucesores axiomaA-5se conoce comoEl Principio de Inducci on Matem atica abreviadamente,PIM . En las aplicaciones de este principio la hip otesisn S, a partir de la cual se demuestra quen+ S, se denominaHip otesisde Inducci Adici on de n umeros Definici siguientes ecuaciones definen la adici on enN. Paratodom, n N:m+ 0 =m,m+n+= (m+n)+.Como todo n umero natural distinto de cero es el sucesor de unn umeronatural la adici on resulta bien adici on de n umeros naturales es asociativa, es decir:Para todon, m, k N(n+m) +k=n+ (m+k).

7 Demostraci el axiomaA-5 PIM .SeaS={k N|(n+m) +k=n+ (m+k) para todon, m N}.1. 0 Spuesto que(n+m) + 0 =n+m=n+ (m+ 0)(def. suma)2. Supongamos quek S, es decir que para todon, m N(n+m) +k=n+ (m+k).GUSTAVO RUBIANO ADICI ON DE N UMEROS NATURALES3 Entonces,(n+m) +k+= [(n+m) +k]+(def. suma)= [n+ (m+k)]+(hip. inducci on)=n+ (m+k)+(def. suma)=n+ (m+k+)(def. suma)luegok+ Sy porA-5,S= demostrar la conmutatividad, probamos todom N,0 +m= {m N|0 +m=m}.1. 0 S, puesto que 0 + 0 = 0 por definici on de Supongamos quem S, es decir, que 0 +m=m. Entonces:0 +m+= (0 +m)+(def. suma)=m+(hip. inducci on)Luegom+ Sy, porA-5,S= todom, n N,m++n= (m+n)+.Demostraci {n N|m++n= (m+n)+para todom N}.1. 0 S, puesto que para todom Nm++ 0 =m+(def. suma)= (m+ 0)+(def. suma)2. Supongamos quen S, es decir, que para todom Nm++n= (m+n)+.GUSTAVO RUBIANO 4 CAP ITULO 1. N UMEROS NATURALESE ntonces para todom N, tenemosm++n+= (m++n)+(def. suma)= [(m+n)+]+(hip. inducci on)= (m+n+)+(def.)

8 Suma)As ,n+ Sy, porA-5,S= adici on de n umeros naturales es conmutativa: para todom, n N,m+n=n+ {n N|m+n=n+mpara todom N}.1. 0 S, puesto quem+ 0 =m= 0 + Supongamos quen S. Entonces, para todom N,m+n+= (m+n)+(def. suma)= (n+m)+(hip. inducci on)=n++m(Lema ).As ,n+ Sy, porA-5,S= , mykson n umeros naturales tales quem+k=n+k,entoncesm= {k N|sim+k=n+kentoncesm=npara todom, n N}.1. 0 S, pues sinymson naturales tales quem+ 0 =n+ 0 pordefinici on de suma concluimos quem= Supongamos quek Sy seann, m Ntales quem+k+=n+k+.GUSTAVO RUBIANO MULTIPLICACI ON DE N UMEROS NATURALES5 Entonces,(m+k)+= (n+k)+(def. suma)luego, porA-4,m+k=n+ky, por la hip otesis de inducci on,m= ,k+ SyS=N, Multiplicaci on de n umeros naturalesLas siguientes ecuaciones definen la multiplicaci on enN. Para todom, n N,m0 = 0,mn+=mn+ todo n umero natural distinto de cero es el sucesor de otro n umeronatural, la operaci on resulta bien multiplicaci on es distributiva con respecto a la adici on,es decir: para todom, n, k N, m(n+k) =mn+ {k N|m(n+k) =mn+mkpara todom, n N}.

9 1. 0 S. En efecto,m(n+ 0) =mn(def. suma)=mn+ 0(def. suma)=mn+m0(def. multiplicaci on).2. Supongamos quek todom, n N, tenemosm(n+k+) =m(n+k)+(def. suma)=m(n+k) +m(def. multiplicaci on)= (mn+mk) +m(hip. inducci on)=mn+ (mk+m)(Teorema )=mn+mk+(def. multiplicaci on)GUSTAVO RUBIANO 6 CAP ITULO 1. N UMEROS NATURALESAs ,k+ Sy, porA-5,S= multiplicaci on de n umeros naturales es asociativa: paratodon, m, k N(mn)k=m(nk).Demostraci {k N(mn)k=m(nk) para todon, m N}1. 0 S. En efecto, la definici on de multiplicaci on nos permite afirmarque(mn)0 = 0 y tambi en quem(n0) =m0 = 02. Supongamos quek S. Para todom, n Ntenemos:(mn)k+= (mn)k+mn(def. multiplicaci on)=m(nk) +mn(hip. inducci on)=m(nk+n)(Teorema )=m(nk+)(def. multiplicaci on);luegok+ Sy, porA-5,S= multiplicaci on de n umeros naturales es conmutativa. Esdecir: Para todom, n N, mn= demostrar el Teorema es necesario probar antes los lemas todom N, tenemos0m= todom, n N, tenemosm+n=mn+ la demostraci on de los Lemas , como la del Teorema lasdejamos como ejercicio al RUBIANO ORDEN ENTRE N UMEROS NATURALES7 Ejercicios Demostrar que todo n umero natural diferente de cero es dela forman+para alg unn Demostrar que para todon N, n+=n+ 0+.

10 3. Simynson n umeros naturales tales quem+n= 0, probar quem= 0yn= Demostrar que sim, n Nentoncesm+n Nymn Probar que sin, m Nson tales quemn= 0 entoncesm= 0, on= Demostrar los lemas y y el Teorema Orden entre n umeros Definici , n Ndecimos que:m nsi existep Ntal quen=m+ que la relaci on define un orden sobreN. En efecto,1. La relaci on es todom N, m mpuesto quem=m+ 0 con 0 La relaci on es antisim , mson n umeros naturales tales quem nyn m, entoncesexistenp, q Ntales quen=m+pym=n+q. Luego,m=(m+p) +q=m+ (p+q). Por lo tanto,p+q= 0 y, en consecuencia,p=q= 0, lo que implicam= La relaci on es , n, r Nson tales quem nyn r, entoncesn=m+pyr=n+qdondep, q N, y por lo tantor= (m+p) +q=m+ (p+q)dondep+q N, luegom RUBIANO 8 CAP ITULO 1. N UMEROS NATURALESComo es usual, definimosm < nsim nym6=n. Podemos observarcomo consecuencia de la definici on quem < nsi y solo sin=m+p+paraalg unp Teorema (Ley de la tricotom a).Dadosm, n Nuna y solo unade las siguientes afirmaciones es verdadera,m < n, m=n, n < demostraci on requiere la prueba del lema , n Ntodas las afirmaciones siguientes son < nym= < myn= < nyn < tuvi eramos simult aneamentem < nym=n, tendr amosn=m+p+, dondep Nym=n, lo que implicar a quep+= 0.