Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
Róbinson Castro Puche moderna Álgebra e introducción al álgebra geométrica ECOE EDICIONES Róbinson Castro Puche. Licenciado en Matemáticas, Universidad Nacional de Colombia, Bogotá. Master of Arts Mathematics Education, Ball State University, Muncie, Indiana, USA. Profesor titular de la Universidad de Córdoba, Montería, donde además ejerció las funciones de Secretario Académico de la Facultad de Ciencias, Director del departamento de Matemáticas y Director de la oficina de Registro y Admisiones. Es además, docente adscrito a la Universidad Nacional de Colombia, 1993 a 1994. A´LGEBRA MODERNA e introduccio´n al a´lgebra geome´trica RO´BINSON CASTRO PUCHE A´lgebra moderna e introduccio´n al a´lgebra geome´trica Copyright c© Ro´binson Castro Puche. Es propiedad intelectual del autor. Todos los derechos reservados. Prohibida la reproduccio´n total o parcial, por cualquier medio o con cualquier propo´sito, sin autorizacio´n escrita del autor. Monter´ıa – Colombia robinson castro p@hotmail.com ISBN: 978-958-648-850-1 Primera edicio´n: 2013 Diagramacio´n: En LATEX realizada por Ro´binson Castro Puche Disen˜o de Cara´tula: Wilson Marulanda Impreso por Ecoe Ediciones Ltda., Bogota´ E-mail: correo@ecoeedicioes.com www.ecoeedicioes.com Carrera 19 No 63C-32, Pbx: 2481449, fax. 346 1741 Coordinacio´n editorial: Andrea del Pilar Sierra Impreso en Colombia Depo´sito legal: Hecho. Catalogación en la publicación – Biblioteca Nacional de Colombia Castro Puche, Róbinson Álgebra moderna e introducción al álgebra geométrica / Róbinson Castro Puche – 1ª. ed. – Bogotá : Ecoe Ediciones, 2013 ��� p. – (Ciencias exactas. Matemáticas) ISBN 978-958-648-850-1 1. Aritmética 2. Álgebra 3. Geometría algebraica I. Título II. Serie CDD: 512 ed. 20� CO-BoBN– a834338 A Olga, la esposa; Milton, Tania, Jaime y Glenna, los hijos; Alejandro, Andrea, Paula, Valery, Daniel y Sara, los nietos. I´ndice general EL AUTOR V PRESENTACIO´N VII PREFACIO IX 1. TEORI´A DE LA ARITME´TICA 3 Introduccio´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2. El m.c.d y el m.c.m . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3. Congruencias . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.4. Criterios de divisibilidad . . . . . . . . . . . . . . . . . . . . . 36 1.5. Sistemas de numeracio´n . . . . . . . . . . . . . . . . . . . . . 42 1.5.1. Cambio de bases . . . . . . . . . . . . . . . . . . . . . 43 1.5.2. Operaciones en base cualquiera . . . . . . . . . . . . . 45 2. GRUPOS 53 2.1. Leyes de composicio´n internas . . . . . . . . . . . . . . . . . . 53 2.2. Grupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.3. Grupos finitos y construccio´n de tablas . . . . . . . . . . . . . 61 2.4. Notacio´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.5. Grupos de permutaciones . . . . . . . . . . . . . . . . . . . . . 72 2.6. Subgrupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 2.7. Grupos C´ıclicos . . . . . . . . . . . . . . . . . . . . . . . . . . 85 2.8. Aplicaciones geome´tricas . . . . . . . . . . . . . . . . . . . . . 94 3. SUBGRUPOS NORMALES–ISOMORFISMOS 101 3.1. Grupos con operadores externos . . . . . . . . . . . . . . . . . 101 i ii I´NDICE GENERAL 3.2. Producto de las partes de G . . . . . . . . . . . . . . . . . . . 106 3.3. Δ–Subgrupos . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 3.4. Clases laterales . . . . . . . . . . . . . . . . . . . . . . . . . . 108 3.5. Subgrupos normales . . . . . . . . . . . . . . . . . . . . . . . 119 3.6. Homomorfismos . . . . . . . . . . . . . . . . . . . . . . . . . . 129 3.7. Isomorfismos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 4. ANILLOS 141 4.1. Definicio´n y Ejemplos . . . . . . . . . . . . . . . . . . . . . . . 141 4.2. El Anillo Zn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 4.3. El anillo de los Endomorfismos de A . . . . . . . . . . . . . . 147 4.4. Divisores de Cero . . . . . . . . . . . . . . . . . . . . . . . . . 153 4.5. Dominios–Semicampos–Campos . . . . . . . . . . . . . . . . . 154 4.5.1. Subdominios–Subcampos . . . . . . . . . . . . . . . . . 156 4.6. Ideales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 4.7. Homomorfismos . . . . . . . . . . . . . . . . . . . . . . . . . . 163 4.8. Otras clases de ideales . . . . . . . . . . . . . . . . . . . . . . 173 4.9. Dominios Euclidianos . . . . . . . . . . . . . . . . . . . . . . . 176 4.10. Divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 4.11. Dominios de factorizacio´n u´nica . . . . . . . . . . . . . . . . . 184 4.12. El campo de cocientes de un dominio . . . . . . . . . . . . . . 185 4.13. Caracter´ısticas de Dominios y Campos . . . . . . . . . . . . . 192 5. ANILLOS DE POLINOMIOS 199 5.1. Construccio´n del anillo F [ x ] . . . . . . . . . . . . . . . . . . . 199 5.2. Polinomios Irreducibles . . . . . . . . . . . . . . . . . . . . . . 211 5.3. Extensiones de Campos . . . . . . . . . . . . . . . . . . . . . . 215 5.4. Los ceros de Polinomios . . . . . . . . . . . . . . . . . . . . . 218 5.5. El Dominio de Factorizacion Unica D[ x ] . . . . . . . . . . . . 230 6. A´LGEBRA GEOME´TRICA 239 6.1. A´lgebras de Clifford . . . . . . . . . . . . . . . . . . . . . . . . 239 6.1.1. Bases y dimensio´n . . . . . . . . . . . . . . . . . . . . 240 6.1.2. El producto exterior . . . . . . . . . . . . . . . . . . . 244 6.1.3. El producto de Clifford . . . . . . . . . . . . . . . . . . 246 6.2. A´lgebras del plano y el espacio . . . . . . . . . . . . . . . . . . 247 6.2.1. El a´lgebra tridimensional . . . . . . . . . . . . . . . . . 249 6.2.2. Trivectores . . . . . . . . . . . . . . . . . . . . . . . . . 256 I´NDICE GENERAL iii 6.3. El a´lgebra Cln . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 6.3.1. Bases algebraicas . . . . . . . . . . . . . . . . . . . . . 259 6.4. La transformacio´n dual . . . . . . . . . . . . . . . . . . . . . . 264 6.4.1. Propiedades generales . . . . . . . . . . . . . . . . . . 266 6.4.2. Involuciones . . . . . . . . . . . . . . . . . . . . . . . . 268 6.5. Los productos interno y externo . . . . . . . . . . . . . . . . . 271 6.6. Multivectores de grado k . . . . . . . . . . . . . . . . . . . . . 278 6.7. La norma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 6.7.1. El inverso de A〈k〉 . . . . . . . . . . . . . . . . . . . . . 287 6.8. Representacio´n matricial del producto . . . . . . . . . . . . . . 288 6.9. El inverso de un multivector . . . . . . . . . . . . . . . . . . . 293 6.9.1. El producto geome´trico en Cl3 . . . . . . . . . . . . . . 294 6.10. Versores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 6.11. El plano euclidiano . . . . . . . . . . . . . . . . . . . . . . . . 299 6.11.1. Interpretacio´n geome´trica de los bivectores en el plano euclidiano . . . . . . . . . . . . . . . . . . . . . . . . . 300 6.11.2. El i-plano espinor . . . . . . . . . . . . . . . . . . . . . 301 EL AUTOR RO´BINSON CASTRO PUCHE Licenciado en Matema´ticas, Universidad Nacional de Colombia, Bogota´. Master of Arts Mathematics Education, Ball State University, Muncie, In- diana, USA. En la Universidad de Co´rdoba, en Monter´ıa, ejercio´ las funciones de secreta- rio acade´mico de la Facultad de Ciencias, director de la Oficina de Registro y Admisiones, director del Departamento de Matema´ticas y profesor titular. Tambie´n fue rector del Colegio El Carmen de Cotorra, Co´rdoba y entre di- ciembre de 1993 y noviembre de 1994, fue docente adscrito a la Universidad Nacional de Colombia. v PRESENTACIO´N A´lgebra moderna e introduccio´n al a´lgebrageome´trica es un texto cuyo objetivo es promover una actitud matema´tica positiva entre los estu- diantes de una asignatura reconocida tradicionalmente como una disciplina abstracta, en la que se estudian entes aparentemente distantes de la realidad concreta y de la experiencia tangible. ¿Que´ se persigue con la ensen˜anza del a´lgebra moderna en las instituciones de educacio´n superior? Ciertamente no es hacer conocer al futuro matema´tico una serie de teoremas y ejercicios ingeniosos relacionados con las estructuras algebraicas, sino ensen˜arle a ordenar el pensamiento con arreglo al me´todo axioma´tico, para desarrollar el rigor del juicio lo´gico, indispensable en la labor del matema´tico. En ese aspecto, el autor presenta un trabajo prolijo que sera´ de gran ayu- da a los estudiantes que se inician en el conocimiento del a´lgebra moderna. El texto esta´ agradablemente redactado y en algunos aspectos presenta ori- ginalidad en la exposicio´n y concatenacio´n lo´gica de los temas, cosa dif´ıcil de lograr con un material que hoy es completamente esta´ndar. De acuerdo con mi criterio, esto u´ltimo representa un aspecto muy valioso del libro. Conociendo las cualidades pedago´gicas del profesor Ro´binson Castro, veo en la presente obra la continuacio´n de su conviccio´n de poner en pra´ctica las teor´ıas de la ensen˜anza de las matema´ticas desarrolladas por Piaget; por esta razo´n puedo afirmar que estamos, sin duda, frente a un material valioso para los interesados en conocer de cerca los fundamentos del a´lgebra moderna. RAFAEL OBREGO´N, Msc. Los A´ngeles, California, USA. enero de 2013. vii PREFACIO Si nos ubicamos en la posicio´n del maestro, de ensen˜ar la teor´ıa o en la del epistemo´logo, que tiene que ver con la naturaleza de los entes matema´ticos; el problema consiste en saber si las conexiones matema´ticas son engendradas por la inteligencia o si esta las descubre como una relidad exterior. Jean Piaget en su disertacio´n, con motivo del Coloquio de la Rochette de Melun en 1952, refirie´ndose a las estructuras matema´ticas; expreso´: Un grupo es un sistema operatorio; la cuestio´n estriba en saber si los elementos de diversa naturaleza a los que se aplica la estructura existen previamente a esta, o si, por el contrario, es la accio´n de la estructura la que confiere a los elementos sus propiedades esenciales. El problema sicolo´gico consiste en establecer si los entes que sirven de elementos a las estructuras son el resultado de las operaciones que los engendran o si preexisten a aquellas operaciones que se aplican a ellos. Para dar respuesta al dilema, continuo´ diciendo: En vez de definir los elementos aisladamente por convenio, la definicio´n estructural consiste en carcterizarlos por las relaciones operatorias que mantienen entre s´ı, en fun- cio´n del sistema. Y la definicio´n estructural de un elemento hara´ las veces de demostracio´n de la necesidad de este elemento, en cuanto esta´ concebido como perteneciente a un sistema cuyas partes son interdependientes. Teniendo en cuenta el criterio de Piaget, el objetivo principal de este trabajo es poner a la consideracio´n de la comunidad matema´tica un texto que proporcione a los estudiantes las bases teo´ricas del a´lgebra moderna que les permita abordar con e´xito una disciplina con un alto grado de abstraccio´n. Dominar las ideas expuestas en el texto constituye un paso fundamental para el estudio de teor´ıas ma´s avanzadas relacionadas con el desarrollo axioma´tico de las matema´ticas. En concordancia con lo anterior, el texto esta´ disen˜ado para usarlo co- mo guia para un primer curso de a´lgebra moderna. Se encuentra dividido ix x PREFACIO en seis cap´ıtulos. En el primero se estudian los aspectos ma´s relevantes de la aritme´tica elemental, comenzando con la caracterizacio´n de los nu´meros naturales tomando como fundamento los postulados de Peano. A partir del concepto de divisibilidad se estudian las congruencias, concluyendo con una presentacio´n suscinta de los sistemas de numercio´n de base diferente a la decimal. Los cap´ıtulos segundo y tercero esta´n dedicados al desarrollo de los gru- pos. El material consignado es el que tradicionalmente se estudia, pero he considerado que desde el punto de vista dida´ctico los subgrupos normales se introduzcan a trave´s de los automorfismos internos. Los cap´ıtulos cuarto y quinto esta´n dedicados a los anillos. El cuarto se inicia con una descripcio´n detallado de los enteros mo´dulo n, se extiende el estudio de la divisibilidad a los anillos en general y se desarrolla la teor´ıa correspondiente a las estructuras algebraicas hasta la nocio´n de campo. El quinto correponde al anillo de los polinomios. El a´lgebra geome´trica es un to´pico que en la actualidad no cuenta con una amplia difusio´n como herramienta matema´tica aplicada a la solucio´n de algunos problemas de la ingenier´ıa; donde el ana´lisis vectorial esta´ndar, en dos y tres dimensiones, y el a´lgebra matricial son las ayudas ampliamente usadas. Pero lo cierto es que cada d´ıa aumenta el nu´mero de investigadores convencidos de la utilidad de esta rama descubierta por Gu¨nther Grassmann. Presentar las bases mı´nimas de esta teor´ıa, tiene como propo´sito invitar a los interesados a profundizar en su estudio e investigar acerca de la im- portancia de esta herrmienta en la reformulacio´n de algunos conceptos de la f´ısica. El autor. Monter´ıa, enero de 2013. A´LGEBRA MODERNA e introduccio´n al a´lgebra geome´trica Cap´ıtulo 1 TEORI´A DE LA ARITME´TICA Introduccio´n El punto de partida es aceptar que los enteros y sus operaciones aritme´ticas han sido objeto de ana´lisis. El intere´s primario sera´ estudiar los fundamentos de la aritme´tica elemental. Se supone conocido el desarrollo axioma´tico de los naturales propuesto por G. Peano en 1889 que permite concebirlos como la coleccio´n {0, 1, 2, . . . , n, . . . } y una operacio´n unaria, la funcio´n siguiente o sucesor que verifica los postulados de Peano: 1. Cero es un nu´mero. 2. El sucesor de un nu´mero es u´nico. 3. Cero no es el sucesor de ningu´n nu´mero. 4. Si Sig(n) = Sig(m), entonces n = m. 5. El principio de induccio´n completa: Dado un conjunto M de nu´meros naturales con las dos propiedades siguientes: a) Cero pertenece a M. b) Si n pertenece a M implica que Sig(n) tambie´n pertenece a M ; entonces M contiene a todos los nu´meros naturales. 3 4 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA Partiendo de estos fundamentos se define la adicio´n mediante las fo´rmulas: Sig(n) = n + 1 Sig[Sig(n)] = n + 2 y as´ı sucesivamente, n + Sig(m) = Sig(n + m) llamadas fo´rmulas de recurrencia. La multiplicacio´n se expresa en te´rminos de la adicio´n por: nm = m + m + · · ·+ m︸ ︷︷ ︸ n veces indicando que el nu´mero m se ha sumado n veces. Los enteros sera´n el resultado de reunir los naturales con sus respectivos inversos aditivos, o sea: {. . . ,−3,−2,−1, 0, 1, 2, 3, . . .}. Ma´s tarde se estudiara´n como ejemplos de sistemas nume´ricos espec´ıficos objeto del a´lgebra moderna. La representacio´n polino´mica de los enteros sera´ igualmente asumida, da´ndose por cierto que para todo entero t > 1, cada uno de los enteros a > 0 puede representarse en forma u´nica como a = c0 + c1t + · · ·+ cn−1tn−1 + cntn = n∑ i=0 cit i donde cn es positivo y 0 ≤ ci < t, para 0 ≤ i ≤ n. Esta proposicio´n garantiza que cada entero mayor que 1 puede servir como base para un sistema de numeracio´n. Las precisiones expuestas servira´n para movernos con libertad suficiente en el desarrollo de algunos to´picos cuya construccio´n esta´ por fuera de los objetivos planteados. Construir tria´ngulos recta´ngulos con lados enteros fue objeto de investi- gacio´n por parte de los babilonios 1600 an˜os antes de Cristo. No solamente le dieron solucio´n a esteproblema sino que lo aplicaron a la trigonometr´ıa 5 construyendo tablas. Euclides en el de´cimo libro de los Elementos escribio´ un ana´lisis detallado al plantear la solucio´n en los enteros de la ecuacio´n: x2 + y2 = z2 conocida como ecuacio´n pitago´rica, debido a la creencia que fue Pita´goras quien la planteo´ por primera vez en el an˜o 550 antes de Cristo. Las soluciones ma´s simples esta´n conformadas por 3, 4, 5 y 5, 12, 13 y mu´ltiplos de estos, por ejemplo 6, 8, 10 que es el doble de la primera y 25, 60, 65 que es cinco veces la segunda. Tal vez se piense que no haya otras, pero efectivamente las hay. En los tria´ngulos de lados 3, 4, 5 y 5, 12, 13 la hipotenusa es una unidad mayor que uno de los catetos. Si a y b son los catetos y la hipotenusa es b + 1, de acuerdo con el teorema de Pita´goras a2 + b2 = (b + 1)2. Realizando las operaciones pertinentes se llega a la igualdad a2 = 2b + 1 de donde se concluye que a2 es impar y por lo tanto a tambie´n lo es. Tomando a = 2n + 1, reemplazando en la igualdad anterior se observa que b = 2n2 + 2n lo que lleva a deducir que (2n+1), (2n2+2n), (2n2+2n+1) son los lados de un tria´ngulo recta´ngulo, donde la u´ltima expresio´n corresponde a la hipotenusa. Pero los anteriores distan de ser todos, estos se encuentran a trave´s de la solucio´n de la ecuacio´n x2 + y2 = z2 ecuacio´n que tiene infinitas soluciones si x, y, z son primos relativos; y es par positivo; x, z ambos impares positivos. Las soluciones vienen dadas por x = u2 − v2, y = 2uv, z = u2 + v2 donde u, v son enteros que satisfacen las condiciones u > v > 0, son primos relativos y uno de los dos es par. Si u = 2, v = 1 se tiene la solucio´n 3, 4, 5. Si u = 3, v = 2, la solucio´n es 5, 12, 13. 6 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA La mejor contribucio´n de Euclides a la aritme´tica fue el desarrollo de las demostraciones del algoritmo euclidiano, la existencia de un nu´mero infinito de primos y el teorema fundamental de la aritme´tica que establece que todo entero distinto de cero se puede expresar como el producto de un nu´mero finito de factores primos, conceptos que tienen su fundamento en la relacio´n de divisibilidad. Fermat estudio´ la ecuacio´n xn + yn = zn para enteros n ≥ 3. Afirmo´ tener una solucio´n asegurando que, excepto para el caso en que n = 2, no hab´ıa solucio´n diferente a 0, 0, 0. Desafortunadamente no la dio a conocer siendo este uno de los tres problemas insolubles ma´s famosos. Este hecho se nombra en la historia como el u´ltimo teorema de Fermat o el teorema grande de Fermat, en contraposicio´n al conocido como el teorema menor de Fermat, cuyo enunciado establece que si p es primo, entonces para todo a, ap ≡ a mod p. Y si p no divide a a, ap − 1 ≡ 1 mod p. Lo de menor tal vez fue para resaltar la importancia del primero. Un caso especial del teorema menor de Fermat establece que si p es primo, entonces p|(2p − 2). Los chinos creyeron por mucho tiempo que el rec´ıproco tambie´n era cierto y lo verificaron hasta 300. Consideraron durante ma´s de 23 siglos que era una regla infalible para decidir primalidad, pero falla para 341 = 11× 31. Debido a que 2341− 2 consta de 103 cifras comprobarlo se pospone hasta cuando haya la teor´ıa suficiente. 1.1. Divisibilidad Definicio´n 1.1.1. Conside´rense los enteros a, b con a �= 0. Si existe un entero c tal que b = ac, se dice que a divide a b y se escribe a|b. Si a no divide a b, se escribe a � b. 1.1. DIVISIBILIDAD 7 Como 8 = 2× 3 + 2 , se deduce que 3 � 8. Otros ejemplos son: 5|15, 1|4, (−2)|6, 2|(−8), 5 � 14. La relacio´n de divisibilidad no es una equivalencia debido a que no es sime´tri- ca, por ejemplo 3|6, pero 6 � 3. Es fa´cil verificar que es reflexiva y transitiva. Para todo entero a diferente de cero, existe el entero 1, tal que a = a× 1 y de acuerdo con la definicio´n a|a indicando que es reflexiva. Sean a, b, c tres enteros donde a y b son ambos diferentes de cero tales que a|b y b|c entonces existen enteros d, e que satisfacen las igualdades b = ad, c = be. Si el valor de b en la primera igualdad lo reemplazamos en la segunda se obtiene c = (ad)e = a(de) y como de es un entero se concluye que a|c, infirie´ndose que es una relacio´n transitiva. Las siguientes proposiciones son otras propiedades de la divisibilidad que se pueden deducir usando la definicio´n. Como es tradicional las letras se usara´n para representar enteros. Para evitar confusiones las cifras enteras se escriben sin usar los puntos correspondientes a la escritura formal. El punto y el signo × se usan para expresar producto, por ejemplo, 23 · 45 y 23× 45 significan ��23 por 45��, mientras que 2345 debe leerse ��dos mil trescientos cuarenta y cinco��. 1. Si a|b y b|a, entonces a = b o a = −b. 2. Si a|b y a|c, entonces a|(bx ± cy) para toda pareja x, y. En particular a|(b± c). Si a|b, entonces a|bx, para todo x. 3. Si a|b y b > 0, entonces a ≤ b. 4. Para todo a �= 0 y para todo b, a|0 y ±1|b. 5. Sean a, b, k con a �= 0, k �= 0, entonces a|b si y solo si ak|bk. 6. Si a|b y b �= 0, entonces | a | ≤ | b |. 8 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA Note que el orden en que aparecen las anteriores proposiciones no es impor- tante, por ejemplo la proposicio´n (3) se puede considerar como una conse- cuencia de (6) pero es posible hacer una demostracio´n directa de (3) sin usar (6). Definicio´n 1.1.2. Dos enteros a, b ambos diferentes de cero tales que a|b y b|a se dice que son asociados. De acuerdo con (1) los u´nicos asociados de un entero a son a y −a. Para demostrar la propiedad (1) se deben tomar dos asociados y concluir que son iguales o que solo difieren en el signo. Para el efecto to´mense los asociados a, b. Por definicio´n existen c y d tales que b = ac, a = bd. Si el valor de a, en la igualdad de la derecha, lo reemplazamos en la de la izquierda se obtiene b = (bd)c = b(dc) y de esta u´ltima se deduce que dc = 1, pero debido a que d y c son enteros, u´nicamente se pueden tener dos posibilidades, d = c = 1 o d = c = −1. Si ocurre la primera posibilidad, reemplazando a c se concluye de la primera igualdad que b = a. Si ocurre la segunda se obtiene b = −a. Para demostrar la propiedad (2) se supone que a|b y a|c, luego existen enteros m,n tales que b = am c = an. Multiplicando ambos miembros de la primera igualdad por x y los de la segunda por y, sumando miembro a miembro y factorizando a, se tiene bx + cy = a(mx + ny). Por la seleccio´n de m, x, n, y, (mx+ny) es un entero, t lo que permite concluir que bx + cy = at de donde se puede afirmar que a|(bx + cy). Haciendo x = y = 1, obtenemos a|(b + c). Si reemplazamos a x por 1, a y por −1 entonces a|(b − c). Si se iguala c con cero se concluye que a|bx. 1.1. DIVISIBILIDAD 9 Hay dos hechos importantes de la aritme´tica que usaremos a lo largo del texto. El primero afirma que cualquier conjunto de enteros positivos que contenga al menos un elemento contiene un elemento mı´nimo, y es conocido como el principio de la buena ordenacio´n. El segundo es una consecuencia del primero y se ha mencionado con anterioridad, es el algoritmo de Euclides o algoritmo de la divisio´n. Se denomina algoritmo porque proporciona un me´todo mediante el cual se pueden hallar cocientes y residuos al momento de dividir. Definicio´n 1.1.3. Un entero p es primo si siendo distinto de cero y de ±1 es divisible solamente por ±1 y ±p. Definicio´n 1.1.4. Un natural n �= 1 se dice compuesto si no es primo, esto es, si existen naturales d1 y d2 tales que 1 < d1 < n, 1 < d2 < n con n = d1d2. Teorema 1.1.1 (El algoritmo de la divisio´n). Si a es un nu´mero natural y b es un entero, existen enteros u´nicos q, r tales que b = aq+r, con 0 ≤ r < a. Demostracio´n. De la igualdad b = at + r, se obtiene r = b − at. To´mese el conjunto S = {b− at, t ∈ Z} ⊆ Z. Consideremos b ≥0, como t recorre el conjunto de los enteros, sea t = 0. En este caso b− at ≥ 0. Supongamos que b < 0 por ide´ntica razo´n hagamos t = b. En dicho caso, b− at = b− ab = b(1− a). Pero, 1 ≤ a entonces, b(1−a) ≥ 0 es decir, b−at ≥ 0, lo que permite afirmar que el conjunto S posee elementos no negativos. Sea D ⊆ S formado por los elementos no negativos de S. Por el principio de la buena ordenacio´n, D tiene un elemento mı´nimo. Tomando r como este nu´mero y a q como el mayor entero que satisface la condicio´n b− aq ≥ 0, se deduce que, r = b − aq ≥ 0. Restando a a ambos miembros y factorizando, r − a = b− aq − a = b− a(q + 1). Pero, q + 1 > q y por la seleccio´n de q debe tenerse que b− a(q + 1) < 0 10 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA o sea, r − a < 0 de donde se concluye que r < a lo que permite escribir 0 ≤ r < a. Para demostrar la unicidad supongamos que q y r no son u´nicos. Sean q1 y r1 enteros tales que b = aq1 + r1, con 0 ≤ r1 < a. Por la propiedad transitiva de la igualdad, aq1 + r1 = aq + r. Supongamos que r > r1, entonces r − r1 > 0. Trasponiendo te´rminos y factorizando, 0 < r − r1 = a(q1 − q) de donde se tiene que a|(r − r1). Pero 0 ≤ r1 < a, implica que −a < −r1 ≤ 0 y como 0 ≤ r < a se pueden sumar miembro a miembro estas desigualdades dando como resultado −a < (r − r1) < a o sea, (r − r1) < a. De acuerdo con la propiedad (3) de divisibilidad, como a|(r − r1), necesa- riamente a < (r − r1); lo cual es una contradiccio´n. Por lo tanto, r no es mayor que r1. Suponer que r1 es mayor que r conduce a una contradiccio´n similar, de donde se deduce que r1 no es mayor que r, quedando como u´nica posibilidad, r = r1. De la expresio´n r − r1 = a(q1 − q) observamos que 0 = a(q1 − q) y como a es diferente de cero se concluye que (q1 − q) = 0 y por lo tanto, q = q1. En s´ıntesis la unicidad del cociente y el residuo quedan demostradas. El quinto axioma de Peano es el principio de induccio´n, este enuncia- do establece que dada una proposicio´n P (n). Si P (0) es verdadera y para cualquier k, la veracidad de P (k) implica la de P (k + 1), entonces P (n) es verdadera para todo natural n. De este principio se conocen cinco formas, la tercera tiene relacio´n con el buen orden y es la clave para demostrar que todo subconjunto S de los naturales que contenga a cero y contenga a n+1, siempre que contenga a n, contiene tambie´n a todos los naturales. La quinta forma nos permite realizar induccio´n a partir de un determinado natural k. 1.1. DIVISIBILIDAD 11 Para ilustrar el me´todo de induccio´n matema´tica realizamos el siguiente ejercicio. Ejemplo 1.1.1. Para todo natural s, 11|(102s+1 + 1). Demostracio´n. Por induccio´n. 102+1 + 1 = 103 + 1 = 1001 = 11× 91. De las igualdades se ve que la proposicio´n es va´lida para s = 1. Supongamos que es va´lida para s, esto es, 102s+1 + 1 = 11k. Multiplicando ambos miembros de esta igualdad por 100, 102s+3 + 100 = 100× 11k. Descomponiendo y factorizando el exponente y transponiendo te´rminos, 102(s+1)+1 = 100× 11k − 100. Sumando 1 a ambos miembros, 102(s+1)+1 + 1 = 100× 11k − 99 = 100× 11k − 11× 9 = 11(100k − 9). Lo anterior permite inferir que la proposicio´n es va´lida para s+1, luego debe serlo tambie´n para todo natural. Con respecto a los primos surgen algunas inquietudes referentes a su nu´mero, a la existencia de una regla para calcular su secuencia, fo´rmulas para determinarlos y muchos otros interrogantes estudiados por los matema´ticos de todos los tiempos entre los que se pueden mencionar, Euclides, Fermat, Euler, Po`lya. En 1914 D. N. Lehmer calculo´ la lista de los primos desde el primero hasta el que ocupa el 664999-e´simo lugar, este u´ltimo resulto´ ser 10006721. El siguiente enunciado sirve para establecer primalidad en un solo sentido 12 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA Ejemplo 1.1.2. Si 2n − 1 es primo, entonces n es primo, para n ≥ 2. Solucio´n. Para demostrarlo supongamos que n es compuesto, es decir, existen naturales a, b tales que, 1 < a < n, 1 < b < n, con n = ab, entonces 2n − 1 = 2ab − 1 = (2a)b − 1 = cb − 1 = (c− 1)(cb−1 + cb−2 + · · ·+ c + 1) donde c ≥ 4. En consecuencia, 2n − 1 es el producto de un entero mayor o igual a 3, por un entero mayor o igual a 5, contradiciendo la hipo´tesis, luego la proposicio´n se sigue. El rec´ıproco no es cierto, ya que para 11, 211−1 = 2047 que es compuesto. Ejemplo 1.1.3. La suma de los cuadrados de dos nu´meros impares no puede ser un cuadrado perfecto Solucio´n. Para un entero cualquiera k, los posibles residuos al dividir por 4 son 0, 1, 2, 3, lo que significa que k es de una de las formas 4t, 4t+ 1, 4t+ 2, 4t + 3, y por consiguiente k2 se puede escribir como 16t2, 4(4t2 + 2t) + 1, 4(4t2 +4t+ 1), 4(4t2 + 6t+ 2) + 1. Por lo visto el residuo de dividir k2 por 4 es 0 o 1. Tomemos los impares x = 2n+ 1, y = 2m+ 1, eleva´ndolos al cuadrado y sumando x2 + y2 = (4n2 + 4n + 1) + (4m2 + 4m + 1) = 4(n2 + m2 + n + m) + 2 lo que lleva a concluir que al dividir x2 + y2 por 4 el residuo es 2. En mejores palabras x2 + y2 no es un cuadrado perfecto. Teorema 1.1.2. El menor divisor positivo mayor que 1, de un entero n > 1 es un primo. Demostracio´n. Sea n ∈ N− {1}, m > 1 el menor divisor positivo de n. Por definicio´n m|n. Si n es primo, n = m luego m es primo. Sea n compuesto y suponga que m no es primo. Como m > 1, debe ser compuesto, esto es, existe un natural d tal que 1 < d < m y d|m, pero por hipo´tesis m|n. Por la propiedad transitiva de la divisibilidad, d|n contradi- ciendo la minimalidad de m. Por consiguiente m debe ser primo. 1.1. DIVISIBILIDAD 13 Teorema 1.1.3. Todo compuesto es el producto de un nu´mero finito de factores primos. Demostracio´n. Supongamos que existen compuestos que son el producto de un infinito nu´mero de factores primos. Por el principio de la buena ordenacio´n existe m el menor compuesto que puede expresarse como un nu´mero infinito de factores primos. Por el teorema 1.1.2, existe un primo p, 1 < p < m adema´s p|m, entonces 1 p < 1 < m p . Multiplicando por m la primera desigualdad tenemos, m p < m, luego 1 < m p < m. Como m p es un natural, entonces m p = p1p2 · · · pr con pi un primo, para 1 ≤ i ≤ r, r es un nu´mero fijo. Dicho en otras palabras m p debe ser el producto de un nu´mero finito de factores primos ya que es menor que m y como es sabido, m es el menor compuesto que puede escribirse como el producto de un infinito nu´mero de factores primos. Pero, m = p( m p ) = p(p1p2 · · · pr) indicando que m es el producto de un nu´mero finito de factores primos, contradiciendo el supuesto. En conclusio´n, todo compuesto es el producto de un nu´mero finito de factores primos. Teorema 1.1.4 (Teorema fundamental de la aritme´tica). Todo entero distinto de cero puede expresarse como el producto de (±1) por un nu´mero finito de factores primos. Esta expresio´n es u´nica salvo el orden en que los factores se consideren. Demostracio´n. Si n es primo el teorema es inmediato. Si es compuesto basta aplicar el teorema 1.1.3 teniendo en cuenta el signo y asunto concluido. Unicidad. Dado n > 1 suponga que se puede escribir en dos formas diferentes como producto de primos n = p1p2 · · ·pr = q1q2 · · · qs 14 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA como p1 es un factor de n, p1|q1q2 · · · qs, por tanto p1|qj para 1 ≤ j ≤ s. Ordenando nuevamente los sub´ındices de ser necesario se concluye que p1|q1. Pero al ser primos cada uno de ellos, obligatoriamente p1 = q1. Cancelando a ambos miembros de la igualdad se llega a p2 · · · pr = q2 · · · qs. Siguiendo un proceso similar se concluye que p2 = q2. Y as´ı sucesivamente, p3 = q3, . . . , pr = qs. Sin pe´rdida de generalidad se puede aceptar que r ≤ s. Si r < s cancelando factores iguales en la primera igualdad se llega a 1 = qr+1· · · qs lo que es imposible porque cada uno de los primos de la derecha es mayor que 1, llegando a la conclusio´n que r = s y de aqu´ı a que pi = qi, para todo i, 1 ≤ i ≤ r. Si n es negativo el primer factor sera´ (−1) seguido por factores primos positivos. Para responder a la inquietud relacionada con la cantidad total de primos, supongamos que existe un nu´mero finito de ellos y escribamos la sucesio´n de todos los primos {p1, p2, . . . , pr}. Sea p el entero definido como sigue p = (p1p2 . . . pr) + 1, p > pi para 1 ≤ i ≤ r, p necesariamente es compuesto y debe existir un primo pj de la coleccio´n dada tal que pj |p y como pj |p1p2 . . . pr sigue que pj|(p − p1p2 . . . pr) pero esta afirmacio´n equivale a decir que pj |1, contraviniendo el hecho de ser pj �= 1. Ahora podemos asegurar formalmente que el nu´mero de primos es infinito. Como aplicacio´n del teorema 1.1.4 se propone el siguiente ejercicio. Ejemplo 1.1.4. Hallar todos los primos que son una unidad menor que un cuadrado perfecto. Solucio´n. Para el efecto tomemos un primo p = x2− 1. El teorema de facto- rizacio´n u´nica establece que p = (x − 1)(x + 1). Como p es primo se tienen las dos posibilidades siguientes: (x− 1) = 1 y (x + 1) = p o (x− 1) = p y (x + 1) = 1. 1.1. DIVISIBILIDAD 15 De estas ecuaciones se obtienen las soluciones, x = 2 y p = 3 o x = 0 y p = −1. La de la derecha hay que desecharla puesto que p es primo, quedando en definitiva p = 3. Por tanto 3 es el u´nico primo que es una unidad menor que un cuadrado perfecto. Ejemplo 1.1.5. Si n > 1 es compuesto, existe un primo p ≤ √n tal que p|n. Solucio´n. El teorema 1.1.2 dice que el menor divisor positivo mayor que 1 de un entero n mayor que 1 es un primo. Sea p tal primo, como p|n existe d, 1 < d < n tal que n = pd. Por la definicio´n de p, p ≤ d y por consiguiente p2 ≤ pd, de donde se obtiene por reemplazo p2 ≤ n, esto es, p ≤ √n. En las igualdades 3 = 2 + 1 7 = 2× 3 + 1 31 = 2× 3× 5 + 1 se observa que 1 ma´s el producto de los primeros k primos es un primo al menos para k = 2, 3, 5. Se puede pensar que es cierto para todo k pero un ejemplo muestra lo contrario, 2× 3× 5× 7× 11× 13 + 1 = 30031 = 59× 509. EJERCICIOS 1. Demostrar las propiedades 3, 4, 5, 6 de divisibilidad enunciadas ante- riormente. 2. Demostrar que para todo natural n, 11 divide a 102n − 1. 3. Demostrar que para todo natural n, 3 divide a 10n − 1. 4. Demostrar que si 2 no divide a n y 3 no divide a n, entonces 24 divide a n2 + 23. 16 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA 5. Demostrar que para todo entero n, 3 divide a alguno de los nu´meros n, n + 2, n + 4. 6. Demostrar que todo primo impar puede ser expresado de manera u´nica como la diferencia de dos cuadrados. Por ejemplo, 11 = 36− 25. 7. Para todo natural n demostrar que ninguno de los siguientes n − 1 enteros consecutivos es primo: n! + 2, n! + 3, n! + 4, . . . , n! + n. 8. Usando la idea del ejercicio anterior hallar una sucesio´n de k consecu- tivos naturales compuestos. 9. Demostrar que para n > 1, n4 + 4 es compuesto. 10. Un nu´mero n es compuesto si existe un primo p ≤ √n, tal que p|n. Usando esta idea diga cua´les de los siguientes enteros son primos y cua´les compuestos : 91, 103, 343, 731. 11. Hallar enteros r, s tales que 144r + 2975s = 5. 12. Demostrar: Si m|(45n + 37) y m|(9n + 4), (m > 1) entonces m = 17. 13. Demostrar que el producto de cuatro enteros consecutivos incrementado en 1, es siempre un cuadrado perfecto. 14. Demuestrar que si p es primo y p|ab, entonces p|a o p|b. 15. Demostrar que si a, b son enteros positivos, existe un entero positivo n tal que na > b. (Considere la diferencia b− na y aplique el axioma del buen orden). 16. Usando el axioma del buen orden demuestrar que no hay enteros entre cero y uno. 17. Demostrar que si p = 6k + r es un primo diferente de 2 y 3, entonces r = 1 o r = 5. 18. Demostrar que existen infinitos primos de la forma 6k − 1. 19. Si a > 2 y s > 1. Demostrar as − 1 es compuesto. 20. Demostrar que el producto de nu´meros de la forma 6k + 1 es de la misma forma. 1.2. EL M.C.D Y EL M.C.M 17 1.2. El ma´ximo comu´n divisor y El mı´nimo comu´n mu´ltiplo Si se toman dos enteros a, b puede ocurrir que ambos sean iguales a cero y en este caso cualquier entero es un divisor comu´n de ellos. Si al menos uno es diferente de cero, los divisores comunes son finitos; uno de los cuales siempre es 1, deducie´ndose que existe alguno mayor que todos y debe ser positivo. Definicio´n 1.2.1. Dados dos enteros a, b, a2 + b2 �= 0, entonces d ∈ Z−{0} se llama un comu´n divisor de a y b si y solo si d|a y d|b. Teorema 1.2.1. Dados dos enteros a y b, a2 + b2 �= 0, existe un entero u´nico g, tal que 1. g > 0. 2. g|a y g|b. 3. g = min{ax + by > 0, x, y ∈ Z}. 4. Si d es cualquier entero tal que d|a y d|b, entonces d|g. La proposicio´n (4) dice que cualquier divisor comu´n de a y b divide a g. De la propiedad (6) de divisibilidad se deduce que g es nume´ricamente mayor que los diferentes divisores de a y b. Por lo tanto, del conjunto de divisores comunes de a y b, g es el ma´ximo desde dos puntos de vista y por esto se le llama el ma´ximo comu´n divisor de a y b. En forma abreviada se escribe g = (a, b). Note que realmente lo ��ma´ximo�� lo tomamos en el sentido de (4). Demostracio´n. Conside´rense primero a y b positivos, a > b. Por el algoritmo de la divisio´n existen enteros r1, q1 u´nicos tales que a = bq1 + r1, 0 ≤ r1 < b. Si r1 = 0, entonces b es un comu´n divisor de a y b. Podemos tomar g = b. 1. g > 0. 2. g|a y g|b. 18 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA Tomemos el conjunto H = {ax + by > 0, x, y ∈ Z} ⊆ Z. Si x < 0, necesariamente y > 0 entonces by > 0. Debido a que ax + by > 0 debe tenerse |ax| < by. Pero cero es el mı´nimo natural que verifica esta u´ltima desigualdad, luego x = 0, entonces el mı´nimo valor para y debe ser 1, por tanto b = a× 0 + b× 1 > 0 es un elemento de H . Similarmente si y ≤ 0 hallamos y = 0, x = 1 como valores mı´nimos, o sea a = a× 1 + y × 0 > 0 pertenece tambie´n a H , pero b < a. Si x > 0, y > 0, ax > a, by > y; entonces ax + by > a + b > b. En s´ıntesis, b = g = min{ax + by > 0, x, y ∈ Z} dando por demostrado (3). (4). Si existe d tal que d|a, d|b debe tenerse d|g puesto que g = b. Si r1 �= 0, la aplicacio´n repetida del algoritmo de la divisio´n demuestra la existencia de parejas u´nicas qi, ri, 2 ≤ i ≤ k + 1, 0 < ri < ri−1, tales que a = bq1 + r1 b = r1q2 + r2 r1 = r2q3 + r3 ... rk−2 = rk−1qk + rk rk−1 = rkqk+1 + 0. 1.2. EL M.C.D Y EL M.C.M 19 Aqu´ı confrontamos cada etapa con la posibilidad de tener cero por residuo; pero suponemos que esto no sucede sino hasta el k-e´simo paso de la divisio´n, o dicie´ndolo en otra forma, definimos a k como el nu´mero de la etapa en la cual aparece cero como residuo. En esta parte el proceso debe detenerse porque la divisio´n por cero no esta´ definida. Por otro lado, eventualmente debe aparecer un cero como residuo puesto que b > r1 > r2 > . . . > rk es una sucesio´n finita estrictamente decreciente de naturales; y como existen b − 1 enteros positivos menores que b, despue´s de a lo ma´s b − 1 divisiones debe obtenerse el esperado cero como residuo. En conclusio´n, si b no divide a a existe siempre un sistema finito de ecua- ciones de la clase anterior y un k-e´simo residuo diferente de cero. Aseguramos que para satisfacer las condiciones (1), (2), (3), (4) podemos tomar g = rk. De la u´ltima ecuacio´n observamos que rk | rk−1 entonces rk−2 = rk−1 + rk = (rkqk+1)qk + rk = rk(qk+1qk + 1) o sea que rk|rk−2. Siguiendo el proceso vemos de las dos primeras ecuaciones que rk|a y rk|b, luego rk es un divisor comu´n a y b. Expresando los residuos sucesivos se obtiene r1 = a− bq1 r2 = b− r1q2 = b− (a− bq1)q2 = b− aq2 + bq1q2 = a(−q2) + b(1 +q1q2). La forma de estas igualdades indica que rk puede obtenerse por reemplazos sucesivos como una combinacio´n lineal de a y b con coeficientes enteros en cuya expresio´n intervienen los qi, o sea, rk = ax + by. Como rk > 0, por el principio de la buena ordenacio´n existe un elemento mı´nimo en el conjunto H . Sea h tal elemento, luego para algunos enteros x0, y0 se establece la igualdad h = ax0 + by0 > 0. 20 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA Supongamos que h no divide a a, entonces existen enteros u´nicos q, r tales que a = hq + r, 0 < r < h luego r = a− hq = a− (ax0 + by0)q = a(1− x0q) + (−y0q). Como r < h, implicar´ıa que h no es el mı´nimo, llegando a una contradiccio´n; por consiguiente h|a. Similarmente h|b y de aqu´ı, h|(ax + by), o sea, h|rk. Por la propiedad (3) de divisibilidad h ≤ rk. Pero rk|a y rk|b implica que rk|(ax0 + by0) y en consecuencia rk = h. Por la misma propiedad rk ≤ h, concluye´ndose que rk = h. En s´ıntesis, rk es el mı´nimo del conjunto de los ax + by > 0. Sea d tal que d|a y d|b, entonces d|(ax + by), es decir d|rk. Como rk cumple las cuatro condiciones del teorema, es posible afirmar que rk = g = (a, b). Si a < b, intercambiamos los roles. Si a < 0 y b < 0 determinar g correspondiente a los respectivos valores absolutos. Si a = 0, entonces | b | = g = (a, b). Para demostrar la unicidad, tomemos g, g1 dos enteros que satisfacen las condiciones del teorema, entonces g|a y g|b implica que g|g1. Por otra parte g1|a y g1|b implica g1|g y como consecuencia g ≤ g1 y g1 ≤ g determina´ndose que g = g1. El teorema anterior proporciona una regla para hallar el ma´ximo comu´n divisor de dos nu´meros por divisiones sucesivas; este es el u´ltimo residuo diferente de cero que se obtiene al aplicar el algoritmo de Euclides. El mismo procedimiento puede utilizarse para expresarlo como una com- binacio´n lineal de dichos nu´meros. Veamos co´mo es posible mediante el al- goritmo de Euclides calcular el ma´ximo comu´n divisor de dos nu´meros. Ejemplo 1.2.1. Calcular el ma´ximo comu´n divisor de 42 y 30 y expresarlo como una combinacio´n lineal de dichos nu´meros. 1.2. EL M.C.D Y EL M.C.M 21 Solucio´n. 42 = 30× 1 + 12 30 = 12× 2 + 6 12 = 6× 2 + 0. La u´ltima igualdad indica que (42, 30) = 6. Ahora, 6 = 30− 12× 2 = 30− (42− 30)2 = 30− 42× 2 + 30× 2 = 30× 3− 42× 2 = 30× 3 + 42(−2). El u´ltimo renglo´n muestra la escritura de 6 como una combinacio´n lineal de 42 y 30, donde intervienen 3 y −2. Teorema 1.2.2. Sean a, b enteros, entonces, 1. (a, b) = (a, b + ka). 2. (a, b) = (a,−b) = (−a, b) = (−a,−b). 3. (ka, kb) = | k |(a, b) si k �= 0. 4. Si d|a, d|b, entonces (a d , b d ) = 1|d|(a, b). 5. Si g = (a, b), entonces (a g , b g ) = 1. Demostracio´n. Sean g = (a, b) g1 = (a, b + ka). Si g|a y g|b, entonces para cualquier entero k, g|(a, b+ka), luego g|g1 y como g > 0, g1 > 0 necesariamente g ≤ g1. Por otra parte, g1|a, y g1|(b+ ka), implica que g1|(b+ ka− ka), o sea g1|b y por razones similares g1 ≤ g. En atencio´n a las dos desigualdades se concluye que g = g1. El resto de la demostracio´n se asigna como ejercicio. 22 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA Definicio´n 1.2.2. Sean ai, 1 ≤ i ≤ n, n enteros, si gi = (ai, ai+1), entonces, gn−1 = (a1, a2, . . . , an). Si gn−1 = 1, los ai se dicen primos relativos o coprimos. Un caso particular se da cuando n es igual a 2. La definicio´n anterior garantiza la existencia del ma´ximo comu´n divisor de ma´s de dos nu´meros, el cual se puede considerar como el divisor comu´n positivo que es divisible por todo comu´n divisor. Definicio´n 1.2.3. Sean ai, 1 ≤ i ≤ n, n enteros. Si (ai, aj) = 1, para i �= j elementos de {1, 2, . . . , n}, entonces se dice que los ai, aj son primos relativos dos a dos. Por ejemplo (6, 5, 10) = 1, pero ellos no son primos relativos dos a dos porque 5 divide a 10. En cambio 10, 9, y 49 son primos relativos dos a dos. Teorema 1.2.3. Sean a, b dos enteros, si a = bq+ r, entonces (a, b) = (b, r). Demostracio´n. (a, b) = (bq + r, b) = (bq + r − bq, b) = (r, b) = (b, r). Lema 1.2.1. Lema de Euclides. Si a|bc y (a, b) = 1, entonces a|c. Demostracio´n. Si (a, b) = 1 existen enteros x, y tales que 1 = ax + by, entonces, c = acx + bcy pero por hipo´tesis a|bc y a|a luego a|(acx + bcy), o sea, a|c. Esta proposicio´n se conoce mejor como la primera versio´n del lema de Euclides. Ejemplo 1.2.2. Si (a, 4) = 2, (b, 4) = 2, demostrar que (a + b, 4) = 4. Solucio´n. Si (a, 4) = 2, entonces 2|a, luego existe un impar x tal que a = 2x. Si x fuera par, entonces x = 2m, y por lo tanto a ser´ıa igual a 4m, de donde se concluir´ıa que (a, 4) = (4m, 4) = 4. Como (b, 4) = 2, por las mismas razones, b = 2n, para un impar n. Efectuando la suma, a+ b = 2(x+n) = 4z, puesto que x + n es un par, de donde se concluye que (a + b, 4) = 4. Ejemplo 1.2.3. Demostrar que si (a, b) = 1, entonces (a+ b, a− b) = 1 o 2 Solucio´n. Sean (a, b) = 1. Si g = (a+ b, a− b), entonces g| [(a+ b)± (a− b)]. Tomando los signos positivo y negativo en ese orden se deduce que g|2a, g|2b y por consiguiente g|(2a, 2b), luego g|2(a, b), de donde se concluye que g|2 puesto que (a, b) = 1. Pero g > 1, infirie´ndose que g = 1 o g = 2. 1.2. EL M.C.D Y EL M.C.M 23 Examinando los conjuntos formados con los mu´ltiplos de 2 y de 3 es fa´cil darse cuenta que la interseccio´n consta de todos los nu´meros de la forma 2 × 3n. De acuerdo con el principio de la buena ordenacio´n este conjunto posee un elemento mı´nimo, el nu´mero 6, indicando que 6 es el menor de los mu´ltiplos comunes a 2 y 3. Esta situacio´n se puede generalizar a toda pareja de enteros con la condicio´n de ser por lo menos uno de los dos diferente de cero, dando como resultado la existencia del mı´nimo comu´n mu´ltiplo de dos enteros cualesquiera prevista la restriccio´n anotada. Tome el valor absoluto del producto y divida entre el ma´ximo comu´n divisor de los nu´meros dados, este cociente siempre es posible puesto que el divisor nunca es cero y por la forma como esta´ concebido es un entero positivo. Teorema 1.2.4. El entero [a, b] = | ab | (a, b) tiene las siguientes propiedades 1. [a, b] ≥ 0. 2. a| [a, b]. 3. Si a|m y b|m, entonces [a, b]|m. La demostracio´n se deja al estudiante. Al elemento descrito en el teorema 1.2.4 se le llama el mı´nimo comu´n mu´ltiplo de los nu´meros dados. El concepto es fa´cilmente extensivo a ma´s de dos enteros. EJERCICIOS 1. Demostrar los numerales restantes del teorema 1.2.2. 2. Dado (u, v) = 1; si u|n y v|n, entonces uv|n. 3. Mediante el algoritmo de la divisio´n hallar el ma´ximo comu´n divisor de: a) 1001 y 7655. b) 4148 y 7684. c) 11 y 15. d) 144 y 24. e) ) 75, 50 y 125. 24 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA 4. Demostrar que si (a, b) = 1 y c|a, entonces (c, b) = 1. 5. Demostrar que si (a, b) = 1, entonces (a2 + b2, a + b) = 1 o 2. 6. Demostrar que el ejercicio 2 no necesariamente es cierto si (u, v) > 1. 7. Demostrar que para todo n, 5|(n5 − n). 8. Si (a, b) = 1, hallar los posibles valores de (a + 3b, a2 − b2). 9. Demostrar que si (a, b) = 1, (ac, b) = (c, b), para todo entero c. 10. Demostrar que si (b, c) = 1, entonces (a,bc) = (a, b)× (a, c). 11. Demostrar que si ax + by = n, entonces (a, b)|n. 12. Demostrar que no es posible la simplificacio´n de la fraccio´n a1+a2 b1+b2 , si a1b2 − a2b1 = ±1. 13. Hallar el mı´nimo comu´n mu´ltiplo de, a) 24 y 144. b) 1001 y 765. c) 36, 12 y 144. 14. Demostrar que si l = [a, b] y n es un mu´ltiplo comu´n de a y b, entonces l|n. Sugerencia: Suponer que l no divide a n. 1.3. Congruencias La solucio´n en los enteros de la ecuacio´n ax + by = c, llevo´ a Diofanto a la comparacio´n de residuos entre algunos de sus componentes. Tomemos, por ejemplo, 8x− 19y = 2. Como la diferencia es 2, x puede ser par o impar, y necesariamentedebe ser par. Por ejemplo, x = 5, y = 2; x = 24, y = 10. Usando el algoritmo de Euclides 19 = 8× 2 + 3 1.3. CONGRUENCIAS 25 8 = 3× 2 + 2 3 = 2× 1 + 1. Despejando y reemplazando en orden inverso y conmutando los productos, 1 = 3− 2× 1 = 3 + 3× 2− 8 = 3× 3− 8 = 3(19− 8× 2)− 8 = 19× 3− 8× 7 = 8(−7)− 19(−3) multiplicando por 2 2 = 8(−7× 2)− 19(−3× 2). Sumando y restando 8(19)t al segundo miembro de esta u´ltima igualdad, despue´s de conmutar y factorizar, se tiene 2 = 8[(−7× 2) + 19t]− 19[(−3× 2) + 8t]. De esta igualdad se deduce que, si t es un entero; al dividir a 8[(−7×2)+19t] y a 19[(−3× 2) + 8t] por 2, el residuo debe ser el mismo. La solucio´n general esta´ dada por x = −(7× 2) + 19t, y = −(3× 2) + 8t. Si t = 1, x = 5, y = 2 y si t = 2, x = 24, y = 10. Existen muchos otros problemas en los cuales debe hacerse comparacio´n de residuos. Los nu´meros que tienen ide´ntico residuo se les denomina equirre- siduales o congruentes y es obvio que pertenecen a una misma clase residual. Definicio´n 1.3.1. Dados dos enteros a y b, m un natural diferente de cero, se dice que a es congruente con b mo´dulo m si y solo si m|(a− b) y se nota a ≡ b mod m. Ejemplos 17 ≡ 2 mod 5, 14 ≡ −6 mod 10. La congruencia es una relacio´n de equivalencia. Para cualquier natural m diferente de cero y para cualquier entero a, m es un divisor de cero y por ende de a−a; esta situacio´n conlleva a la reflexividad. 26 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA Si m es un divisor de a− b, tambie´n lo es de b− a, propiedad que implica la simetr´ıa. Si m es simulta´neamente divisor de a− b, y, de b− c, lo sera´ de la suma y por tanto de a− c, verifica´ndose la transitividad. Para una relacio´n de equivalencia definida en un conjunto S y para cada elemento a de S, existe un conjunto formado por todos los elementos relacio- nados con a denominado la clase de equivalencia de a, notado [ a ]. Si b es un elemento de S que no esta´ relacionado con a tambie´n existe la clase de equiva- lencia de b y as´ı sucesivamente. Estas clases tienen la particularidad de no ser vac´ıas, de no tener elementos comunes, de poder incluir cada elemento de S en alguna de ellas y la unio´n de todas debe ser todo S. Ya habra´ oportunidad de hacer una mejor exposicio´n de este tema en otro contexto. Teorema 1.3.1. Sean x, y enteros. Si a ≡ b mod m, c ≡ d mod m, entonces 1. (xa + yc) ≡ (xb + yd) mod m. 2. (a + c) ≡ (b + d) mod m. 3. xa ≡ xb mod m. Demostracio´n. Por hipo´tesis m|(a − b), m|(c − d). Por la propiedad (2) de divisibilidad m| [x(a− b)+y(c−d)], entonces m| [(xa+yc)− (xb+yd)] y por definicio´n, (xa + yc) ≡ (xb + yd) mod m. Si x = y = 1 se tiene (2). Si y = 0 se tiene (3). Teorema 1.3.2. Si a ≡ b mod m y c ≡ d mod m, entonces ac ≡ bd mod m. Demostracio´n. Como m|(a− b), m|(c− d), entonces m|(ac− bc+ bc− bd) de donde m|(ac− bd) y por definicio´n ac ≡ bd mod m. Una regla para multiplicar un nu´mero de tres d´ıgitos por 1001 consiste en escribirlo dos veces. Por ejemplo, 152× 1001 = 152152. Por otra parte la descomposicio´n en factores primos de 1001 es 1001 = 7× 143. Estos hechos permiten hallar ra´pidamente el factor desconocido del producto 143x si cono- cemos los tres u´ltimos d´ıgitos del resultado. La clave consiste en multiplicar estas cifras por 7 y tomar nuevamente las tres u´ltimas cifras de este nuevo producto. Por ejemplo, si 143x = 61204 se toman las tres u´ltimas cifras, esto es, 204 y multiplicando por 7 se obtiene 204×7 = 1428. El factor desconocido es 428. Puede comprobarlo. 1.3. CONGRUENCIAS 27 En te´rminos de congruencias, deseamos encontrar un nu´mero x de una, dos o tres cifras donde b es la cantidad formada con las tres u´ltimas cifras de 143x. Esto lo podemos transformar en: 143x ≡ b mod 1000. Adema´s 7 ≡ 7 mod 1000. Multiplicando miembro a miembro 7× 143x ≡ 7b mod 1000 en otros te´rminos 1001x ≡ 7b mod 1000 pero 1001 ≡ 1 mod 1000 y x ≡ x mod 1000 por tanto 1001x ≡ x mod 1000 finalmente x ≡ 7b mod 1000. Esta congruencia indica que los tres u´ltimos d´ıgitos de x concuerdan con los tres u´ltimos d´ıgitos de 7b. Como x tiene a lo ma´s tres d´ıgitos, los tres u´ltimos de 7b determinan completamente a x. Teorema 1.3.3. Si a ≡ b mod m, entonces para todo n ∈ N, an ≡ bn mod m. Demostracio´n. Por induccio´n matema´tica. Por hipo´tesis el teorema se verifica para 1. Supongamos que se verifica para k, esto es, ak ≡ bk mod m. Usando el teorema 1.3.2, aka ≡ bkb mod m, pero esta expresio´n es equivalente a ak+1 ≡ bk+1 mod m. Es decir la proposicio´n es va´lida para todo natural n. 28 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA Teorema 1.3.4. Sea f(x) un polinomio con coeficientes enteros. Si a ≡ b mod m, entonces f(a) ≡ f(b) mod m. Demostracio´n. Sea f(x) = n∑ i=0 cix i un polinomio con coeficientes enteros, f(a) = n∑ i=0 cia i entonces f(a) ≡ n∑ i=0 cia i mod m. Usando los teoremas 1.3.3 y 1.3.1 respectivamente n∑ i=0 cia i ≡ n∑ i=0 cib i ≡ f(b) mod m y por aplicacio´n de la propiedad transitiva f(a) ≡ f(b) mod m. La demostracio´n del siguiente teorema es una de aquellas tareas fa´ciles si se usa la induccio´n matema´tica. Teorema 1.3.5. Si aj ≡ bj mod m, entonces n∑ i=0 aj ≡ n∑ i=0 bj mod m para todo n ≥ 1. En lo que sigue se enuncian algunas propiedades importantes de las con- gruencias, especialmente las restricciones impuestas a la ley cancelativa del producto. El factor a cancelar puede ser parte decisiva de la divisibilidad in- herente a la congruencia considerada. Dos de estas propiedades se establecen de la siguiente manera y sus demostraciones se dejan al intere´s de los lectores. 1. Sea d �= 0 un natural tal que d|m. Si a ≡ b mod m, a ≡ b mod d. 2. a ≡ b mod xi, 1 ≤ i ≤ n si y solo si a ≡ b mod l, l = [x1, x2, . . . , xn]. Teorema 1.3.6. Si g = (a,m), ax ≡ ay mod m si y solo si x ≡ y mod m g . 1.3. CONGRUENCIAS 29 Demostracio´n. Si g = (a,m), existen m1, a1, (m1, a1) = 1, m, g,m1 enteros positivos tales que, a = a1g, m = m1g. Pero ax ≡ ay mod m, si y solamente si, m|a(x− y) o equivalentemente, despue´s de realizar los reemplazos correspondientes y cancelar, m1|a1(x− y) expresio´n equivalente, de acuerdo con el lema de Euclides, a m1|(x− y). La definicio´n de congruencia indica que x ≡ y mod m1. Pero, m1 = m g . Realizando la sustitucio´n se obtiene lo pedido. Teorema 1.3.7. Si ax ≡ ay mod m y (a,m) = 1, entonces x ≡ y mod m. Demostracio´n. En el teorema anterior tome g = 1. Teorema 1.3.8. La congruencia ax ≡ b mod m tiene solucio´n si y solamente si (a,m)|b. Si g = (a,m), existen g diferentes soluciones mo´dulo m. Demostracio´n. Conside´rese la congruencia ax ≡ b mod m donde a, b,m, son enteros y m > 0. Por hipo´tesis m|(ax− b). Si el entero s es una solucio´n, m|(as− b). Por la propiedad (2) de divisi- bilidad para cualquier entero k, m| [a(s + km)− b] por tanto a(s + km) ≡ b mod m, o sea, s + km es otra solucio´n. As´ı pues, si s es una solucio´n tambie´n lo es cualquier otro elemento de la clase de equivalencia [ s ] mo´dulo m. En 30 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA consecuencia, si ax ≡ b mod m tiene soluciones, estas son elementos de una o ma´s clases de equivalencia del conjunto cociente Z/m. Suponga ahora que (a,m) = 1 = ra + tm. Entonces, b = bra + btm. Despejando, a(br)− b = (−bt)m esto es, m| [a(br)− b)], concluye´ndose que br es una solucio´n. Sea s = br y supongamos que u es otra solucio´n. Como as ≡ b mod m y au ≡ b mod m, sigue que as ≡ au mod m, o sea, m|a(s− u). Pero (a,m) = 1 entonces, por el lema de Euclides, m|(s− u) y de aqu´ı se concluye s ≡ u mod m. En s´ıntesis ax ≡ b mod m tiene una solucio´n s y [ s ] denominada la clase de congruencia contiene todas las soluciones. Supongamos que (a,m) = g = ra + tm > 1. Como a= cg, m = dg se sigue que si s es una solucio´n, entonces as− b = mq = dgq. Reemplazando y transponiendo te´rminos de obtiene b = g(cs− dq). Ahora es obvio que g|b. Rec´ıprocamente, supongamos que g = (a,m) divide a b y escribamos a = cg, b = eg, entonces de acuerdo con el hecho de ser ax ≡ b mod m se sigue que cg ≡ eg mod m. Por el teorema 1.3.6, 1.3. CONGRUENCIAS 31 cx ≡ e mod n, n = m g . Por tanto toda solucio´n de ax ≡ b mod m es solucio´n de cx ≡ e mod n y viceversa. Ahora bien, (c, n) = 1 de modo que cx ≡ e mod n tiene una solucio´n y por tanto ax ≡ b mod m tiene soluciones, quedando demostrada la primera parte del teorema. Para la segunda parte sea S = {s, s+ n, s + 2n, . . . , s + (g − 1)n} ⊆ [ s ] el conjunto que contiene la totalidad de las soluciones de cx ≡ e mod n. Para demostrar que no hay dos elementos de S congruentes mo´dulo m, as´ı que ax ≡ b mod m tiene por lo menos g soluciones incongruentes, en tanto que cada elemento de [ s ]−S es congruente mo´dulo m con algu´n elemento de S. Luego ax ≡ b mod m tiene a lo ma´s g soluciones incongruentes. Sean s + kn, s + ln con k �= l dos elementos diferentes de S. Aceptemos que son congruentes mo´dulo m, entonces m|(k− l)n, o sea, ng|(k− l)n, y por consiguiente g|(k− l), pero (k− l) < g, implicando que k− l = 0, de donde se concluye que k = l, contradiciendo el supuesto. De modo que los elementos de S son incongruentes mo´dulo m. Sea por ejemplo, s + (qg + r)n, g > r ≥ 0, q > 0 un elemento arbitrario de [ s ] − S. Como gn = m, reordenando y reempla- zando: s + (gq + r)n = (s + rn) + q(gn) = (s + rn) + qm. Pero (s + rn) + qm ≡ (s + rn) mod m, y (s + rn) ∈ S ya que r < g. De modo que ax ≡ b mod m tiene exactamente g soluciones incongruen- tes, siempre y cuando (a,m) = g, g|b. Teniendo la teor´ıa suficiente nos proponemos demostrar que a pesar de ser compuesto, 341 divide a (2341 − 2). Solucio´n. El teorema de Fermat establece que 210 ≡ 1 mod 11. 32 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA Por tanto 2341 ≡ 2(210)34 ≡ 2 mod 11 y en consecuencia 11|(2341 − 2). Adema´s, 25 ≡ 32 ≡ 1 mod 31 luego 2341 ≡ 2(25)68 ≡ 2(1)68 ≡ 2 mod 31 de donde se concluye que 31|(2341 − 2). Puesto que 11 y 31 son primos relativos, su producto divide a (2341−2). Esto es, 341|(2341 − 2). Los chinos se equivocaron y en honor al equ´ıvoco se dice que un compuesto que verifica la anterior proposicio´n es un seudoprimo. 341 es un seudoprimo. Ejemplo 1.3.1. Resolver la congruencia 14x ≡ 5 mod 45. Solucio´n. Como (14, 45) = 1 y 1|5, existe una u´nica solucio´n. Dado que 5 ≡ 50 mod 45, por la propiedad transitiva 14x ≡ 50 mod 45. Pero (2, 45) = 1, luego simplificando por 2, resulta 7x ≡ 25 mod 45. Pero 25 ≡ 70 mod 45, por tanto 7x ≡ 70 mod 45, adema´s (7, 45) = 1, lo que permite simplificar por 7, reducie´ndose a x ≡ 10 mod 45, 1.3. CONGRUENCIAS 33 lo que en te´rminos de divisibilidad se traduce en 45|(x− 10) de donde se recibe finalmente la ecuacio´n, x = 45k + 10, 0 ≤ k ≤ 44 considerada la solucio´n general. Si k = 0 se obtiene la solucio´n particular x = 10. Ejemplo 1.3.2. Resolver 3x ≡ 2 mod 78. Solucio´n. En la congruencia 3x ≡ 2 mod 78, (3, 78) = 3, pero 3 no divide a 2, por lo tanto no existe solucio´n. Ejemplo 1.3.3. Resolver 6x ≡ 10 mod 14. Solucio´n. (6, 14) = 2 y 2|10, entonces existen dos soluciones. Por el teorema 1.3.6, simplificando, 3x ≡ 5 mod 7. Como 5 ≡ 12 mod 7, entonces 3x ≡ 12 mod 7 de donde x ≡ 4 mod 7 porque (3, 7) = 1. En total se obtienen dos soluciones x ≡ 4 mod 7 x ≡ 4 mod 14 y al final las igualdades x = 7k + 4, 0 ≤ k ≤ 6 x = 14k + 4, 0 ≤ k ≤ 13. Para k = 1, se obtienen las soluciones respectivas, x = 11 y x = 18. Observe que 11 y 18 no son congruentes mo´dulo 14. 34 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA Algunas veces es de ma´s utilidad usar el algoritmo de la divisio´n para resolver congruencias como en el caso que presentamos a continuacio´n que por lo grande del mo´dulo y los coeficientes, los me´todos utilizados hasta ahora no son recomendables Ejemplo 1.3.4. Resolver 343x ≡ 15 mod 1426. Solucio´n. Como (343, 1426) = 1, existe una u´nica solucio´n. Aplicando el algoritmo de Euclides, 1426 = 343× 4 + 54 54 = 1426− 343× 4 343 = 54× 6 + 19 19 = 343− 54× 6 54 = 19× 2 + 16 16 = 54− 19× 2 19 = 16× 1 + 3 3 = 19− 16× 1 16 = 3× 5 + 1 1 = 16− 3× 5. A continuacio´n procedemos a expresar a 1 como una combinacio´n lineal de 343 y 1426. 1 = 16− 3× 5 = (54− 19× 2)− (19− 16× 1)5 = 54− 19× 7 + 16× 5 = 54− 19× 7 + (54− 19× 2)5 = 54× 6− 19× 17 = 54× 6− (343− 54× 6)17 = 54× 6− 343× 17 + 54× 102 = 54× 108− 343× 17 = (1426− 343× 4)108− 343× 17 = 1426× 108− 343× 432− 343× 17 = 1426× 108− 343× 449. 1.3. CONGRUENCIAS 35 Multiplicando por 15, el primero y el u´ltimo miembros, 15 = 1426(108× 15)− 343(449× 15). Multiplicando por (−1) esta u´ltima igualdad y transponiendo te´rminos se transforma en, 343(−449× 15)− 15 = 1426(−108× 15), expresio´n que traducida en te´rminos de congruencia significa 343(−449× 15) ≡ 15 mod 1426. Comparando esta congruencia con la original, debido al parecido de las ex- presiones se deduce que x ≡ −449× 15 mod 1426 de donde finalmente se puede escribir como consecuencia de la definicio´n x = −449× 15 + 1426k, 0 ≤ k ≤ 1425. Si k = 1, entonces x = −449× 15 + 1426 = −6735 + 1426 = −5309. Si k = 5, x = −6735 + 1426× 5 = −6735 + 7130 = 395, corresponde a la primera solucio´n positiva. EJERCICIOS 1. Demostrar el teorema 1.3.5. 36 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA 2. Resolver las siguientes congruencias, a) 3x ≡ 2 mod 5. b) 243x + 17 ≡ 101 mod 725. c) 5x ≡ 2 mod 7. d) 9x ≡ 21 mod 12. e) 6x + 3 ≡ 1 mod 10 . 3. Demostrar que si m es entero, m2 ≡ 0 o 1 mod 4. 4. Mostrar que la congruencia 6x ≡ 5 mod 78 no tiene solucio´n. 5. Usando el algoritmo de Euclides resolver las siguientes congruencias, a) 243x + 17 ≡ 101 mod 725. b) 3x ≡ 2 mod 5. c) 7x ≡ 21 mod 14. 6. Demostrar que para todo x, x3 ≡ x mod 3 y x5 ≡ x mod 5. 7. Demostrar que el discriminante b2 − 4ac ≡ 0 o 1 mod 4. 1.4. Criterios de divisibilidad Las congruencias hacen posible desarrollar los criterios de divisibilidad usados en Aritme´tica de los cuales se demostrara´n los ma´s usados. El primero es el Criterio de divisibilidad por 2. Ejemplo 1.4.1. Un entero es divisible por 2 si y solo si la cifra de sus unidades es un nu´mero par Solucio´n. Sea n un entero divisible por 2, n se puede escribir en forma u´nica como n = m∑ k=0 ak10 k pero 10 ≡ 2 mod 2, entonces por el teorema 1.3.4 m∑ k=0 ak10 k ≡ m∑ k=0 ak2 k mod 2 1.4. CRITERIOS DE DIVISIBILIDAD 37 por consiguiente n ≡ m∑ k=0 ak2 k mod 2 y como 2|n, 2 ∣∣∣∣ [ n− ( n− m∑ k=0 ak2 k )] . Iniciando la sumatoria con k = 1 y sumando a0, esta expresio´n se puede escribir en forma equivalente como, 2 ∣∣∣∣ [ m∑ k=1 ak2 k + a0 ] y su validez depende de ser a0 par, puesto que los restantes componentes son todos divisibles por 2. Si n es un entero terminado en cifra par se puede escribir n = 2k + m∑ k=1 ak10 k, 2k = a0, 0 ≤ k ≤ 4. Por la forma de representar a n, se concluye que debe ser par. Ejemplo 1.4.2. Un entero es divisible por 3 si y solo si la suma de sus d´ıgitos es un mu´ltiplo de 3. Solucio´n. Sea n un entero divisible por 3. 1k ≡ 10k mod 3 entonces m∑ k=0 ak10 k ≡ m∑ k=0 ak1 k mod 3 sustituyendo la sumatoria por n n ≡ m∑ k=0 ak1 k mod 3. 38 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA Por definicio´n de congruencia, 3 ∣∣∣∣ [ n− m∑ k=0 ak1 k ] Debido a que 3|n la propiedad (2) de divisibilidad y el reemplazo de n por la sumatoria permiten escribir, 3 ∣∣∣∣ [ m∑ k=0 ak10 k − ( m∑ k=0ak10 k − m∑ k=0 ak )] lo que conduce a afirmar que 3 ∣∣∣∣ m∑ k=0 ak. Supongamos que m∑ k=0 ak = 3c luego m∑ k=1 ak + a0 = 3c despejando, a0 = 3c− m∑ k=1 ak sumando, m∑ k=1 ak10 k + a0 = 3c + m∑ k=1 ak10 k − m∑ k=1 ak sustituyendo se obtiene n = 3c + m∑ k=1 ak ( 10k − 1) de donde se observa que 3|n, ya que 3|(10k − 1). 1.4. CRITERIOS DE DIVISIBILIDAD 39 Ejemplo 1.4.3. Un entero es divisible por 7 si y solo si, separando la cifra de las unidades, multiplica´ndola por 2, restando este producto de lo que queda a la izquierda y as´ı sucesivamente, el resultado es cero o un mu´ltiplo de 7. Solucio´n. Sea n un entero tal que m∑ k=1 ak10 k−1 − 2a0 = 7c multiplicando por 10 ambos miembros m∑ k=1 ak10 k − 20a0 = 70c sumando 21a0 a ambos lados, n = 70c + 21a0 o equivalentemente, 7|n. Realizando el proceso r veces m∑ k=r ak10 k−r + r−1∑ k=0 (−1)r−k2r−kak = 7t. Multiplicando por 10r ambos te´rminos, m∑ k=r ak10 k + r−1∑ k=0 (−1)r−k2r−kak10r = 7× 10rt. Sumando a ambos lados la expresio´n r−1∑ k=0 [ 10k − (−1)r−k2r−k10r]ak. Reorganizando te´rminos y factorizando se llega a la igualdad n = 7× 10rt + r−1∑ k=0 10k [ 1± (2× 10)r−k]ak. 40 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA En la expresio´n [1± (2× 10)r−k] se toma el signo ma´s si r − k es impar y el signo menos si r − k es par, 0 < r − k ≤ m. Pero 7|[1 + (2× 10)r−k] si r− k es impar e igualmente 7|[1− (2× 10)r−k] si r − k es par. Por lo visto 7|n. Suponga que n es divisible por 7, pero que m∑ k=1 ak10 k−1 = 7s + r, con 0 < r < 7. Siguiendo el procedimiento de los casos anteriores n = 70s + 21a0 + 10r, lo cual implica que 7 no divide a n, contradiciendo el supuesto. Para el caso general proceda de la misma manera. Ejemplo 1.4.4. Un entero es divisible por 11 si y solamente si la diferencia entre la suma de sus d´ıgitos de lugar impar y la suma de sus d´ıgitos de lugar par es cero o mu´ltiplo de 11. Solucio´n. Supongamos que n tiene un nu´mero impar de d´ıgitos y verifica la primera condicio´n n = 2m∑ k=0 ak10 k. Pero 10 ≡ −1 mod 11, lo que significa que 2m∑ k=0 ak10 k ≡ 2m∑ k=0 ak(−1)k mod 11. Aplicando un razonamiento similar al de las ocasiones precedentes mediante el uso de la propiedad (2) de divisibilidad se llega a 11 ∣∣∣∣ 2m∑ k=0 ak(−1)k de esta expresio´n se concluye 2m∑ k=0 a2k − m−1∑ k=1 a2k+1 = 11t. Igualdad que expresa la conclusio´n deseada y sera´ el punto de partida para demostrar la segunda parte. 1.4. CRITERIOS DE DIVISIBILIDAD 41 De la u´ltima igualdad, despue´s de efectuar algunas transformaciones es- cribimos a0 = 11t− m∑ k=1 a2k(−1)2k + m+1∑ k=0 a2k+1(−1)2k+1 agregando a ambos miembros de la ecuacio´n la expresio´n 2m∑ k=1 ak10 k se llega a la igualdad n = 11t + 2m∑ k=1 (102k − 1)a2k + m+1∑ k=0 (102t+1 + 1)a2k+1 factorizando el miembro de la derecha se obtiene n = 11t + m∑ k=1 (102k − 1)a2k + m+1∑ k=0 (102k+1 + 1)a2k+1. Pero 11|(102k − 1) y 11|(102k+1 + 1), por lo tanto 11|n. Si n tiene un nu´mero par de d´ıgitos se procede de semejante manera. Es necesario hacer notar que en la demostracio´n de los criterios de divisi- bilidad se asumio´ que n era un entero positivo a pesar de no hacer mencio´n ex- pl´ıcita de este hecho. Las propiedades de la divisibilidad as´ı lo justifican. EJERCICIOS 1. Demostrar: Un entero es divisible por 5 si y solo si termina en cero o en 5. 2. Demostrar: Un entero es divisible por 13 si y solo si separando la cifra de las unidades, multiplica´ndola por 9, restando este producto de lo que queda a la izquierda y as´ı sucesivamente, da cero o mu´ltiplo de 13. 3. Demostrar: Un entero es divisible por 17 si y solo si separando la cifra de las unidades, multiplica´ndola por 5, restando este producto por lo que queda a la izquierda, y as´ı sucesivamente da cero o mu´ltiplo de 17. 4. Demostrar: Un entero es divisible por 19, si y solo si, separando la cifra de las unidades, multiplica´ndola por 17, restando este producto de lo que queda a la izquierda, y s´ı sucesivamente, da cero o mu´ltiplo de 19. 42 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA 1.5. Sistemas de numeracio´n La invencio´n de un sistema de numeracio´n, que ahora luce tan natural costo´ mu- chos milenios a la humanidad. Los pueblos primitivos trajinaban con conjun- tos muy reducidos y los valoraban o comparaban sin necesidad de conocer los nombres de sus objetos. El gran descubrimiento fue hallar un procedimiento para nombrar y re- presentar todos los nu´meros con un conjunto reducido de palabras y s´ımbo- los que es el objetivo de cualquier sistema de numeracio´n. La mayor´ıa de los sistemas de numeracio´n tienen su fundamento en un nu´mero clave lla- mado base del sistema, que en el sistema decimal es el 10. Los s´ımbolos, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 se denominan d´ıgitos cuando se usan para representar enteros. El sistema decimal se desarrollo´ en la India, pero fue introducido en Europa por los a´rabes con motivo de la invasio´n efectuada por estos u´lti- mos al continente, por esta razo´n se le conoce como hindu´-ara´bico, pero ma´s popularmente como sistema ara´bico de numeracio´n. Cada entero t mayor que 1 puede servir de base para un sistema de numeracio´n. Escogemos s´ımbolos arbitrarios para representar los d´ıgitos, esto es los elementos, 0, 1, 2, 3, 4, . . . , (t− 1). Y sustituimos el nu´mero n = m∑ k=0 akt k por el s´ımbolo n = amam−1am−2 · · ·a1a0(t. Si la base es mayor que 10 debemos buscar s´ımbolos para sustituir los d´ıgitos mayores que 9. Por ejemplo para la base 12, hacemos 10 = α, 11 = β. As´ı las cosas en dicha base podemos escribir nu´meros tales como 507β34, 87α35, 4129, β03, y as´ı sucesivamente. Siempre se ha pensado que el sistema duodecimal ser´ıa muy pra´ctico porque 12 tiene ma´s divisores primos que 10 y se puede agrupar mejor por docenas que por decenas, pero esta inquietud se ha reducido al campo de las especulaciones. Lo cierto es que el sistema decimal esta´ muy adherido al desarrollo de la humanidad. El sistema binario o los de potencias de 2 han sido popularizados por las computadoras. La tecnolog´ıa de estos artefactos esta´ basada en los co´digos de verdadero-falso, apagado-encendido. El sistema binario esta´ conformado por los d´ıgitos 0, 1, lo que constituye una aparente desventaja debido a que se necesita una cantidad grande de d´ıgitos binarios 1.5. SISTEMAS DE NUMERACIO´N 43 para escribir cualquier nu´mero, por ejemplo 1325 = 10100101101. Pero la aparente desventaja se traduce en versatilidad. 1.5.1. Cambio de bases 1. Paso de un nu´mero escrito en una base cualquiera t a la base decimal. Sea t > 1 una base cualquiera, n un nu´mero escrito en dicha base n = m∑ k=0 akt k con 0 ≤ ak ≤ (t− 1) para 0 ≤ k ≤ m esta igualdad proporciona una regla pra´ctica para escribir el nu´mero n en base 10. Primero desarrollamos todas las potencias de t, desde la cero hasta la m-e´sima, despue´s efectuamos todos los productos y por u´ltimo procedemos a sumarlos. Si realizamos las operaciones en base 10 el resultado sera´ la representacio´n de n en base decimal. Ejemplo 1.5.1. Escribir en base 10 el nu´mero 2αβ12. Las tres primeras potencias de 12 son 1, 12, 144. 2αβ12 = 2× 144 + 10× 12 + 11× 1 = 288 + 120 + 11 = 419. 2. Paso de un nu´mero escrito en base 10 a una base cualquiera. Sea t > 1 una base cualquiera, n un nu´mero escrito en base 10 y sea n = amam−1am−2 · · ·a1a0(t la expresio´n de n en base t. n = m∑ k=0 akt k = m∑ k=1 akt k + a0. Del tercer miembro y teniendo en cuenta que los valores absolutos de los d´ıgitos son siempre menores que la base se deduce que si dividimos n por t 44 CAPI´TULO1. TEORI´A DE LA ARITME´TICA se obtiene un cociente q1 y a0 de residuo, es decir, el residuo corresponde al primer d´ıgito leyendo de derecha a izquierda. m∑ k=1 akt k = m∑ k=2 akt k + a1. De esta igualdad observamos que si dividimos por segunda vez por t ob- tenemos nuevos cocientes y residuos q2 y a1 respectivamente, residuo que corresponde al segundo d´ıgito leyendo en el mismo orden. Despue´s de rei- teradas operaciones llega un momento en que se obtienen por cociente y residuo finales am y am−1 respectivamente, nu´meros que corresponden a los dos u´ltimos d´ıgitos de n en base t. Las operaciones anteriores se pueden representar en un gra´fico as´ı: . . . . . . n t a0 q1 t ta1 q2 qm−2 tam−3 am−2 qm−1 t am−1 am Figura 1.1 Este gra´fico nos dice que para pasar de un nu´mero escrito en base 10 a una base cualquiera t dividimos el nu´mero dado (operando en base 10) sucesiva- mente por t hasta que lleguemos a un cociente menor que la base y despue´s tomamos el u´ltimo cociente y todos los residuos encontrados pero en sentido retro´grado y estos valores sera´n las cifras del nu´mero de izquierda a derecha. Hay que notar que si t es mayor que 10 los residuos pueden ser 10 o ma- yores y entonces tenemos que sustituir esos residuos por los s´ımbolos que le corresponden en ese sistema. Ejemplo 1.5.2. Escribir en base 12 el nu´mero 15135510. 1.5. SISTEMAS DE NUMERACIO´N 45 Solucio´n. Tome 10 = α, 11 = β. Efectuando las divisiones sucesivas 151355 = 12× 12612 + 11 12612 = 12× 1051 + 0 1051 = 12× 87 + 7 87 = 12× 7+ 3. El nu´mero escrito en base 12 es 7370β12. Ejemplo 1.5.3. Escribir en base 5 el nu´mero 7210. Solucio´n. 72 = 5× 14 + 2 14 = 5× 2+ 4. La respuesta es 2425. 1.5.2. Operaciones en base cualquiera Un procedimiento para operar nu´meros en cualquier base (pero todos en la misma) ser´ıa pasarlos a la base 10, efectuar las operaciones y el resultado devolverlo luego a la base original. Para cantidades pequen˜as otro me´todo consiste en operar en la base res- pectiva teniendo el cuidado de recordar que opera en base diferente a la decimal con el fin de evitar equ´ıvocos. Cuando hay que realizar muchas ope- raciones lo mejor es utilizar una tabla. La tabla de sumar Para construir una tabla de sumar, que puede utilizarse para restar, se escribe en fila la sucesio´n de los nu´meros hasta donde se quiera, pero por lo menos hasta agotar los d´ıgitos. Debajo de esa primera fila se escriben los mismos nu´meros agregados en la unidad, la tercera sera´ igual a la segunda ma´s la unidad y as´ı sucesivamente. Para sumar dos nu´meros se toma uno en la primera columna y el otro en la primera fila y la suma estara´ en la interseccio´n de la columna y fila que encabezan los sumandos, aunque la propiedad conmutativa permite tomarlos sin importar cua´l se toma en la fila y cua´l en la columna. A continuacio´n se construye una tabla de sumar en base 5. 46 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA + 1 2 3 4 10 11 12 13 14 20 21 1 2 3 4 10 11 12 13 14 20 21 22 2 3 4 10 11 12 13 14 20 21 22 23 3 4 10 11 12 13 14 20 21 22 23 24 4 10 11 12 13 14 20 21 22 23 24 30 10 11 12 13 14 20 21 22 23 24 30 31 11 12 13 14 20 21 22 23 24 30 31 32 12 13 14 20 21 22 23 24 30 31 32 33 Figura 1.2 Ejemplo 1.5.4. Sumar: 11112 + 10102 + 1102 + 111012. Solucio´n. Tomando las primeras cifras de derecha a izquierda (unidades) y operando en base dos, 1 + 0 + 0 + 1 = 1 + 1 = 10. Escribo 0 en la primera posicio´n del resultado y traslado 1 a la segunda posicio´n. Tomando las cifras de la segunda posicio´n ma´s 1 que traslado se obtiene. 1 + (1 + 1 + 1 + 0) = 1 + (11) = 100. Escribo 0 en la segunda posicio´n y traslado 10 a la tercera. Tomando las cifras de la tercera posicio´n ma´s 10 se escribe, 10 + (1 + 0 + 1 + 1) = 10 + (11) = 101. Escribo 1 en la tercera posicio´n y traslado 10 a la cuarta. Tomando las cifras de la cuarta posicio´n ma´s 10, se tiene, 10 + (1 + 1 + 0 + 1) = 10 + 11 = 101. Escribo 1 en la cuarta y traslado 10 a la quinta . Tomando las cifras de la quinta posicio´n ma´s 10, se obtiene 10 + (0 + 0 + 0 + 1) = 11 cifra que corresponde al u´ltimo resultado. Finalmente, escribiendo de izquier- da a derecha se obtiene el total: 1111002. Escribiendo la suma en forma compacta, 1.5. SISTEMAS DE NUMERACIO´N 47 1 1 1 1 1 0 1 0 + 1 1 0 1 1 1 0 1 1 1 1 1 0 0 Ejemplo 1.5.5. Efectuar la diferencia 220237 – 46257. Solucio´n. Tomando el desarrollo polino´mico de 22023 en base siete 22023 = 2×74+2×73+0×72+2×7+3 = 1×74+11×73+6×72+11×7+13. Recuerde que estamos haciendo un desarrollo en base 7. El desarrollo polino´mico de 4625 es, 4625 = 4× 73 + 6× 72 + 2× 7 + 5. Ahora basta con efectuar las respectivas restas as´ı, 13− 5 = 5 11− 2 = 6 6− 6 = 0 11− 4 = 4 1− 0 = 1. Tomando los resultados en orden ascendente y escribie´ndolos de izquierda a derecha la respuesta obtenida es, 140657. En forma compacta 2 2 0 2 3 – 4 6 2 5 1 4 0 6 5 La tabla de multiplicar La tabla de multiplicar que tambie´n sirve para dividir se construye escribien- do la sucesio´n de los nu´meros de la base en el sistema en referencia a partir 48 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA de 1. En la segunda fila en correspondencia con la primera se escribe el resul- tado de sumar la primera fila consigo misma. La tercera se obtiene sumando la segunda con la primera. La cuarta es el resultado de sumar la primera con la tercera y as´ı sucesivamente cada nueva fila se obtiene sumando la primera con la u´ltima obtenida. Para hallar el producto de dos nu´meros se toman los factores se procede en forma similar a la suma. La siguiente es una tabla de multiplicar en base cinco × 1 2 3 4 10 11 12 13 14 20 21 1 1 2 3 4 10 11 12 13 14 20 21 2 2 4 10 13 20 22 24 31 33 40 42 3 3 11 13 22 30 33 41 44 102 110 113 4 4 13 21 31 40 44 103 112 121 130 134 10 10 20 24 40 100 110 120 130 140 200 210 11 11 22 32 44 110 121 132 143 204 220 231 12 12 24 40 103 120 131 144 211 223 240 302 Figura 1.3 Ejemplo 1.5.6. En base 4 se opera de manera semejante a la base 10, exa- minemos el siguiente producto: Solucio´n. Se dispone el producto de manera ordinaria. 1 0 2 1 3 × 2 2 1 1 0 2 1 3 2 1 0 3 2 2 1 0 3 2 2 3 3 0 3 3 3 El resultado es 23303334. Finalmente se da solucio´n a la siguiente divisio´n en base cinco. Ejemplo 1.5.7. Dividir 231245 entre 325. Solucio´n. La operacio´n se dispone as´ı: 1.5. SISTEMAS DE NUMERACIO´N 49 2 3 1 ′ 2 ′ 4 ′ 3 2 −2 0 1 3 4 2 1 4 4 3 0 2 −2 3 3 −1 1 4 3 0 El algoritmo se desarrolla de la siguiente forma. Se toman las tres primeras cifras de la izquierda del dividendo, esto es, 231. El nu´mero que multiplicado por 32 se aproxima ma´s a 231 es 3. Se multiplica 32 por 3. 32× 3 = 201. Se efectu´a la diferencia 231− 201 = 30. A 30 se le agrega la cuarta cifra del dividendo, obtenie´ndose 302. El nu´mero que multiplicado por 32 se aproxima ma´s a 302 es 4. Se multiplica 32 por 4. 32× 4 = 233. Se realiza la diferencia 302− 233 = 14. Tomando la u´ltima cifra del dividendo, 4 y agrega´ndola a 14 se obtiene 144. El nu´mero que multiplicado por 32 se aproxima ma´s a 144 es 2. Multiplicando 32 por 2. 32× 2 = 114. La diferencia 144− 114 = 30 produce el residuo 30. El cociente es 3425. Los enteros obtenidos mediante las diferentes bases son equivalentes, por ejemplo las igualdades 125 + 205 = 325 710 + 1010 = 1710 213 + 1013 = 1223 50 CAPI´TULO 1. TEORI´A DE LA ARITME´TICA conducen a resultados correspondientes. Estas correspondencias se dice que son isomorfismos y a las estructuras se les denomina isomorfas. EJERCICIOS 1. Construir tablas de adicio´n y multiplicacio´n para las siguientes bases: 2, 3, 4, 5, 6, 7, 8, 9, 11, 12. 2. Usando las tablas del ejercicio anterior, evaluar: a) 110112 + 10012 + 112
Compartir