Cap´ıtulo

2 Congruencias 2.1

Definiciones b´ asicas

Definici´ on 2.1.1 Sea m un entero fijo, diremos que dos enteros a y b son congruentes m´ odulo m , y usamos la notaci´on a ≡ b mod m si y s´olo si m divide a a − b Ejemplo: 25 ≡ 4 mod 7, pues 7 divide a 25 - 4 = 21. Observaci´ on: Podemos decir que a es congruente a b m´odulo m si existe un entero k, tal que a = b + km. Tambi´en se puede definir congruencia, usando el concepto de pertenencia. M´as precisamente a es congruente a b m´odulo m si y s´olo si a est´a en la sucesi´on de enteros . . . , b − m, b, b + m, b + 2m, . . . Cuando a y b no son congruentes m´odulo m, diremos que son incongruentes y lo denotaremos por a 6≡ b mod m. La notaci´on de congruencias fue introducida por Gauss en su libro Disquisitions Arithmeticae, en 1799. Gauss desarroll´o gran parte de la teor´ıa de congruencias, plante´o muchos problemas interesantes sobre este tema y resolvi´o algunos de ellos. Uno de los m´as importantes fue la resoluci´on de la ecuaci´on cuadr´atica de congruencias. La noci´on de congruencia se utiliza a diario para medir el tiempo. Por ejemplo las horas del d´ıa se cuentan m´odulo 24, los d´ıas de la semana se cuentan m´odulo 7 , etc... En lo sucesivo, m ser´a un entero positivo fijo. 33

34

Cap´ıtulo 2. Congruencias

Teorema 2.1.1 Sean a, b y c enteros cualesquiera. Entonces se tiene 1. a ≡ a mod m 2. Si a ≡ b mod m, entonces b ≡ a mod m. 3. Si a ≡ b mod m, y b ≡ c mod m, entonces a ≡ c mod m. Demostraci´ on: 1) Notemos que m divide a a − a = 0, luego a ≡ a mod m. 2) Se tiene que m divide a b − a, por hip´otesis, luego m| − (b − a), y por lo tanto m | a − b. 3) Por hip´otesis se tiene m | b−a y m | c−b. Luego m | (b−a)+(c−b), esto es m | c − a. Por lo tanto a ≡ c mod m. ♠ Observaci´ on: Las tres propiedades anteriores para la relaci´on de congruencia, nos indican que ´esta es una relaci´on de equivalencia (Ver Cap´ıtulo 1). Como resultado de esto, se obtiene una partici´on en el conjunto de los enteros en clases de equivalencia disjuntas, las cuales llamaremos clases de congruencia m´ odulo m. Definici´ on 2.1.2 Sea a un entero cualquiera, entonces la clase de congruencia de a m´odulo m, es el conjunto [a] = {x entero | x ≡ a mod m} El entero a en la definici´on anterior se llama el representante de la clase y puede ser elegido arbitrariamente de entre los elementos de la clase: esto es, si b ≡ a mod m entonces [a] = [b]. Ejemplo: Si se considera la relaci´on de congruencia m´odulo 7, se tendr´a entonces: [0] = {. . . , −14, −7, 0, 7, 14, . . .} [1] = {. . . , −13, −6, 1, 8, 15, . . .}

2.1. Definiciones b´ asicas

35

[2] = {. . . , −12, −5, 2, 9, 16, . . .} .. . [6] = {. . . , −8, −1, 6, 13, 20, . . .} Ejemplo:. Las horas. Para contar el tiempo en un mismo d´ıa, usamos las horas. Un d´ıa tiene 24 horas exactas y para contar las horas comenzamos por la hora 1, que es cuando comienza el d´ıa. T´ecnicamente, el d´ıa comienza en un instante 0 y contando 12 horas a partir de ese instante, el sol se hallar´a en la posici´on m´as alta del firmamento. As´ı pues, la primera hora comienza en el instante 0, la segunda despu´es de una hora, . . . y as´ı sucesivamente hasta la hora 24. Al finalizar la hora 24 comienza un nuevo d´ıa y aqu´ı reiniciamos el conteo de las horas. Es decir contamos las horas m´odulo 24. Por ejemplo, si en este momento son las 8 p.m. ¿Qu´e hora ser´a dentro de 200 horas? Soluci´ on: En primer lugar, si x es la hora buscada, debemos tener x ≡ 20 + 200 mod 24 luego podemos reducir el lado derecho de esta ecuaci´on “m´odulo 24”. As´ı se obtiene x ≡ 4 mod 24 Luego la hora x ser´a las 4 a.m.

36

Cap´ıtulo 2. Congruencias

Ejercicios 1) Probar que las tres definiciones de la noci´on de congruencia, dadas al comienzo, son equivalentes. 2) Si hoy es jueves, entonces ¿que d´ıa de la semana ser´a ... a) dentro de 20 d´ıas?, b) dentro de 100 d´ıas ? 3) Indicar cu´ales de las siguientes afirmaciones son correctas y cu´ales son falsas 1. 18 ≡ 1 mod 5 2. 86 ≡ 1 mod 5 3. 100 ≡ 10 mod 9 4. 62 6≡ 2 mod 8 5. 103 ≡ 1 mod 9 6. 2a ≡ 6 mod 2 7. s2 + s + 1 ≡ 1 mod 2 8. a(a + 1)(a + 2) ≡ 0 mod 3 4) Probar que si a ≡ b mod m, entonces a ≡ b mod k, para todo k divisor de m. ¿Ser´a cierto el rec´ıproco de este resultado? Dar un contraejemplo. 5) Si hoy es jueves 27 de octubre de 1993, entonces ¿que d´ıa de la semana ser´a el 27 de octubre de 1994? Use congruencias para hallar el resultado.

2.2. Propiedades de las Congruencias

2.2

37

Propiedades de las Congruencias

A continuaci´on damos una serie de propiedades de las congruencias, relacionadas con la suma y el producto de n´ umeros enteros. Teorema 2.2.1 Si a ≡ b mod m, y c es un entero, se tiene 1. a + c ≡ b + c mod m. 2. ac ≡ bc mod m Demostraci´ on: 1) Si a ≡ b mod m, se tendr´a entonces m | b − a . Luego m | (a + c) − (b + c), y de aqu´ı obtenemos a + c ≡ b + c mod m 2) Se tiene m | a − b, y por lo tanto m | (a − b)c . Luego m | ab − ac, lo cual implica ac ≡ bc mod m. ♠ Ejemplo: La ecuaci´on de congruencia 1 ≡ 10 mod 9, se puede multiplicar por 30, para obtener 30 ≡ 300 mod 9. Observaci´ on: El rec´ıproco del teorema anterior no es cierto en general. Es decir de la congruencia ca ≡ cb mod m no se puede inferir a ≡ b mod m. Por ejemplo 12 ≡ 6 mod 6, pero 6 6≡ 3 mod 6. Seguidamente, daremos un par de propiedades mediante las cuales podemos multiplicar y sumar ecuaciones de congruencias, de la misma forma como se hace para las ecuaciones normales. Teorema 2.2.2 Sean a, b y c enteros con a ≡ b mod m Entonces se tiene

y

c ≡ d mod m.

38

Cap´ıtulo 2. Congruencias

1. a + c ≡ b + d mod m 2. ac ≡ bd mod m Demostraci´ on: 1) Si a ≡ b mod m, entonces existe un entero k tal que a = b + km. Igualmente de c ≡ d mod m, se obtiene un entero h, tal que c = d+hm. Luego a + c = b + d + (h + k)m y de aqu´ı se sigue que: a + c ≡ b + d mod m. 2) Tambi´en tenemos ac = (b + km)(d + hm) = bd + (bh + dk + hkm)m y de esto se sigue que ac ≡ bd mod m.

♠

Teorema 2.2.3 (Congruencia de Polinomios) Sea f (x) = cn xn + cn−1 xn−1 + . . . + c1 x + c0 , un polinomio con coeficientes enteros. Entonces si a ≡ b mod m se tendr´ a: f (a) ≡ f (b) mod m. Demostraci´ on: Partiendo de la congruencia a ≡ b mod m, y aplicando el teorema anterior parte 2) tantas veces como se desee, deducimos ai ≡ bi mod m para todo 1 ≤ i ≤ n.

2.3. Cronolog´ıa

39

Multiplicando cada ecuaci´on por su respectivo coeficiente nos da ci ai ≡ ci bi mod m Finalmente, podemos sumar todas estas ecuaciones, gracias al teorema 2.2.1 parte 1), para obtener el resultado deseado cn an + . . . + c1 a + c0 ≡ cn bn + . . . + c1 b + c0 mod m luego, hemos probado f (a) ≡ f (b) mod m.

2.3

Cronolog´ıa

En esta secci´on estudiaremos algunas aplicaciones de las congruencias en la cronolog´ıa, como por ejemplo la determinaci´on del d´ıa de la semana de una fecha determinada.

El Calendario Gregoriano El origen de nuestro calendario actual se encuentra en el Calendario Juliano, llamado as´ı por Julio C´esar, quien particip´o activamente en el dise˜ no de ´este. En dicho calendario cada a˜ no constaba de 365 d´ıas y cada cuatro a˜ nos hab´ıa un a˜ no bisiesto de 366 d´ıas. El calendario de 12 meses comenzaba en el mes de Marzo y finalizaba en Febrero. El nombre y duraci´on de los meses era el siguiente: Nombre del mes Marzo Abril Mayo Junio Quinto Sexto Septiembre Octubre Noviembre Diciembre Enero Febrero

No. de d´ıas Nombre en Lat´ın 30 Martius 30 Aprilis 31 Maius 30 Junius 31 Quintilis 31 Sextilis 30 Septembris 31 Octobris 30 Novembris 31 Decembris 31 Januaris 28 Februarius

40

Cap´ıtulo 2. Congruencias

Durante el tiempo de C´esar el mes quinto cambi´o de nombre por julio, en honor a este emperador. M´as tarde, el mismo Julio C´esar decidi´o que el a˜ no deber´ıa comenzar en enero. De esta manera qued´o organizado el calendario sin sufrir ninguna modificaci´on hasta la reforma del Papa Gregorio XIII en 1582. Los a˜ nos eran numerados de acuerdo al per´ıodo de cada emperador, hasta el triunfo del cristianismo, cuando se comenz´o a enumerarlos en forma diferente. A partir de entonces, el a˜ no 1 fue el nacimiento de Cristo y el d´ıa de Navidad el primer d´ıa de la Era Cristiana, luego los a˜ nos se cuentan en sucesi´on creciente, partiendo desde este inicio. Esta reforma fue hecha en el 533 d.c. durante el per´ıodo del Emperador Dionisio Exigus. Una de las motivaciones que han tenido todos los pueblos en el momento de establecer un calendario, es la de ubicar correctamente las fiestas religiosas. As´ı observamos que en el Calendario Cristiano, el Domingo de Pascua determina las otras fechas movibles como la Ascensi´on y el Corpus Cristi. Durante el Concilio de Nicea en el 325 d.c. se acord´o fijar esta fecha, como el primer domingo despu´es de luna nueva que aparezca en el Equinoccio de Primavera (21 de Marzo) o despu´es . Si la luna nueva aparece un domingo, entonces el Domingo de Pascua ser´a el domingo siguiente. Si bien el Calendario Juliano funcion´o bien durante algunos siglos, la celebraci´on de una Semana Santa a fines del siglo XVI, en donde el Domingo de Pascua correspondi´o al 11 de Marzo, hizo pensar a muchos que este calendario estaba lejos de ser perfecto. Veamos el por qu´e de semejante error y las rectificaciones que se le hicieron a el mismo, a fin de ajustarlo al tiempo sideral. El a˜ no astron´ omico, una revoluci´on completa de la tierra alrededor del sol, es de 365 d´ıas, 6 horas, 9 minutos y 9.5 segundos. Sin embargo el a˜ no visible o a˜ no tropical, per´ıodo entre dos equinoccios de primavera, es m´as corto: 365 d´ıas, 5 horas, 48 minutos y 46.43 segundos. El Calendario Juliano supon´ıa que el a˜ no ten´ıa 365 d´ıas y un cuarto, lo cual excede en 11 minutos y 14 segundos al a˜ no tropical. Como consecuencia de esto, se comete un error de un d´ıa cada 128 a˜ nos.

2.3. Cronolog´ıa

41

A fin de corregir este error, el Papa Gregorio XIII introdujo una reforma en el calendario, mediante la cual se eliminaron 10 d´ıas de la historia . Se decidi´o que el d´ıa siguiente al 4 de octubre de 1582, fuese el 15 de octubre. Adem´as se redujeron los a˜ nos bisiestos mediante la siguiente convenci´on. Los a˜ nos bisiestos seculares (divisibles por 100) ser´ıan s´olo aquellos divisibles por 400. As´ı, por ejemplo 1800 y 1900 no son bisiestos, pero 2000 ser´a bisiesto. Esta reforma del Calendario Juliano se conoce con el nombre de Calendario Gregoriano y es el calendario que se ha venido usando hasta el presente. Una vez hecha esta exposici´on de nuestro calendario, pasemos a calcular los d´ıas de la semana de algunas fechas hist´oricas importantes. N´otese la importancia de las congruencias, en cuanto a su capacidad de simplificar los c´alculos considerablemente. Ejemplo: ¿Que d´ıa de la semana fue el 19 de abril de 1810? Soluci´ on: En primer lugar, calculamos el n´ umero de a˜ nos bisiestos entre 1993 y 1810. Vemos que 1812 fue bisiesto y cien a˜ nos m´as tarde 1912 ocurrieron 25 a˜ nos bisiestos (descontamos a 1900 que no fue bisiesto). Entre 1912 y 1993 hay 20 a˜ nos bisiestos, lo cual da un total de 45 a˜ nos bisiestos desde 1810 hasta 1993. Luego calculamos el desfase entre ambos a˜ nos relativo a los d´ıas de la semana. En otras palabras nos interesa la diferencia x en d´ıas desde 1810 hasta 1993 m´odulo 7. Usando congruencias tenemos: 365 ≡ 1 mod 7 Multiplicando por el n´ umero de a˜ nos transcurridos 183(365) ≡ 183 mod 7 ≡ 1 mod 7 luego, despu´es de agregar todos los d´ıas adicionales, producto de los a˜ nos bisiestos, tenemos:

42

Cap´ıtulo 2. Congruencias

x ≡ 45 + 1 mod 7 ≡ 46 mod 7 ≡ 4 mod 7 Por lo tanto hay un desfase de 4 d´ıas en el almanaque del a˜ no 1810 con respecto al a˜ no 1993. Por comodidad, este desfase lo haremos positivo, −4 ≡ 3 mod 7. Luego el desfase ser´a de tres d´ıas contando los d´ıas hacia adelante en el tiempo. Para terminar de resolver el problema, miramos el almanaque de 1993 y vemos que el 19 de abril fue lunes. Luego el 19 de abril de 1810 fue jueves. De la misma forma como hallamos el d´ıa de la semana correspondiente al 19 de abril de 1810, podemos determinar cualquier d´ıa de otra fecha en ese a˜ no. Basta ubicar la fecha correspondiente en el almanaque de 1993, y entonces agregar tres d´ıas m´as. Es decir, el desfase x da toda la informaci´on necesaria. Daremos los desfases para los a˜ nos en el per´ıodo de vida del Libertador Sim´on Bol´ıvar.

Tabla Cronol´ ogica 1783 6 1793 4 1803 1 1813 7 1823 5

1784 1 1794 5 1804 3 1814 1 1824 7

1785 2 1795 6 1805 4 1815 2 1825 1

1786 3 1796 1 1806 5 1816 4 1826 2

1787 5 1797 2 1807 6 1817 5 1827 3

1788 6 1798 3 1808 1 1818 6 1828 5

1789 7 1799 4 1809 2 1819 7 1829 6

1790 1 1800 5 1810 3 1820 2 1830 7

1791 3 1801 6 1811 4 1821 3

1792 4 1802 7 1812 6 1822 4

2.4. Trucos de divisibilidad

43

Ciclos Lunares El ciclo lunar o ciclo met´onico, es un per´ıodo igual a 19 a˜ nos solares. La raz´on de esto se debe al astr´onomo griego Meton (siglo 5 a.c.), quien descubri´o que 19 a˜ nos solares son iguales a 235 meses lunares. El mes lunar o mes sin´ odico, es el intervalo de tiempo entre dos conjunciones consecutivas del sol y la luna (4 fases lunares). Este tiene una duraci´on de 29 d´ıas, 12 horas y 44 minutos. En la Iglesia Cristiana hubo necesidad de introducir el ciclo lunar dentro del Calendario, debido a la determinaci´on del Domingo de Pascua, el cual depende de la luna llena, como ya hemos explicado. Los a˜ nos del ciclo met´onico se llaman a˜ nos dorados. El primer a˜ no de un ciclo es aquel en que las fases lunares del mes de enero de dicho a˜ no comienzan el 24 de diciembre. As´ı, por ejemplo en el a˜ no 1 de la Era Cristiana se inici´o un ciclo met´onico. Luego en a˜ no 1 d.c. tiene n´ umero dorado 1, el a˜ no 2 d.c. tiene n´ umero dorado 2 ,..etc. Luego el a˜ no 20 tiene n´ umero de oro 1, y asi sucesivamente. La regla para calcular el n´ umero de oro t, de un a˜ no x cualquiera es: t ≡ x + 1 mod 19 Por ejemplo 1993 tiene n´ umero de oro 18, pues 1993 + 1 = 1994 ≡ 18 mod 19

2.4

Trucos de divisibilidad

Existen criterios pr´acticos para decidir cu´ando un n´ umero es divisible entre 3,9, 11,· · · etc. Todos estos criterios est´an basados en las congruencias y son f´aciles de interpretar, una vez vistos los resultados previos, en donde se estudiaron las reglas de manipulaci´on de ecuaciones de congruencias.

44

Cap´ıtulo 2. Congruencias

Criterio de divisibilidad entre nueve Proposici´ on 2.4.1 Un n´ umero x es divisible entre nueve si y s´olo si la suma de sus d´ıgitos es divisible entre nueve. Demostraci´ on: En primer lugar notemos que 10 ≡ 1 mod 9 Multiplicando esta ecuaci´on por s´ı misma tantas veces como se desee 10i ≡ 1 mod 9 para todo 1 ≤ i. Sea ahora x un n´ umero positivo cualquiera. Entonces x tiene una descomposici´on decimal, y por lo tanto existen enteros ci , 0 ≤ i ≤ n, tales que x = cn 10n + . . . c1 10 + c0 donde 0 ≤ ci ≤ 9, para todo i. Luego x = cn 10n + . . . + c1 10 + c0 ≡ cn + . . . + c1 + c0 mod 9 Como consecuencia de lo anterior, hemos demostrado que x es congruente m´odulo 9 a la suma de sus d´ıgitos. Entonces x es un m´ ultiplo de 9 si y s´olo si la suma de sus d´ıgitos lo es. Ejemplo: El entero 1575 es divisible entre 9, pues 1 + 5 + 7 + 5 = 18 = 2 × 9.

Criterio de divisibilidad entre 3 Proposici´ on 2.4.2 Un n´ umero es divisible entre 3 si y s´olo si la suma de sus d´ıgitos es divisible entre 3.

2.4. Trucos de divisibilidad

45

Veamos ahora otra aplicaci´on pr´actica de las congruencias, en la obtenci´on de un viejo truco para verificar el resultado de una multiplicaci´on, llamado Eliminaci´ on de los Nueve. Si se multiplican dos n´ umeros a y b, para obtener un resultado c, entonces daremos un m´etodo para verificar si c es el resultado correcto. Este m´etodo falla en un 10 por ciento de los casos, pero sin embargo es apropiado para esta tarea, debido a la simplicidad del mismo.

Eliminaci´ on de los nueve Proposici´ on 2.4.3 Si en la multiplicaci´ on de a por b se obtiene un entero c, entonces al sumar los d´ıgitos de cada una de los tres n´ umeros 0 0 0 0 se obtienen enteros a , b y c , los cuales deben satisfacer: a × b0 = c0 . Daremos un ejemplo pr´actico para ilustrar este m´etodo. 786 x219 172134

7 + 8 + 6 = 21 2 + 1 + 9 = 12 1 + 7 + 2 + 1 + 3 + 4 = 18

2+1=3 3 1 + 2 = 3 x3 1+8=9 9

La prueba de la proposici´on, es una consecuencia del criterio de divisibilidad entre nueve, pues a ≡ a0 mod 9 y b ≡ b0 mod 9, Luego se tiene ab ≡ a0 b0 mod 9 o sea c ≡ c0 mod 9.

46

Cap´ıtulo 2. Congruencias

Ejercicios 1) Hallar criterios de divisibilidad para 2 y 5. Justificarlos. 2) Hallar y probar un criterio de divisibilidad para 11. 3) Hallar y probar un criterio de divisibilidad para 7. 4) Existe un m´etodo para multiplicar, que fue muy popular en Europa durante la Edad Media, en el cual s´olo se requiere la tabla de multiplicaci´on hasta el n´ umero cinco. Supongamos que queremos multiplicar 7 por 8. Entonces la diferencia de 8 con 10 es 2 y la diferencia de 7 con 10 es 3. Multiplicando ambas diferencias nos da: 2 × 3 = 6. Este es el primer d´ıgito del resultado. Luego a 7 se le resta la diferencia del 8 (o bien a 8 se le resta la diferencia de 7) y en cualquiera de los dos casos nos da 7-3 = 8-2 = 5 . Este es el otro d´ıgito del n´ umero buscado. Podemos ilustrar este algoritmo, mediante el diagrama:

Dar una demostraci´on de este algoritmo. 5) Demuestre que el almanaque se repite cada 28 a˜ nos. 6) Usando la tabla cronol´ogica hallar los d´ıas de la semana de las fechas siguientes. a) 25 de marzo de 1.815 b) 6 de enero de 1.799 c) 24 de diciembre de 1803 7) Demostrar que el error cometido al medir el tiempo con el Calendario Juliano es de un d´ıa cada 128 a˜ nos. 8) Calcular el error que se comete al medir el tiempo con el Calendario Gregoriano.

2.5. Clases de congruencias

47

9) Usando el truco de eliminaci´on de los nueve, verificar las operaciones siguientes. a) 1.254 × 456 = 571.824 b) 6.532 × 123 = 893.436 c) 1.223 × 362 = 442.626 d) 125 × 337 = 41.125 10) Hallar el valor de x que satisfaga a) x2 ≡ −1 mod 7 b) 2x ≡ 1 mod 5 c) x3 + 4x − 1 ≡ 0 mod 7

2.5

Clases de congruencias

Hemos visto que para un n´ umero positivo m fijo, la relaci´on m´odulo m en el conjunto de enteros es de equivalencia. En esta secci´on, veremos c´omo se puede dotar al conjunto de las clases de congruencias de una estructura algebr´aica. Supondremos que el lector est´a familiarizado con los conceptos de operaci´ on binaria, grupo y anillo . De cualquier forma, daremos un breve repaso a estos conceptos con la finalidad de hacer esta secci´on autocontenida. Definici´ on 2.5.1 Sea A un conjunto no vac´ıo. Una operaci´ on binaria en A es una ley que asocia a cada par de elementos (a, b) de A × A otro elemento de A el cual ser´a denotado por a ∗ b. Esto se simboliza por ∗ : A × A −→ A (a, b) −→ a ∗ b Definici´ on 2.5.2 Un Grupo es un conjunto no vac´ıo G, el cual est´a dotado de una operaci´ on binaria ∗, la cual satisface 1. Para a y b en G, a ∗ b est´ a en G.

48

Cap´ıtulo 2. Congruencias

2. Para a, b y c en G (a ∗ b) ∗ c = a ∗ (b ∗ c) 3. Existe un elemento e en G, llamado el elemento neutro de G, el cual satisface: a∗e=e∗a=a

para todo a en G.

4. Para todo a en G, existe un elemento en G, llamado el inverso de a, el cual denotamos por a−1 , con la propiedad: a ∗ a−1 = a−1 ∗ a = e. Si adem´as de las cuatro propiedades anteriores, el grupo G posee la propiedad adicional a∗b=b∗a para todo a y b en G, entonces diremos que G es un grupo abeliano. Ejemplo: El conjunto de los n´ umeros enteros con la suma (ZZ , +) es un grupo abeliano. Ejemplo: El conjunto de las fracciones no nulas bajo el producto, ( Q ∗ , .) es un grupo abeliano. Definici´ on 2.5.3 Sea IR un grupo abeliano con operaci´ on *. Diremos que IR es un anillo, si en IR est´a definida otra operaci´ on ⊕, la cual verifica: 1. Para a y b en IR, a ⊕ b est´ a en IR. 2. para a, b y c en IR (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)

2.5. Clases de congruencias

49

3. Para todos a, b y c en IR a ⊕ (b ∗ c) = a ⊕ b ∗ a ⊕ c y (a ∗ b) ⊕ c = a ⊕ c ∗ b ⊕ c Notaci´ on: El anillo IR con las dos operaciones *, ⊕, se denota por (IR, ∗, ⊕). Si adem´as el anillo IR satisface la propiedad a ⊕ b = b ⊕ a para todo a, b en IR, entonces diremos que IR es un anillo conmutativo. Si en IR hay elemento identidad para el producto, es decir un elemento llamado “uno” y denotado por 1, tal que 1⊕a=a⊕1=a para todo a, diremos que IR es un Anillo Unitario. Ejemplo: Los Enteros El conjunto ZZ de los n´ umeros enteros con la suma y multiplicaci´on, es un anillo conmutativo unitario. Ejemplo: Los Polinomios El conjunto de todos los Polinomios en una variable x con coeficientes enteros, con las operaciones de suma y producto de polinomios, es un anillo conmutativo unitario. Este anillo se denota por ZZ [x].

Enteros m´ odulo m A continuaci´on daremos un ejemplo de anillo, que ser´a de importancia fundamental en todo el desarrollo de la teor´ıa de n´ umeros. Consideremos un entero positivo m, y sea ZZm el conjunto de clases de equivalencia m´odulo m. Entonces hay dos operaciones definidas en ZZm .

50

Cap´ıtulo 2. Congruencias

1. Suma m´ odulo m, definida por [a] + [b] = [a + b] 2. Producto m´ odulo m, definida por [a] · [b] = [a · b] Antes de pasar a ver las propiedades de este par de operaciones, debemos asegurarnos de que no hay ambig¨ uedades en la definici´on. Esto es, si sumamos dos clases usando distintos representantes: ¿Se obtendr´a el mismo resultado? Es decir, si a1 , a2 , b1 , b2 son enteros tales que [a1 ] = [a2 ]

y

[b1 ] = [b2 ]

entonces debemos asegurarnos, para evitar dudas, que: [a1 ] + [b1 ] = [a2 ] + [b2 ] Si esto se cumple, diremos que la suma m´odulo m est´ a bien definida. Notemos en primer lugar que si [a1 ] = [a2 ] entonces a1 ≡ a2 mod m Igualmente, de [b1 ] = [b2 ] se desprende b1 ≡ b2 mod m Por lo tanto podemos sumar ambas congruencias para obtener a1 + b1 ≡ a2 + b2 mod m, lo cual implica [a1 + b1 ] = [a2 + b2 ], luego [a1 ] + [b1 ] = [a2 ] + [b2 ]. De igual manera, para el producto tenemos [a1 ].[b1 ] = [a2 ].[b2 ]. Concluimos de esta manera que la suma y el producto m´odulo m est´an bien definidas.

2.5. Clases de congruencias

51

Proposici´ on 2.5.1 Sea m un entero positivo. Entonces el conjunto ZZm de las clases de congruencias m´odulo m, con las operaciones de suma y producto m´odulo m es un anillo conmutativo con unidad. Demostraci´ on: Ejercicio.

♠

Ejemplo: Consideremos ZZ6 , el anillo de los enteros m´odulo 6. Podemos construir una tabla para la operaci´on de suma, para lo cual colocaremos todos los elementos de ZZ6 en la primera columna y en la primera fila de la tabla + 0 1 2 3 4 5

0 0 1 2 3 4 5

1 1 2 3 4 5 0

2 2 3 4 5 0 1

3 3 4 5 0 1 2

4 4 5 0 1 2 3

5 5 0 1 2 3 4

Ejercicio: Analizar la tabla anterior, verificando cada una de las operaciones y responda a las preguntas 1. ¿Por qu´e la tabla es sim´etrica con respecto a la diagonal ? 2. ¿Por qu´e ning´ un elemento se repite en una misma columna o fila? 3. ¿Por qu´e aparece el cero en todas las filas y columnas? Podemos construir una tabla para el producto m´odulo 6, de la misma forma como lo hicimos para la suma. . 0 1 2 3 4 5

0 0 0 0 0 0 0

1 0 1 2 3 4 5

2 0 2 4 0 2 4

3 0 3 0 3 0 3

4 0 4 2 0 4 2

5 0 5 4 3 2 1

52

Cap´ıtulo 2. Congruencias

Si analizamos esta tabla, vemos que en la columna del elemento 2, no aparece el elemento 1. Luego no existe elemento x tal que [2] · [x] = 1. Por lo tanto los enteros m´odulo 6 no forman un grupo bajo el producto, pues el elemento [2] no posee inverso. Definici´ on 2.5.4 Un anillo conmutativo con unidad IR, en donde todo elemento posee inverso bajo el producto, se llama un Cuerpo. Observaci´ on : Si el anillo conmutativo unitario IR es finito, entonces la existencia de elementos inversos para el producto es equivalente a la ley de cancelaci´on para el producto. La cual establecemos a continuaci´on: Ley de cancelaci´ on para el producto: Si a, b y c son elementos de IR tales que a 6= 0, entonces a · b = a · c implica b = c La prueba de esto se deja como ejercicio para el lector. Veamos bajo que condiciones sobre m, se cumple la ley de cancelaci´on en ZZm . Teorema 2.5.1 Sea a un entero positivo y (a, m) = d. Entonces si ab ≡ ac mod m, se tiene b ≡ c mod

m d

Demostraci´ on: Tenemos por hip´otesis que m | a(b−c). Luego m/d divide a a/d(b− c) y adem´as ( md , ad ) = 1. Luego concluimos que m/d divide a b − c, de donde se obtiene b ≡ c mod

m d ♠

Ejemplo: Sea la congruencia 3 ×2 ≡ 3×4 mod 6. Notar que (3, 6) = 3 y por lo cual se tiene 2 ≡ 4 mod 2.

2.5. Clases de congruencias

53

Proposici´ on 2.5.2 Sea p un primo y a un entero positivo, tal que (p, a) = 1, entonces si ab ≡ ac mod p,

se tiene

b ≡ c mod p.

Finalmente, podemos caracterizar los anillos ZZm , que son cuerpos. Teorema 2.5.2 El anillo de clases de congruencias ZZp es un cuerpo s´ı y s´olo si p es primo. Demostraci´ on: Ejercicio.

♠

Ejercicios 1) Construir tablas para las operaciones de suma y producto m´odulo 7. 2) Usando las tablas anteriores, resolver la congruencias 1. 2a ≡ 3 mod 7 2. 5a ≡ 4 mod 7 3) Un elemento a 6= 0 en un anillo IR, se dice que es un divisor de cero, si existe un b 6= 0 en IR, tal que a · b = 0. Demostrar que no hay divisores de cero en Zp , con p primo. 4) Demuestre que el anillo ZZm tiene exactamente m elementos. 5) Demuestre que en un grupo siempre se puede resolver la ecuaci´on: a ∗ x = b. 6) Sea IR un anillo y a, b y c elementos de IR. ¿Bajo que condiciones sobre estos elementos, se puede resolver la ecuaci´on: a · x + b = c? 7) Demuestre que si f (x) y h(x) son dos polinomios con coeficientes reales, se cumple que

54

Cap´ıtulo 2. Congruencias

f (x)h(x) = h(x)f (x). 8) Demuestre que no existe divisores de cero en el anillo de polinomios sobre los reales. 9) Probar que [a], [b] y [c] son tres clases de congruencia m´odulo m, se cumple que [a] + ([b] + [c]) = ([a] + [b]) + [c]. 10) Si p es un n´ umero primo probar que ZZp es un cuerpo.

√ 11) Sea A el conjunto de los n´ umeros reales de la forma a + b 2, con a y b n´ umeros racionales. Probar que A es un cuerpo con las operaciones de suma y producto de n´ umeros reales. 12) Probar que en la tabla de operaci´on de un grupo no pueden haber elementos repetidos en una misma fila o columna.

2.6

Ecuaciones lineales de congruencia

Una ecuaci´on del tipo a · x ≡ b mod m

(2.1)

se llama ecuaci´ on lineal de congruencia. Observaci´ on: Si x0 es soluci´on de (2.1), y x1 es otro entero tal que x1 ≡ x0 mod m, entonces x1 tambi´en ser´a soluci´on de la ecuaci´on. As´ı pues, si (2.1) posee soluci´on, entonces posee infinitas. Sin embargo s´olo nos interesan aquellas soluciones que no sean congruentes entre si. Volviendo a la ecuaci´on anterior, podemos expresarla como a·x−m·y =b donde y es un entero a determinar.

(2.2)

2.6. Ecuaciones lineales de congruencia

55

Una ecuaci´on del tipo (2.2) se denomina ecuaci´ on lineal diof´ antica en las variables x e y. Se supone que las soluciones de esta ecuaci´on son n´ umeros enteros. Diofantos de Alejandr´ıa fue uno de los grandes matem´aticos griegos y escribi´o sus obras a mediados del siglo 3 d.c. La m´as importante es la Aritm´etica, que consist´ıa en el estudio de resoluci´on de ecuaciones, como por ejemplo la ecuaci´on Ax2 + C = y 2 . Ejemplo: Resolver 7 · x + 15 · y = 12 Soluci´ on: Usaremos el m´etodo de Euler, que consiste en despejar una de las inc´ognitas con menor coeficiente, en funci´on de la otra. Esto nos conduce a establecer una ecuaci´on diof´antica con coeficientes menores. Se tiene entonces 5−y 12 − 15 · y =1−2·y+ 7 7 Si se requiere que x e y sean enteros, se debe tener x=

z=

5−y 7

entero.

Luego y =5−7·z D´andole valores enteros arbitrarios a z, podemos obtener valores enteros de x e y, que cumplen la ecuaci´on original. Expresando x e y en funci´on de z se deduce x = −9 + 15 · z y = 5 − 7 · z.

56

Cap´ıtulo 2. Congruencias

Siendo z cualquier entero. Por ejemplo, haciendo z = 0 se tiene x = −9, y = 5, lo cual nos da una soluci´on a la ecuaci´on. Como veremos enseguida, la ecuaci´on lineal diof´antica siempre se puede resolver si se cumplen ciertas condiciones sobre los coeficientes a, b y c. Teorema 2.6.1 La ecuaci´ on ax + by = c

(2.3)

tiene soluci´on si y s´olo si d | c, donde d = (a, b). Demostraci´ on: Notemos en primer lugar que d | a, y d | b. Por lo tanto, si la ecuaci´on (2.3) tiene soluci´on (x, y) se tiene que d | ax + by, y luego d | c. Rec´ıprocamente, supongase que d | c. Dividiendo entre d la ecuaci´on original, nos da a0 x + b0 y = c0 (2.4) donde a0 = a/d, b0 = b/d y c0 = c/d. Es claro que si (2.4) tiene soluci´on, entonces (2.3) tambi´en posee soluci´on y viceversa. Luego ambas ecuaciones son equivalentes. Notemos que (a0 , b0 ) = 1, y por lo tanto existen enteros x00 e y00 tales que a0 x00 + b0 y00 = 1 Luego es f´acil verificar que x0 = c0 x00 e y0 = c0 y00 son soluciones de (2.4) y por ende soluciones de (2.3). Teorema 2.6.2 Si la ecuaci´ on lineal diof´antica (2.3) posee soluci´on y (x0 , y0 ) es una soluci´on particular, entonces toda otra soluci´on (x, y) es de la forma a b x = x0 + t, y = y0 − t d d donde t es cualquier entero.

2.6. Ecuaciones lineales de congruencia

57

Demostraci´ on: En primer lugar, probaremos que x e y son soluci´on. En efecto b a a(x0 + t) + b(y0 − t) = ax0 + by0 = c d d Por otro lado si (x, y) es cualquier soluci´on de (2.3), tambi´en lo ser´a de (2.4) y en consecuencia a0 (x − x0 ) + b0 (y − y0 ) = c0 − c0 = 0 de donde a0 (x − x0 ) = −b0 (y − y0 ) De ac´a se deduce a0 | b0 (y − y0 ) y por lo tanto a0 | (y − y0 ). Luego y = y0 + a0 t, donde t es un entero. Igualmente, se verifica x = x0 + b0 s, con s entero. Probaremos que s = −t, para lo cual sustituimos la solucion (x, y) en (2.4) a0 (x0 + b0 s) + b0 (y0 + a0 t) = c0 a0 x0 + b0 y0 + a0 b0 (s + t) = c0 como (x0 , y0 ) es soluci´on de (2.4) se tiene a0 x0 + b0 y0 = c0 , y por lo tanto c0 + a0 b0 (s + t) = c0 o sea a0 b0 (s + t) = 0 de donde s = −t. Con esto termina la demostraci´on. ♠ Teorema 2.6.3 La ecuaci´ on lineal de congruencia ax ≡ b mod m

(2.5)

posee soluci´on si y s´olo si d | b, donde d = (a, m). Si x0 es una soluci´on particular de (2.5), entonces la soluci´on general viene dada por m x ≡ x0 mod . d

58

Cap´ıtulo 2. Congruencias

Demostraci´ on: Podemos expresar la ecuaci´on anterior como ax − my = b

(2.6)

De acuerdo al teorema anterior, sabemos que (2.6) posee soluci´on y adem´as la soluci´on general para la x viene expresada mediante: m t. d Para finalizar la demostraci´on, observemos que las d soluciones x = x0 +

m (d − 1)m , . . . , x0 + d d son todas distintas m´odulo m. x0 , x 0 +

♠

Ejemplo: Resolver 30x ≡ 15 mod 21 Soluci´ on: Obs´ervese que (30, 21) = 3, y 3 divide a 15. Luego la ecuaci´on tiene soluci´on. El n´ umero de soluciones m´odulo 21 ser´a igual a (21, 30) = 3. Con la finalidad de hallar una soluci´on particular, procederemos a dividir entre 3 la ecuaci´on. Luego 10x ≡ 5 mod 21 esto es 3x ≡ 5 mod 7 Por simple inspecci´on, calculamos una soluci´on x ≡ 4 mod 7. Luego las tres soluciones distintas m´odulo 21 son: 4, 11 y 18. Ejemplo:

2.6. Ecuaciones lineales de congruencia

59

Resolver 238x + 125y = 31 Soluci´ on: En este ejemplo se puede reducir el tama˜ no de los coeficientes, mediante un cambio de variables. Podemos reescribir la ecuaci´on anterior 125(y + 2x) − 12(x + 2) = 7 Empleamos ahora el siguiente cambio de variables X = x + 2,

Y = y + 2x

Luego la ecuaci´on original se transforma en 125Y − 12X = 7 Resolviendo tenemos 125Y − 7 5Y − 7 = 10Y + 12 12 Nuevamente, haciendo el cambio de variable X=

z=

5Y − 7 12

de donde Y =

12z + 7 2z + 2 = 2z + 1 + 5 5

2z + 2 es un entero y por lo tanto hacemos z = −1. Luego 5 De aqu´ı obtenemos los resultados Y = −1,

X = −11

volviendo al cambio de variables y = 15,

x = −13

60

Cap´ıtulo 2. Congruencias

Luego la soluci´on de la ecuaci´on original viene expresada por x = −13 + 125t,

y = 15 − 238t

Estudiemos ahora el problema de resolver una ecuaci´on de congruencia con m´as de una indeterminada. Ejemplo: Resolver 3x + 4y ≡ 11 mod 14

(2.7)

En primer lugar, observamos que 14 = 7 · 2. Luego es posible trabajar con m´odulos 7 ´o 2, para hallar soluciones de (2.7). Escogemos el 2 por ser menor. Luego tomando la misma ecuaci´on m´odulo 2 se obtiene 3x + 4y ≡ 11 mod 2 o sea 3x ≡ 1 mod 2 De esta ecuaci´on provienen 7 soluciones distintas m´odulo 14 para x, las cuales son: 1, 3, 5, 7, 9, 11 y 13. Al sustituir cada una de ´estas en la ecuaci´on original, se obtendr´an las correspondientes soluciones para la y. Por ejemplo, si se considera x ≡ 1 mod 14, se tendr´a 3x + 4y ≡ 11 mod 14 o bien 4y ≡ 8 mod 14 Notemos que (14, 2) = 2, luego podemos simplificar: 2y ≡ 4 mod 7 Luego las soluciones de y m´odulo 14 son 2 y 9.

2.6. Ecuaciones lineales de congruencia

61

Usaremos pares ordenados para indicar las soluciones de la ecuaci´on (2.7), donde la primera componente indica la x y la segunda indica la y. De esta forma, se obtienen las soluciones (1, 2) y (1, 9). Las restantes soluciones son: (3, 4), (3, 11), (5, 6), (5, 13), (7, 1), (7, 8), (9, 3), (9, 10), (11, 5), (11, 12), (13, 7), (13, 14). Teorema 2.6.4 La congruencia a1 x1 + a2 x2 + . . . + an xn ≡ c mod m es soluble si y s´olo si d | c, donde d = (a1 , a2 , . . . , an , m). El n´ umero de soluciones distintas m´odulo m es dmn−1 . Demostraci´ on: Haremos la demostraci´on para el caso n = 2. El caso general se deduce de este caso particular y del principio de inducci´on. Consideremos entonces a1 x + a2 y ≡ c mod m

(2.8)

donde (a1 , a2 , m) = d y d | c. Es f´acil ver que la condici´on d | c es necesaria para la existencia de la soluci´on. Probaremos que esta condici´on es tambi´en suficiente. A tal efecto, sea (a2 , m) = d0 . Luego de (2.8) obtenemos a1 x ≡ c mod d0

(2.9)

Notemos que (d0 , a1 ) = ((a2 , m), a1 ) = d, y d | c. Luego (2.9) posee d soluciones distintas m´odulo d0 , de acuerdo al teorema 2.6.3. Estas d soluciones, generan d · m/d0 soluciones distintas m´odulo m para x. Para cada soluci´on x, se reemplaza su valor en la ecuaci´on (2.8) para obtener

62

Cap´ıtulo 2. Congruencias

a2 y ≡ c − a1 x mod m Teniendo en cuenta que: (m, a2 ) = d0 , y adem´as: d0 | c − a1 x, se deduce entonces que la ecuaci´on anterior posee d0 soluciones distintas para y m´odulo m. Contando el n´ umero de soluciones de (2.8), se tendr´a la ecuaci´on S = Sx × Sy donde S = n´ umero de soluciones de (2.8), Sx = n´ umero de soluciones para x y Sy = n´ umero de soluciones para y. Luego S=d

2.7

m 0 d = d.m d0

Teorema Chino del Resto

El problema de resolver la congruencia ax ≡ b mod m

(2.10)

puede ser bastante laborioso si m es grande, debido al n´ umero de calculos requeridos, cuando esta se resuelve usando el m´etodo de la secci´on anterior. Si m se factoriza como un producto de enteros m1 .m2 . . . mn entonces la ecuaci´on anterior es equivalente a las ecuaciones ax ≡ b mod mi ,

1≤i≤n

Teorema 2.7.1 Sean m1 , m2 , . . . , mn enteros positivos. Entonces el sistema   ax ≡  

b mod m1 .. .    ax ≡ b mod m n es equivalente a la ecuaci´ on ax ≡ b mod [m1 , m2 , . . . , mn ]

2.7. Teorema Chino del Resto

63

Demostraci´ on: Notemos que para todo i, se tiene mi | ax − b, por hip´otesis, luego ax − b, es m´ ultiplo com´ un de los mi y por lo tanto [m1 , . . . , mn ] divide a ax − b . Luego ax ≡ b mod [m1 , . . . , mn ]. Rec´ıprocamente, es f´acil ver que toda soluci´on de la ecuaci´on satisface el sistema, con lo cual se da fin a la prueba. ♠ Observaci´ on: Si los mi son primos relativos por pareja, esto es, (mi , mj ) = 1 para todo par de enteros i 6= j, entonces se tiene [m1 , . . . , mn ] = m1 . . . mn . As´ı pues, tenemos el siguiente resultado Teorema 2.7.2 Si m se factoriza m = pα1 1 .pα2 2 . . . pαnn entonces la ecuaci´ on ax ≡ b mod m es equivalente al sistema de n ecuaciones ax ≡ b mod pαi i , 1 ≤ i ≤ n Ejemplo: Resolver 7x ≡ 6 mod 100 Soluci´ on:

64

Cap´ıtulo 2. Congruencias

Descomponiendo a 100 como producto de primos, nos da 100 = 22 52 , luego la ecuaci´on es equivalente al sistema 7x ≡ 6 mod 25 3x ≡ 2 mod 4 La primera ecuaci´on tiene soluci´on x ≡ 8 mod 25, o sea x = 8, 33, 58, 83, . . .. La segunda ecuaci´on tiene soluci´on x ≡ 2 mod 4, esto es x = 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, . . .. Luego la soluci´on com´ un viene expresada por x ≡ 58 mod 100

2.7. Teorema Chino del Resto

65

Ejemplo: Ahora planteamos un problema de la antigua China, que data del a˜ no 1275 d.c. “Hallar un n´ umero tal que, al ser dividido por siete da uno como residuo, al ser dividido por ocho da dos como residuo y al ser dividido por nueve da tres como residuo”. Soluci´ on: Podemos plantear el problema en t´erminos de congruencias de la siguiente manera; sea x el n´ umero buscado, entonces    x

≡ 1 mod 7 x ≡ 2 mod 8   x ≡ 3 mod 9 De la primera ecuaci´on obtenemos x = 1 + 7k Sustituyendo en la segunda ecuaci´on 1 + 7k ≡ 2 mod 8 de donde 7k ≡ 1 mod 8 Luego k ≡ 7 mod 8, y por lo tanto k = 7 + 8l. Sustituyendo en la expresi´on de x nos da: x = 50 + 56l. Este u ´ltimo valor de x lo sustituimos en la tercera ecuaci´on para obtener 50 + 56l ≡ 3 mod 9 y despu´es de reducir m´odulo 9 nos queda: l = 8 + 9j. Finalmente, si se remplaza el valor de l en la expresi´on de x produce

66

Cap´ıtulo 2. Congruencias

x = 50 + 56(8 + 9j) = 498 + 504j de donde se concluye x ≡ 498 mod 504 Proposici´ on 2.7.1 Sean m1 y m2 enteros primos relativos. Entonces existen enteros x0 y x1 tales que x0 ≡ 1 mod m1

x0 ≡ 0 mod m2 (2.11)

x1 ≡ 0 mod m1

x1 ≡ 1 mod m2

Demostraci´ on: Sabemos que existen enteros s y t tales que s · m1 + t · m2 = 1 Luego s · m1 ≡ 1 mod m2 y s · m1 ≡ 0 mod m1 . Similarmente t · m2 ≡ 1 mod m1 y t · m2 ≡ 0 mod m2 . Tomar entonces x0 = t · m2 y x1 = s · m 1 . ♠ Proposici´ on 2.7.2 Sean m1 y m2 enteros primos relativos. Entonces dados dos enteros cualesquiera a y b, existe un entero x que satisface x ≡ a mod m1 x ≡ b mod m2 Demostraci´ on: Tomar x = a · x0 + b · x1 , donde x0 y x1 satisfacen la condici´on (2.11) ♠

2.7. Teorema Chino del Resto

67

Teorema 2.7.3 (Teorema Chino del Resto) Sean m1 , . . . , mn enteros positivos, primos relativos por parejas. Entonces si a1 , . . . , an son enteros cualesquiera, el sistema   x      x

≡ a1 mod m1 .. . ≡ an mod mn

posee soluci´on. Adem´ as si m = m1 · · · mn , cualquier par de soluciones son congruentes m´odulo m. Demostraci´ on: Usaremos inducci´on sobre n. Para n = 1 el teorema es cierto. Supongase que el sistema   x      x

≡ a1 .. .

mod m1

≡ an−1 mod mn−1

posee soluci´on u ´nica x0 m´odulo m0 = m1 · m2 · · · mn−1 . Entonces el sistema original se puede reducir a resolver x ≡ x0 mod m0 x ≡ an mod mn Tenemos entonces que (mn , m0 ) = (mn , m1 . . . . mn−1 ) = 1. Luego podemos aplicar la proposici´on anterior para hallar la soluci´on buscada, la cual ser´a u ´nica m´odulo m1 · · · mn , por hip´otesis de inducci´on.

Aplicaci´ on del teorema chino en cronolog´ıa Una de las medidas m´as usadas en la cronolog´ıa hist´orica es la de los d´ıas julianos. Los d´ıas julianos tienen la misma duraci´on que los d´ıas

68

Cap´ıtulo 2. Congruencias

solares, sin embargo ´estos se cuentan a partir del primero de enero del 4713 a.c., el cual es el d´ıa juliano 1, y de all´ı en adelante se enumeran los d´ıas en sucesi´on creciente. Este sistema fue ideado por Joseph Justus Scaliger de Leyden, y apareci´o por primera vez en su obra “De emendatione temporum” (Par´ıs 1583). Estos d´ıas julianos se agrupan en per´ıodos de 7980 a˜ nos. Cada uno de estos per´ıodos se denomina Ciclo Juliano o Per´ıodo Juliano. La raz´on para elegir semejante n´ umero, la veremos a continuaci´on. Tenemos que 7980 = 28 × 19 × 15 y cada uno de estos factores tiene un significado muy especial dentro de los calendarios de distintas cronolog´ıas El n´ umero 28 corresponde al llamado Ciclo Solar de 28 a˜ nos. Este es el ciclo m´as peque˜ no en el cual los d´ıas de la semana y las fechas del calendario se repiten. El primer a˜ no de un ciclo solar es aquel, en donde el d´ıa primero de enero es lunes. Por ejemplo, el a˜ no 1560 tiene a˜ no solar 1. El n´ umero 19 corresponde al Ciclo Met´ onico o Ciclo Lunar, el cual dura 19 a˜ nos. Este es el menor ciclo en el cual las fases de la luna se repiten en las mismas fechas del calendario. Este proviene del astr´onomo griego Meton (siglo V a.c.), qui´en descubri´o que 19 a˜ nos solares corresponden exactamente a 235 lunaciones o meses lunares. Los a˜ nos del ciclo met´onico se llaman A˜ nos Dorados. Este sistema fue introducido por el Emperador Dionisio Exigus en el a˜ no 533 d.c. y este a˜ no tiene a˜ no dorado 1. Finalmente, el n´ umero 15 corresponde a otro ciclo, el cual no tiene nada que ver con astronom´ıa. Se trata del ciclo de recolecci´on de impuestos en la antigua Roma que constaba de 15 a˜ nos y se llama la indicci´ on. Este ciclo fue introducido por el Emperador Constantino en el a˜ no 313 d.c. correspondiendo a este a˜ no el primer a˜ no de dicho ciclo. La idea de Scaliger era usar un sistema de cronolog´ıa que incluyera todos estos ciclos. Esto permitir´ıa calcular f´acilmente una fecha determinada al pasar de un sistema a otro. El problema entonces era

2.7. Teorema Chino del Resto

69

escoger una fecha apropiada para iniciar la cuenta de los a˜ nos julianos. Se necesitaba un a˜ no x de la historia, tal que en ese a˜ no se diera inicio a los tres ciclos. Esto es, x debe tener A˜ no solar = 1 A˜ no dorado = 1 A˜ no de indicci´on = 1 Usando congruencias, se debe tener el sistema    x

≡ 1560 mod 28 x ≡ 532 mod 19   x ≡ 313 mod 15 Reduciendo esto se tiene    x

≡ 20 mod 28 x ≡ 0 mod 19   x ≡ 13 mod 15 N´otese que (28, 27) = 1, (28,15) = 1 y (15,19) = 1. Luego por el Teorema Chino del Resto, el sistema anterior posee soluci´on. A fin de determinar el valor de x, comenzaremos por usar la primera ecuaci´on. Luego x = 20 + 28k

con k entero.

Usando la segunda ecuaci´on nos queda 20 + 28k ≡ 0 mod 19 1 + 9k ≡ 0 mod 19 9k ≡ 18 mod 19 de donde k ≡ 2 mod 19

70

Cap´ıtulo 2. Congruencias

Luego k = 2 + 19s y por lo tanto volviendo a x en la u ´ltima ecuaci´on tenemos 76 + 532s ≡ 13 mod 15 1 + 7s ≡ 13 mod 15 luego, 7s ≡ 12 mod 15, de donde s ≡ 6 mod 15. Por lo tanto s = 6+15t. Nuevamente, si reemplazamos este valor en la expresi´on para x nos da x = 76 + 532(6 + 15t) = 326 + 7980t Luego la soluci´on viene dada por x ≡ 3268 mod 7980 Sin embargo, descartamos el a˜ no 3268 por ser del futuro y buscamos el a˜ no y en que se inici´o el per´ıodo juliano anterior. Esto es y = 3268 − 7980 = −4712 En el calendario gregoriano, el a˜ no -4712 corresponde al 4713 a.c. (no hay a˜ no 0) y ´este se toma como el a˜ no 1 juliano. Ejemplo: Conociendo el a˜ no juliano de un a˜ no cualquiera, podemos calcular su a˜ no solar, dorado y de indicci´on; basta tomar los restos de la divisi´on del n´ umero entre 28, 19 y 15 respectivamente. Por ejemplo para buscar el a˜ no juliano de 1993, el cual llamaremos x, hacemos x = 4713 + 1993 = 6706 Luego dividimos a 6706 entre 28, 19 y 15 respectivamente para obtener los restos que nos dan toda la informaci´on. Por lo tanto

2.7. Teorema Chino del Resto

71

A˜ no solar de 1993 = 14 A˜ no dorado de 1993 = 18 A˜ no de indicci´on de 1993 = 1

Ejercicios 1) Resolver 238x + 133y = 31 2) Resolver 15x + 30y = 720 3) Resolver 7x + 11y = 150 4) Resolver las ecuaciones de congruencia. a) 12x ≡ 7 mod 17 b) 11x ≡ 7 mod 84 c) 18x ≡ 1 mod 25 5) Resuelva el sistema  x    

≡ 1 mod x ≡ 2 mod  x ≡ 3 mod    x ≡ 5 mod

2 3 5 7

6) Resuelva la congruencia 2x + 3y ≡ 15 mod 16 7) Hacer una tabla en donde aparezcan los a˜ nos solares, dorados y de indicci´on para el per´ıodo comprendido entre 1800 y 1850. 8) Demostrar que si x0 es un entero y d|m, entonces los d enteros

72

Cap´ıtulo 2. Congruencias

x0 , x 0 +

m (d − 1)m , . . . , x0 + d d

son todos diferentes m´odulo m. 9) Un comerciante compr´o un lote de juguetes de dos tipos distintos por Bs. 50.000. El primer tipo cuesta Bs. 1.950 por unidad, y el segundo tipo cuesta Bs. 770. ¿Qu´e cantidad de juguetes de cada tipo compr´o el comerciante?. 10) Resolver 1050x + 6y + 462z ≡ 6 mod 12 11) En X se celebraron eleciones para elegir el Presidente en 1994. En 1992 se realizaron elecciones para elegir gobernadores. Si el per´ıodo de mando de los presidente es de 5 a˜ nos, y el de los gobernadores de 8, entonces determine en qu´e a˜ no coincidir´an ambas elecciones.