Teor´ıa de N´umeros Naoki Sato 22 de julio de 2012 Resumen Estas notas sobre teor´ıa de n´ umeros fueron originariamente escritas en 1995 para estudiantes de nivel OIM. Cubre s´olo lo b´asico del material con el cual un estudiante de OIM deber´ıa estar familiarizado. Este texto se pens´ o como una referencia no como un reemplazo, sino como un suplemento para un libro de teor´ıa de n´ umeros; varios libros son sugeridos al final. Hay algunas demostraciones cuando sea apropiado o para ilustrar un punto o una idea importante. Los problemas son tomados de varias fuentes, muchos de concursos existentes u olimp´ıadas, y en general son bastante dif´ıciles. El autor agradece cualquier correcci´ on o sugerencia.

1.

Divisibilidad

Para enteros a y b, decimos que a divide a b, o que a es un divisor (o un factor de b, o que b es un m´ ultiplo de a, si existe un entero c tal que b = ca, y denotamos esto por a | b. En otro caso, a no divide b, y denotamos esto por a - b. Un entero positivo p es primo si los u ´nicos divisores de p son 1 y p. Si pk | a y pk+1 - a donde p es primo, es decir pk es la mayor potencia de p que divide a a, entonces denotamos esto por pk k a.

Resultados u ´ tiles: Si a, b > 0, y a | b, entonces a ≤ b. Si a | b1 , a | b2 , . . . , a | bn , entonces para cualesquiera enteros c1 , c2 , . . . , cn a|

n X i=1

1

bi c i

Teorema 1.1. El Algoritmo de la Divisi´on. Para cualquier entero positivo a y entero b, existe u ´nicos enteros q y r tal que b = qa + r y 0 ≤ r < a, con r = 0 si y s´olo si a | b. Teorema 1.2. El Teorema Fundamental de la Aritm´etica. Cada entero mayor que 1 puede ser escrito de manera u ´nica en la forma pe11 pe22 · · · pekk donde los pi son primos distintos y los ei son enteros positivos. Teorema 1.3. Euclides. Existen una infinitud de n´ umeros primos. Demostraci´ on. Supongamos que hay una cantidad finita de n´ umeros primos, digamos p1 , p2 , . . . , pn . Sea N = p1 p2 · · · pn + 1. Por el teorema fundamental de la aritm´etica, N es divisible por alg´ un primo p. Este primo p debe estar entre los pi , pues asumimos que estos eran todos los primos, pero se puede ver que N no es divisible por ninguno de los pi , contradicci´on. Ejemplo 1.1. Sea x e y enteros. Probar que 2x + 3y es divisible por 17 si y s´olo si 9x + 5y es divisible por 17. Soluci´ on. 17 | (2x + 36) ⇒ 17 | [13(2x + 3y)], o 17 | (26x + 39y) ⇒ 17 | (9x + 5y)y , rec´ıprocamente, 17 | (9x + 5y) ⇒ 17 | [4(9x + 5y)], o 17 | (36x + 20y) ⇒ 17 | (2x + 3y). Ejemplo 1.2. Encontrar todos los enteros positivos d tales que d divide simult´aneamente a n2 + 1 y a (n + 1)2 + 1 para alg´ un entero n. Soluci´ on. Sea d | (n2 + 1) y d | (n + 1)2 + 1, o d | (n2 + 2n + 2). Entonces d | [(n2 + 2n + 2] − (n2 + 1)], o d | (2n + 1) ⇒ d | (4n2 + 4n + 1), luego d | [4(n2 +2n+2)−(4n2 +4n+1)], o d | (4n+7). Entonces d | [(4n+7)−2(2n+1)], o d | 5, luego d s´olo puede ser 1 o 5. Tomando n = 2 vemos que se puede lograr estos valores. Ejemplo 1.3. Supongamos que a1 , a2 , . . . , a2n son enteros distintos tal que la ecuaci´on (x − a1 )(x − a2 ) · · · (x − a2n ) − (−1)n (n!)2 = 0 tiene una soluci´on entera r. Pruebe que r=

a1 + a2 + · · · + a2n . 2n

(1984 Lista Corta - Olimpiada Internacional de Matem´atica) 2

Soluci´ on. Claramente r 6= ai para todo i, y como r − ai son 2n enteros distintos, entonces |(r − a1 )(r − a2 ) · · · (r − a2n )| ≥ |(1)(2) · · · (n)(−1)(−2) · · · (−n)| = (n!)2 , con igualdad si y s´olo si {r − a1 , r − a2 , . . . , r − a2n } = {1, 2, . . . , n, −1, −2, . . . , −n}. Por lo tanto, este debe ser el caso, luego (r − a1 ) + (r − a2 ) + · · · + (r − a2n ) = 2nr − (a1 + a2 + · · · + a2n ) = 1 + 2 + · · · + n + (−1) + (−2) + · · · + (−n) = 0 a1 + a2 + · · · + a2n ⇒r= . 2n Ejemplo 1.4. Sean 0 < a1 < a2 < · · · < amn+1 , mn + 1 enteros. Probar que se pueden seleccionar m + 1 tal que no sean divisibles entre si, o n + 1 tal que cada uno divida al siguiente. (1966 Competencia Matem´atica Putnam) Soluci´ on. Para cada i, 1 ≤ i ≤ mn + 1, sea ni la longitud de la secuencia m´as larga que empieza con ai donde cada t´ermino divide el siguiente, entre los enteros ai , ai+1 , . . . , amn+1 . Si para alg´ un ni es mayor que n entonces el problema esta resuelto. En otro caso, por el principio del palomar, existen por lo menos m + 1 valores de ni que son iguales. Luego, los enteros ai correspondientes a estos ni no pueden ser divisibles entre si.

´ Resultados Utiles Postulado de Bertrand. Para cada entero positivo n, existe un primo p tal que n ≤ p ≤ 2n. Lema de Gauss. Si un polinomio con coeficientes enteros se factoriza en dos polinomios con coeficientes racionales, entonces se factoriza en dos polinomios con coeficientes enteros.

Problemas 1. Sean a y b enteros positivos tales que a | b2 , b2 | a3 , a3 | b4 , b4 | a5 , . . . . Pruebe que a = b. 3

2. Sean a, b y c tres enteros distintos, y sea P un polinomio con todos los coeficientes enteros. Pruebe que es imposible que P (a) = b, P (b) = c y P (c) = a. (1974 Olimpiada Matem´atica de Estados Unidos) 3. Demuestre que si a y b son enteros positivos, entonces n  n  1 1 + b+ a+ 2 2 es entero s´olo para finitos enteros positivos n. (A Problem Seminar, D.J. Newman) 4. Dado un entero positivo n, sea r(n) la suma de los restos cuando n es dividido por 1, 2, . . . , n respectivamente. Pruebe que r(k) = r(k − 1) para finitos enteros positivos k. (1981 Competici´on K¨ ursch´ak) 5. Pruebe que para todos los enteros positivos n, 0<

n X g(k)

k

k=1

−

2n 2 < , 3 3

donde g(k) denota el mayor divisor impar de k. (1973 Olimpiada Matem´atica de Austria) 6. Sea d un entero positivo, y sea S el conjunto de todos los enteros positivos de la forma x2 + dy 2 , donde x y y son enteros no negativos. a) Pruebe que si a ∈ S y b ∈ S, entonces ab ∈ S. b) Pruebe que si a ∈ S y p ∈ S, tal que p es un primo y p | a, entonces a/p ∈ S. c) Asumiendo que la ecuaci´on x2 + dy 2 = p tiene soluci´on en los enteros no negativos x y y, donde p es un primo dado. Demuestre que si d ≥ 2, entonces la soluci´on es u ´nica, y si d =, entonces hay exactamente dos soluciones.

2.

M´ aximo Com´ un Divisor y M´ınimo Com´ un m´ ultiplo

El m´ aximo com´ un divisor de dos enteros positivos a y b es el mayor entero positivo que divide a a y b simult´aneamente, el cual vamos a denotar 4

mcd(a, b), y similarmente, el m´ınimo com´ un m´ ultiplo de a y b es el menor entero positivo que es m´ ultiplo de a y b simult´aneamente, el cual vamos a denotar mcm(a, b). Decimos que a y b son primos relativos si mcd(a, b) = 1. Para a1 , a2 , . . . , an , gcd(a1 , a2 , . . . , an ) es el mayor entero positivo que divide a todos los a1 , a2 , . . . , an simult´aneamente y mcm(a1 , a2 , . . . , an ) se define similarmente.

´ Resultados Utiles Para todos a, b mcd(a, b) mcm(a, b) = ab. Para todos a, b y m, mcd(ma, mb) = m mcd(a, b) y mcm(ma, mb) = m mcm(a, b). Si d | mcd(a, b), entonces  mcd

a b , d d

 =

mcd(a, b) . d

En particular, si d = mcd(a, b), entonces mcd(a/d, b/d) = 1; esto es a/d y b/d son primos relativos. Si a | bc y mcd(a, c) = 1, entonces a | b. Para a y b enteros positivos, si d es un entero positivo tal que d | a, d | b, y para cualquier d0 , d0 | a y d0 | b implica que d0 | d, entonces d = mcd(a, b). Esto es simplemente la afirmacion de que cualquier divisor com´ un de a y b divide a mcd(a, b). Si a1 a2 · · · an es una potencia k-´esima y los ai son primos relativos de a pares, entonces cada ai es una potencia k-´esima. Cualesquiera dos enteros consecutivos son primos relativos. Ejemplo 2.1. Muestre que para cualquier entero positivo N , existe un m´ ultiplo de N que consiste s´olo de unos y ceros. M´as a´ un, muestre que si N es primo relativo a 10, entonces existe un m´ ultiplo que consiste s´olo de unos. Soluci´ on. Considere los N +1 enteros 1, 11, 111, 111 . . . 1 (N +1 unos). Cuando son divididos por N dejan N +1 restos. Por el principio del palomar, dos de estos restos son iguales, luego la diferencia entre los correspondientes enteros, un entero de la forma 111 . . . 000, es divisible por N . Si N es primo relativo a 10, entonces podemos quitar todas las potencias de 10, hasta obtener un entero de la forma 111 . . . 1 que permanece divisible por N . 5

Teorema 2.1. Para cualesquiera enteros positivos a y b, existen enteros x e y tal que ax + by = mcd(a, b). M´as a´ un, haciendo variar x e y sobre los enteros, ax + by genera todos los m´ ultiplos y s´olo los m´ ultiplos de mcd(a, b). Soluci´ on. Sea S el conjunto de todos los enteros de la forma ax + by, y sea d el menor entero positivo entre los elementos de S. Por el algoritmo de divisi´on, existen enteros q y r tal que a = qd + r, 0 ≤ r < d. Luego r = a − qd = a − q(ax + by) = (1 − qa)a − (qy)b, luego r tambi´en esta en S. Pero r < d, luego r = 0 ⇒ d | a, y similarmente, d | b, luego d | mcd(a, b). Sin embargo, mcd(a, b) divide a todos los elementos de S, en particular mcd(a, b) | d ⇒ d = mcd(a, b). La segunda parte del teorema sale inmediatamente. Corolario 2.2. Los enteros positivos a y b son primos relativos s´ı y s´olo si existen enteros x e y tal que ax + by = 1. Corolario 2.3. Para cualesquiera enteros positivos a1 , a2 , . . . , an , existen enteros x1 , x2 , . . . , xn tal que a1 x1 + a2 x2 + · · · an xn = mcd(a1 , a2 , . . . , an ). Corolario 2.4. Sean a y b enteros positivos, y sea n un entero. Entonces la ecuaci´on ax + by = n tiene soluci´on en enteros x e y s´ı y s´olo si mcd(a, b) | n. Si este es el caso, entonces todas las soluciones son de la forma   a b (x, y) = x0 + t · , y0 − t · d d donde d = mcd(a, b), (x0 , y0 ) es una soluci´on particular de la ecuaci´on ax + by = n, y t es un entero. Demostraci´ on. La primer parte sale del Teorema 2.1. Para la segunda parte, sea d = mcd(a, b), y sea (x0 , y0 una soluci´on particular de ax + by = n, tal que ax0 + by0 = n. Si ax + by = n, entonces ax + by − ax0 − by0 = a(x − x0 ) + b(y − y0 ) = 0, o a(x − x0 ) = b(y0 − y), por lo tanto (x − x0 ) ·

a b = (y0 − y) · d d

Como a/d y b/d son primos relativos, b/d debe dividir a x − x0 , y a/d debe dividir a y0 − y. Sean x − x0 = tb/d y y0 − y = ta/d. Esto da las soluciones descriptas anteriormente. 6

Ejemplo 2.2. Pruebe que la fracci´on 21n + 4 14n + 3 es irreducible para cualquier entero positivo n. (1959 Olimpiada Internacional de Matem´atica) Soluci´ on. Para todo n, 3(14n + 3) − 2(21n + 4) = 1, luego numerador y denominador son primos relativos. n

Ejemplo 2.3. Para todo lo entero positivo n, sea Tn = 22 + 1. Muestre que si m 6= n, entonces Tm y Tn son primos relativos. Soluci´ on. Tenemos que n

n−1

Tn − 2 = 22 − 1 = 22 ·2 − 1 2 = (Tn−1 − 1)2 − 1 = Tn−1 − 2Tn−1 = Tn−1 (Tn−1 − 2) = Tn−1 Tn−2 (Tn−2 − 2) = ··· = Tn−1 Tn−2 · · · T1 T0 (T0 − 2) = Tn−1 Tn−2 · · · T1 T0 , para todo n. Por lo tanto, cualquier divisor com´ un de Tm y Tn debe dividir a 2. Pero cada Tn es impar, luego Tm y Tn son primos relativos. Nota. De este resultado se deduce inmediatamente que existen infinitos n´ umeros primos. El Algoritmo de Euclides. Usando recursivamente el algoritmo de la divisi´on, podemos encontrar el mcd de dos enteros positivos a y b sin factorizar ninguno de los dos, y x e y del Teorema 2.1 (y tambi´en, una soluci´on particular del Corolario 2.4). Por ejemplo, para a = 329 y b = 182, calculamos 329 = 1 · 182 + 147, 182 = 1 · 147 + 35, 147 = 4 · 35 + 7, 35 = 5 · 7, y nos detenmos cuando no hay resto. El u ´ltimo dividendo es el mcd, luego en nuestro ejemplo, mcd(329, 182) = 7. Ahora, reemplazando hacia atr´as, 7 = 147 − 4 · 35 = 147 − 4 · (182 − 1 · 147) = 5 · 147 − 4 · 182 = 5 · (329 − 182) − 4 · 182 = 5 · 329 − 9 · 182. 7

Nota. El algoritmo de Euclides tambi´en funciona para polinomios. Ejemplo 2.4. Sea n un entero positivo, y sea S un conjunto de n + 1 elementos de el conjunto {1, 2, . . . , 2n}. Pruebe que: 1. Existen dos elementos de S que son primos relativos, y 2. Existen dos elementos de S, uno de los cuales divide al otro Soluci´ on. (1) Tiene que haber dos elementos de S que sean consecutivos, y por lo tanto, primos relativos. (2) Considere el mayor factor impar de cada uno de los n+1 elementos en S. Cada est´a entre los n enteros impares 1, 3, . . . , 2n − 1. Por el principio del palomar, dos deben tener el mismo mayor factor impar, luego deben diferir (m´ ultiplicativamente) por una potencia de 2, luego uno divide al otro. Ejemplo 2.5. Los enteros positivos a1 , a2 , . . . , an son tales que cada uno es menor que 1000, y mcd(ai , aj ) > 1000 para todo i, j, i 6= j. Pruebe que n X 1 1, m, n. 3. Sean a, b y c enteros positivos. Demuestre que mcm(a, b, c) =

abc · mcd(a, b, c) . mcd(a, b) · mcd(a, c) · mcd(b, c)

Exprese mcd(a, b, c) en funci´on de abc, mcm(a, b, c), mcm(a, b), mcm(a, c) y mcm(b, c). Luego generalice. 4. Sean a, b enteros positivos impares. Defina la secuencia (fn ) con f1 = a, f2 = b, y haciendo que fn para n ≥ 3 sea el mayor divisor impar de fn−1 + fn−2 . Demuestre que fn es constante para n suficientemente grande y exprese el valor eventual en funci´on de a y b. (1993 Olimpiada Matem´atica de Estados Unidos) 9

5. Sean n ≥ a1 > a2 > · · · > ak enteros positivos tales que mcm(ai , aj ) ≤ n para todos i, j. Pruebe que iai ≤ n para i = 1, 2, . . . , k.

3.

Funciones Aritm´ eticas

Hay varias funciones aritm´eticas importates, de las cuales tres son presentadas aqu´ı. Si la factorizaci´on de n > 1 es pe11 pe22 · · · pekk , entonces el n´ umero de enteros positivos menores que n, primos relativos a n es:      1 1 1 1− ··· 1 − n φ(n) = 1 − p1 p2 pk = pe11 −1 pe22 −1 · · · pkek −1 (p1 − 1)(p2 − 1) · · · (pk − 1), el n´ umero de divisores de n es τ (n) = (e1 + 1)(e2 + 1) · · · (ek + 1), y la suma de los divisores de n es σ(n) = (pe11 + pe11 −1 + · · · + 1)(pe22 + pe22 −1 + · · · + 1) · · · (pekk + pkek −1 + · · · + 1)  e1 +1   e2 +1   ek +1  p1 − 1 p2 − 1 pk −1 = ··· . p1 − 1 p2 − 1 pk − 1 Adem´as, φ(1), τ (1) y σ(1) se definen como 1. Decimos que una funci´on f es multiplicativa si f (mn) = f (m)f (n) para m y n enteros positivos primos relativos, y f (1) = 1 (de lo contrario, f (1) = 0, que implica que f (n) = 0 para todo n). Teorema 3.1. Las funciones φ, τ y σ son multiplicativas. Por lo tanto tomando la factorizaci´on en primos y evaluando en las potencias de primos, se encuentran f´acilmente la f´ormulas anteriores. Ejemplo 3.1. Encontrar el n´ umero de pares ordenados de enteros positivos (x, y) que son soluci´on de la ecuaci´on 1 1 1 + = , x y n donde n es un entero positivo.

10

Soluci´ on. De la ecuaci´on dada, 1 1 1 + = ⇐⇒ xy = nx + ny ⇐⇒ (x − n)(y − n) = n2 . x y n Si n = 1, inmediatamente deducimos la u ´nica soluci´on (2, 2). Para n > 2, sea ek e1 e2 n = p1 p2 · · · pk la factorizaci´on en primos de n. Como x, y > n, hay una correspondencia uno a uno entre las soluciones en (x, y) y los factores de n2 , entonces el n´ umero de soluciones es τ (n2 ) = (2e1 + 1)(2e2 + 1) · · · (2ek + 1). Ejemplo 3.2. Sea n un entero positivo. Pruebe que X φ(d) = n. d|n

Soluci´ on. Para un divisor d de n, sea Sd el conjunto de todos los a, 1 ≤ a ≤ n, tal que mcd(a, n) = nd . Entonces Sd consiste de todos los elementos de la forma b · nd donde 0 ≤ b ≤ d, y mcd(b, d) = 1, entonces Sd contiene φ(d) elementos. Tambi´en, es claro que cada entero entre 1 y n pertenece a un u ´nico Sd . El resultado entonces sigue de sumar sobre todos los divisores d de n.

Problemas 1. Sea n un entero positivo. Pruebe que n X

τ (k) =

k=1

n j k X n k=1

k

.

2. Sea n un entero positivo. Pruebe que  2 X X τ 3 (d) =  τ (d) . d|n

d|n

3. Pruebe que si σ(N ) = 2N + 1, entonces N es el cuadrado de un entero impar. (1976 Competencia Matem´atica Putnam)

11

4.

Aritm´ etica Modular

Para un entero positivo m, y enteros a y b, decimos que a es congruente a b m´odulo m si m | (a − b), y denotamos esto por a ≡ b modulo m, o m´as comunmente a ≡ b (m´od m). De otro modo, a no es congruente a b m´odulo m, y denotamos esto por a 6≡ b (m´od m) (aunque esta notaci´on no es usada frecuentemente). En esta notaci´on, m se llama m´ odulo, y consideramos los enteros m´ odulo m. Teorema 4.1. Si a ≡ b y c ≡ d (m´od m), entonces a + c ≡ b + d (m´od m) y ac ≡ bd (m´od m). Demostraci´ on. Si a ≡ b y c ≡ d (m´od m), entonces existen enteros k y l tales que a = b + km y c = d + lm. Por lo tanto, a + c = b + d + (k + l)m, luego a + c ≡ b + d (m´od m). Tambi´en ac = bd + dkm + blm + klm2 = bd + (dk + bl + klm)m, entonces ac ≡ bd (m´od m).

´ Resultados Utiles Para todo entero n,   0 n ≡ 1 2

Para todo entero n,   0 2 n ≡ 4   1

 (m´od 4)

si n es par, si n es impar.

 si n ≡ 0 (m´od 4), (m´od 8) si n ≡ 2 (m´od 4),  si n ≡ 1 (m´od 2).

Si f es un polinomio con coeficientes enteros y a ≡ (m´od m), entonces f (a) ≡ f (b) (m´od m). Si f es un polinomio con coeficientes enteros de grado n, no todos identicamente cero, y p un primo, entonces la congruencia f (x) ≡ 0

(m´od p)

tiene como mucho n soluciones m´odulo p, contando multiplicidad. 12

Ejemplo 4.1. Probar que la u ´nica soluci´on en n´ umeros racionales de la ecuaci´on x3 + 3y 3 + 9z 3 − 9xyz = 0 es x = y = z = 0. (1983 Competencia K¨ ursch´ak) Soluci´ on. Supongamos que la ecuaci´on tiene una soluci´on en los racionales, con al menos una variable distinta de cero. C´omo la ecuaci´on es homog´enea, podemos obtener una soluci´on en enteros (x0 , y0 , z0 ) multiplicando la ecuaci´on por el cubo del m´ınimo com´ un m´ ultiplo de los denominadores. Tomando 3 la ecuaci´on m´odulo 3, obtenemos x ≡ 0 (m´od 3). Por lo tanto, x0 debe ser divisible por 3, digamos x0 = 3x1 . Substituyendo, 27x31 + 3y03 + 9z03 − 27x1 y0 z0 = 0 y03 + 3z03 + 9x31 − 9x1 y0 z0 = 0 Por lo tanto, tenemos otra soluci´on (y0 , z0 , x1 ). Podemos aplicar esta reducci´on recursivamente, para obtener y0 = 3y1 , z0 = 3z1 , y otra soluci´on (x1 , y1 , z1 ). Luego, podemos dividir potencias de 3 de nuestra soluci´on un n´ umero arbitrario de veces, contradicci´on. Ejemplo 4.2. ¿Alguno de los primeros 108 + 1 n´ umeros de Fibonacci terminan con cuatro ceros? Soluci´ on. La respuesta es s´ı. Considere la secuencia de pares (Fk , Fk+1 ) m´odulo 104 . Como hay s´olo un n´ umero finito de posibles pares distintos (108 + 1 para ser exactos), y cada par s´olo depende en el anterior, esta secuencia es eventualmente peri´odica. Pero F ≡ 0 (m´od 104 ), luego dentro de 108 t´erminos, otro n´ umero de Fibonacci divisible por 104 debe aparecer. De hecho, una comprobaci´on con computadora muestra que 104 | F7500 , y (Fn ) m´odulo 104 tiene per´ıodo 15000, que es mucho m´as peque˜ no que la 8 cota superior de 10 . Si ax ≡ 1 (m´od m), entonces decimos que x es el inverso de a m´odulo m denotado por a−1 , y es u ´nico m´odulo m. Teorema 4.2. El inverso de a m´odulo m existe y es u ´nico si y s´olo si a es primo relativo a m. Demostraci´ on. Si ax ≡ 1 (m´od m), entonces ax = 1 + km para alg´ un k, ⇒ ax − km = 1. Por el corolario 2.2, a y m son primos relativos. Ahora si mcd(a, m) = 1, entonces por corolario 2.2, existen enteros x e y tales que ax + ym = 1 ⇒ ax = 1 − ym ⇒ ax ≡ 1 (m´od m). El inverso x es u ´nico 0 0 m´odulo m, pues si x es tambi´en un inverso, entonces ax ≡ ax ≡ 1 ⇒ xax = xax0 ⇒ x ≡ x0 . 13

Corolario 4.3. Si p es primo, entonces el inverso de a m´odulo p existe y es u ´nico si y s´olo si p no divide a a. Corolario 4.4. Si ak ≡ bk (m´od m) y k es relativo primo a m entonces a ≡ b (m´od m). Demostraci´ on. Multiplicando ambos lados por k −1 , que existe por el teorema 4.2, obtenemos el resultado buscado. Decimos que un conjunto {a1 , a2 , . . . , am } es un sistema completo de residuos m´odulo m si para todo i, 0 ≤ i ≤ m − 1, entonces existe un u ´nico j tal que aj ≡ i (m´od m). Ejemplo 4.3. Encuentre todos los enteros positivos n tal que existen sistemas completo de residuos {a1 , a2 , . . . , an } y {b1 , b2 , . . . , bn } m´odulo n para los cuales {a1 + b1 , a2 + b2 , . . . , an + bn } es tambi´en un sistema completo de residuos. Demostraci´ on. La respuesta es todo los n impares. Primero probamos la necesidad. Para cualquier sistema completo de residuos {a1 , a2 , . . . , an } m´odulo n, tenemos que a1 + a2 + · · · + an ≡ n(n + 1)/2 (m´od n). Entonces, si los tres conjuntos son sistemas completos de residuos, entonces a1 + a2 + · · · + an + b1 +b2 +· · ·+bn ≡ n2 +n ≡ 0 (m´od n) y a1 +a2 +· · ·+an +b1 +b2 +· · ·+bn ≡ n(n + 1)/2 (m´od n), luego n(n + 1)/2 ≡ 0 (m´od n). La cantidad n(n + 1)/2 es divisible por n si y s´olo si (n + 1)/2 es un entero, lo cual implica que n es impar. Ahora asumamos que n es impar. Sea ai = bi = i para todo i. Entonces ai + bi = 2i para todo i, y n es primo relativos a 2, entonces por el corolario 4.4, {2, 4, . . . , 2n} es un sistema completo de residuos m´odulo m. Teorema 4.5. Teorema de Euler. Si a es un primo relativo a m, entonces aφ(m) ≡ 1 (m´od m). Demostraci´ on. Sean a1 , a2 , . . . , aφ(m) los enteros positivos menores que m que son primos relativos a m. Considere los enteros aa1 , aa2 , . . . , aaφ(m) . Afirmamos que son una permutaci´on de los φ(m) enteros originales ai , m´odulo m. Para cada i, aai tambi´en es primo relativo a m, luego aai ≡ ak para alg´ un k. Como aai ≡ aaj ⇐⇒ ai ≡ aj (m´od m), cada ai es enviado a un ak diferente bajo la multiplicaci´on por a, por lo tanto son permutados. Entonces a1 a2 · · · aφ(m) ≡ (aa1 )(aa2 ) · · · (aaφ(m) ) ≡ aφ(m) a1 a2 · · · aφ(m) ⇒ 1 ≡ aφ(m) 14

(m´od m).

Nota. Esto da una f´ormula expl´ıcita para el inverso de a m´odulo m: a−1 ≡ aφ(m)−2 (m´od m). Alternativamente, podemos usar el algoritmos de Euclides para encontrar a−1 ≡ x como en la demostraci´on del Teorema 4.2. Corolario 4.6. El Peque˜ no Teorema de Fermat (PTF). Si p es primo, y p no divide a a, entonces ap−1 ≡ 1 (m´od p). Ejemplo 4.4. Muestre que si a y b son enteros positivos primos relativos, entonces existen enteros m y n tales que am + bn ≡ 1 (m´od a)b. Soluci´ on. Sea S = am + bn , donde m = φ(b) y n = φ(a). Entonces por el Teorema de Euler, S ≡ bφ(a) equiv1 (m´od a), o S − 1 ≡ 0 (m´od a), y S ≡ aφ(b) ≡ 1 (m´od b), o S − 1 ≡ 0 (m´od b). Por lo tanto S − 1 ≡ 0, o S ≡ 1 (m´od a)b. Ejemplo 4.5. Para todos los enteros positivos i, sea Si la suma de los productos de 1, 2, . . . , p − 1 tomando de a i cada vez, donde p es un primo impar. Muestre que S1 ≡ S2 ≡ · · · ≡ Sp−2 ≡ 0 (m´od p). Soluci´ on. Primero, observe que (x − 1)(x − 2) · · · (x − (p − 1)) = xp−1 − S1 xp−2 + S2 xp−3 − · · · − Sp−2 x + Sp−1 Estos polinomios se anulan para x = 1, 2, . . . , p − 1. Pero por el Peque˜ no Teorema de Fermat, tambi´en se anula xp−1 − 1 m´odulo p. Tomando la diferencia de estos dos polinomios, obtenemos otro polinomio de grado p − 2 con p − 1 raices m´odulo p, luego debe ser el polinomio nulo, y el resultado sigue de comparar coeficientes. Nota. Inmediatamente tenemos que (p − 1)! ≡ Sp−1 ≡ −1 (m´od p), que es el Teorema de Wilson. Tambi´en, xp − x ≡ 0 (m´od p) para todo x, pero aqu´ı no podemos comparar coeficientes. ¿Por qu´e no? Teorema 4.7. Si p es un primo y n es un entero tal que p | (4n2 + 1), entonces p ≡ 1 (m´od 4). Demostraci´ on. Claramente, p no puede ser 2, luego s´olo necesitamos mostrar que p 6≡ 3 (m´od 4). Supongamos que p = 4k + 3 para alg´ un k. Sea y = 2n, luego por el Peque˜ no Teorema de Fermat, y p−1 ≡ 1 (m´od p), como p no divide a n. Pero y 2 + 1 ≡ 0, luego y p−1 ≡ y 4k+2 ≡ (y 2 )2k+1 ≡ (−1)2k+1 ≡ −1 contradicci´on. Por lo tanto p = 2 ´o p ≡ 1 (m´od 4). 15

(m´od p),

Nota. La misma prueba se puede usar para mostrar que si p es un primo y p | (n2 + 1), entonces p = 2 o p ≡ 1 (m´od 4). Ejemplo 4.6. Muestre que existen infinitos n´ umeros primos de la forma 4k + 1 y de la forma 4k + 3. Soluci´ on. Suponga que existen finitos n´ umeros primos de la forma 4k + 1, digamos p1 , p2 , . . . , pn . Sea N = 4(p1 p2 · · · pn )2 + 1. Por el teorema 4.7, N es s´olo divisible por primos de la forma 4k +1, pero claramente N no es divisible por ninguno de estos primos, contradicci´on. Similarmente, supongamos que hay finitos primos de la forma 4k + 3, digamos q1 , q2 , . . . , qm . Sea M = 4q1 q2 · · · qm − 1. Entonces M ≡ 3 (m´od 4), luego M debe ser divisible por un primo de la forma 4k + 3, pero M no es divisible por ninguno de estos primos, contradicci´on. Ejemplo 4.7. Muestre que si n es un entero mayor que 1, entonces n no divide a 2n − 1. Soluci´ on. Sea p el menor primo que divide a n. Entonces mcd(n, p − 1) = 1, y por el corolario 2.2, existen enteros x e y tales que nx + (p − 1)y = 1. Si p | (2n − 1), entonces 2 ≡ 2nx+(p−1)y ≡ (2n )x (2p−1 )y ≡ 1 (m´od p) por el Peque˜ no n n Teorema de Fermat, contradicci´on. Por lo tanto p - (2 − 1) ⇒ n - (2 − 1) Teorema 4.8. Teorema de Wilson. Si p es un primo, entonces (p − 1)! ≡ −1 (m´od p). (Vea tambi´en el ejemplo 4.5.) Demostraci´ on. Considere la congruencia x2 ≡ 1 (m´od p). Entonces x2 − 1 ≡ (x − 1)(x + 1) ≡ 0, luego las u ´nicas soluciones son x ≡ 1 y −1. Por lo tanto, para cada i, 2 ≤ i ≤ p − 2, existe un u ´nico inverso j 6= i de i, 2 ≤ j ≤ p − 2, m´odulo p. Luego, cuando agrupamos en pares de inversos, (p − 1)! ≡ 1 · 2 · · · (p − 2) · (p − 1) ≡ 1 · 1 · · · 1 · (p − 1) ≡ −1 (m´od p). Ejemplo 4.8. Sea {a1 , a2 , . . . , a101 } y {b1 , b2 , . . . , b101 } un sistema completo de residuos m´odulo 101. ¿Puede {a1 b1 , a2 b2 , . . . , a101 b101 } es un sistema completo de residuos m´odulo 101? Soluci´ on. La respuesta es que no. Suponga que {a1 b1 , a2 b2 , . . . , a101 b101 } es un sistema completo de residuos m´odulo 101. Sin p´erdida de generalidad asuma que a101 ≡ 0 (m´od 101). Entonces b101 ≡ 0 (m´od 101), porque si cualquier otro bj fuera congruente a 0 m´odulo 101, entonces aj bj ≡ a101 b101 ≡ 0 16

(m´od 101), contradicci´on. Por el teorema de Wilson, a1 a2 · · · a100 ≡ b1 b2 · · · b100 ≡ 100! ≡ −1 (m´od 101), luego a1 b1 a2 b2 · · · a100 b100 ≡ 1 (m´od 101). Pero a101 b101 ≡ 0 (m´od 101), entonces a1 b1 a2 b2 · · · a100 b100 ≡ 100! ≡ −1 (m´od 101), contradicci´on. Teorema 4.9. Si p es un primo, entonces la congruencia x2 + 1 ≡ 0 (m´od p) tiene soluci´on si y s´olo si p = 2 o p ≡ 1 (m´od 4). (Compare con el teorema ) Demostraci´ on. Si p = 2, entonces x = 1 es una soluci´on. Si p = 3 (m´od 4), entonces por la nota en el teorema 4.7, no existen soluciones. Finalmente si p = 4k + 1, entonces hacemos x = 1 · 2 · · · (2k). Entonces x2 ≡ 1 · 2 · · · (2k) · (2k) · · · 2 · 1 ≡ 1 · 2 · · · (2k) · (−2k) · · · (−2) · (−1) (multiplicando por 2k − 1s) ≡ 1 · 2 · · · (2k) · (p − 2k) · · · (p − 2) · (p − 1) ≡ (p − 1)! ≡ −1 (m´od p). Teorema 4.10. Sea p un primo tal que p ≡ 1 (m´od 4). Entonces existen enteros positivos x y y tales que p = x2 + y 2 . Demostraci´ on. Por el teorema 4.9, existe un entero a tal que a2 ≡ −1 m´od p. Considere el conjunto de enteros de la forma ax − y, donde x y √ y son enteros, 0 ≤ x, y < p. La cantidad de pares posibles es entonces √ √ (b pc + 1)2 > ( p)2 = p, por el principio del palomar, existen enteros √ 0 ≤ x1 , x2 , y1 , y2 < p, tal que ax1 − y1 ≡ ax2 − y2 (m´od p). Sea x = x1 − x2 y y = y1 − y2 . Al menos uno entre x y y es distinto de cero, y ax ≡ y ⇒ a2 x2 ≡ −x2 ≡ y 2 ⇒ x2 + y 2 ≡ 0 (m´od p). Entonces, x2 + y 2 es un m´ ultiplo √ 2 √ 2 2 2 2 2 de p, y 0 < x + y < ( p) + ( p) = 2p, luego x + y = p. Teorema 4.11. Sea n un entero positivo. Entonces existen enteros x y y tal que n = x2 + y 2 si y s´olo si cada factor primo de n de la forma 4k + 3 aparece un n´ umero par de veces. Teorema 4.12. Teorema Chino del Resto (TCR). Si a1 , a2 , . . . , ak son enteros, y m1 , m2 , . . . , mk son primos relativos de a pares, entonces el sistema de congruencias x ≡ a1 x ≡ a2 .. . x ≡ ak

(m´od m1 ), (m´od m2 ), (m´od mk )

tiene una u ´nica soluci´on m´odulo m1 m2 · · · mk . 17

Demostraci´ on. Sea m = m1 m2 · · · mk , y considere m/m1 . Es primo relativo a m1 , luego existe un entero t1 tal que t1 · m/m1 ≡ (m´od m1 ). En consecuencia, sea s1 = t1 · m/m1 . Entonces s1 ≡ 1 (m´od m1 ) y s1 ≡ 0 (m´od mj ), j 6= 1. Similarmente, para todo i, existe si tal que si ≡ 0 (m´od mi ) y si ≡ 0 (m´od mj ), j 6= i. Entonces, x = a1 s1 + a2 s2 + · · · + ak sk es una soluci´on del sistema anterior. Para probar la unicidad, sea x0 otra soluci´on. Entonces x − x0 ≡ 0 (m´od mi ) para todo i ⇒ x − x0 ≡ 0 (m´od m1 m2 · · · mk ). Nota. La demostraci´on muestra expl´ıcitamente como encontrar la soluci´on x. Ejemplo 4.9. Para un entero positivo n, encuentre la cantidad de soluciones de la congruencia x2 ≡ 1 (m´od n). Soluci´ on. Sea la factorizaci´on de n de la forma 2e pe11 pe22 · · · pekk . Por TCR, 2 x ≡ 1 (m´od n) ⇐⇒ x2 ≡ 1 (m´od pei i ) para todo i y x2 ≡ 1 (m´od 2e ). Vamos a considerar estos casos por separado. Tenemos que x2 ≡ 1 (m´od pei i ) ⇐⇒ x2 − 1 = (x − 1)(x + 1) (m´od pei i ). Pero pi no puede dividir a ambos x − 1 y x + 1, luego divide uno de ellos; esto es x ≡ ±1 (m´od pei i ). Luego hay dos soluciones. Ahora, si (x − 1)(x + 1) ≡ 0 (m´od 2e ), 2 puede dividir a x − 1 y a x + 1, pero 4 no puede dividir a ambos. Para e = 1 y e = 2, se puede comprobar f´acilmente que hay una y dos soluciones respectivamente. Para e ≥ 3, como tiene que haber como mucho un factor 2 en uno de los factores x − 1 o x + 1, tiene que haber al menos e − 1 en el otro para que su producto sea divisible por 2e . Por lo tanto, las u ´nicas posibilidades son x − 1 o x + 1 ≡ 0, 2e−1 e (m´od 2 ), lo que lleva a las cuatro soluciones x ≡ 1, 2e−1 − 1, 2e−1 + 1 y 2e − 1. Ahora que conocemos cuantas soluciones cada factor primo contribuye, la cantidad de soluciones m´odulo n es simplemente el producto de estos, por el TCR. La siguiente tabla da la respuesta: e 0, 1 2 ≥3

N´ umero de soluciones 2k 2k+1 2k+2

Teorema 4.13. Sea m un entero positivo, sean a y b enteros, y sea k = mcd(a, b). Entonces la congruencia ax ≡ b (m´od m) tiene k soluciones o no tiene soluciones de acuerdo a si k | b o k - b.

18

Problemas 1. Probar que para cada entero positivo n existen n enteros positivos consecutivos, ninguno de los cuales es una potencia de un primo. (1989 Olimpiada Internacional de Matem´atica) 2. Para un entero positivo impar n > 1, sea S el conjunto de enteros x, 1 ≤ x ≤ n, tales que x y x + 1 son primos relativos de n. Muestre que Y x ≡ 1 (m´od n). x∈S

3. Encuentre todas las soluciones en enteros positivos a 3x + 4y = 5z . (1991 Olimpiada Internacional de Matem´atica - Lista corta) 4. Sea n un entero positivo tal que n + 1 es divisible por 24. Pruebe que la suma de todos los divisores de n es divisible por 24. (1969 Competencia Matem´atica Putnam) 5. (Teorema de Wolsteholme) Pruebe que si 1+

1 1 1 + + ··· + 2 3 p−1

es escrito como fracci´on, donde p > 5 es un primo, entonces p2 divide al numerador. 6. Sea a la ra´ız positiva mas grande de la ecuaci´on x3 − 3x2 + 1 = 0. Muestre que ba1788 c y ba1988 c son divisibles por 17. (1988 Olimpiada Internacional de Matem´atica - Lista corta) 7. Sean {a1 , a2 , . . . , an } y {b1 , b2 , . . . , bn } sistemas completos de residuos m´odulo n, tales que {a1 b1 , a2 b2 , . . . , an bn } es tambi´en un sistema completo de residuos m´odulo n. Muestre que n = 1 ´o 2. 8. Sean m y n enteros positivos. Muestre que 4mn − m − n no puede ser un cuadrado. (1984 Olimpiada Internacional de Matem´atica)

5.

Coeficientes Binomiales

Para los enteros no negativos n y k, k ≤ n, el coeficiente binomial se define como n! , k!(n − k)! 19

n k





y tiene varias propiedades importantes. Por convenci´on, nk = 0 si k > n. En los resultados que siguen, para polinomios f y g con coeficientes enteros, decimos que f ≡ g (m´od m) si m divide a todos los coeficientes de f − g. Teorema 5.1. Si p es un primo, entonces el n´ umero de factores p en n! es       n n n + 2 + 3 + ··· . p p p Tambi´en es

n − sn , p−1 donde sn es la suma de los d´ıgitos de n cuando esta expresado en base p. Teorema 5.2. Si p es un primo, entonces   p ≡ 0 (m´od p) i para 1 ≤ i ≤ p − 1. Corolario 5.3. (1 + x)p ≡ 1 + xp (m´od p) Lema 5.4. Para todos los n´ umeros reales x e y, bx + yc ≥ bxc + bxc. Demostraci´ on. x ≥ bxc ⇒ x+y ≥ bxc+byc ∈ Z, luego bx+yc ≥ bxc+byc. Teorema 5.5. Si p es un primo, entonces  k p ≡ 0 (m´od p) i para 1 ≤ i ≤ pk − 1. Demostraci´ on. Por el lema 5.4,   k  X k  k  k X i p −i p + ≤ , j j p p pj j=1 j=1

donde el lado izquierdo y el lado derecho p en j k sonj elk n´ kumero de j kfactores k p −i p i k k i!(p − i)! y p ! respectivamente. Pero pk = pk = 0 y pk = 1, luego k
la desigualdad es estricta, y por lo menos un factor p divide a pi . k

k

Corolario 5.6. (1 + x)p ≡ 1 + xp (m´od p). 20

Ejemplo 5.1. Sea n un entero positivo. Mostrar que el producto de n enteros positivos consecutivos es divisible por n! Soluci´ on. Si los enteros consecutivos son m, m + 1, . . . , m + n − 1, entonces   m(m + 1) · · · (m + n − 1) m+n−1 = . n! n Ejemplo 5.2. Sea n un entero positivo. Mostrar que       n n n (n + 1) mcm , ,..., = mcm (1, 2, . . . , n). 0 1 n (AMM E2686) Soluci´ on. Sea p un primo ≤ n + 1 y sea α (respectivamente β) la mayor potencia de p en el lado izquierdo (respectivamente el derecho) de la igualdad anterior. Elegimos r tal que pr ≤ n + 1 < pr+1 . Entonces claramente β = r. Afirmamos que   m r r+1 r+1 si p ≤ m < p , entonces p para 0 ≤ k < m. (*) k
En efecto, el n´ umero de factores p en m es k      r  X m k m−k γ= − s − . s s p p p s=1 Como cada sumando en esta suma es 0 o´ 1, tenemos que γ ≤ r, esto es que (*) se cumple. Para 0 ≤ k ≤ n sea       n n+1 n+1 ak = (n + 1) = (n − k + 1) = (k + 1) . k k k+1


n+1 Por (*), pr+1 no divide a ninguno de los enteros nk , n+1 , o ´ . Por lo k k+1 tanto pr+1 divide a ak si y s´olo si p divide a cada uno de los enteros n + 1, n−k+1 y k+1. Esto implica que p divide a (n+1)−(n−k+1)−(k+1) = −1, contradicci´on. Por lo tanto pr+1 para k = pr − 1, tenemos
- ak . Por otro lado, n+1 r que k ≤ n y ak = (k + 1) k+1 es divisible por p . Por lo tanto β = r = α. Teorema 5.7. Teorema de Lucas. Sean m y n enteros no negativos, y sea p un primo. Sean m = mk pk + mk−1 pk−1 + · · · + m1 p + m0 , y n = nk pk + nk−1 pk−1 + · · · + n1 p + n0 21

las expansiones de m y n en base p respectivamente. Entonces         m mk mk−1 m1 m0 ≡ ··· (m´od p). n nk nk−1 n1 n0 Demostraci´ on. Por el corolario 5.6 (1 + x)m ≡ (1 + x)mk p ≡ (1 + x)p

km

k +m

k

k

k−1 p

k−1 +···+m p+m 1 0 k−1 m k−1

(1 + x)p

≡ (1 + xp )mk (1 + xp

k−1

· · · (1 + x)pm1 (1 + x)m0

)mk−1 · · · (1 + xp )m1 (1 + x)m0

(m´od p)

Por la expansi´on en base p, el coeficiente de xn en ambos lados es         m mk mk−1 m1 m0 ≡ ··· (m´od p). n nk nk−1 n1 n0 Corolario 5.8. Sea n un entero positivo. Denotamos con A(n) la cantidad de factores 2 en n!, y denotemos con B(n) la cantidad de d´ıgitos 1 en la expansi´on binaria de n. Entonces la cantidad de entradas impares en la fila n-´esima del Tri´angulo de Pascal, o equivalentemente el n´ umero de coeficientes en la expansi´on de (1 + x)n , es 2B(n) . M´as a´ un, A(n) + B(n) = n para todo n.

Resultados u ´ tiles: Para un polinomio f con coeficientes enteros y p primo, n

n

[f (x)]p ≡ f (xp )

(m´od p).

Problemas 1. Sean a y b enteros no negativos, y p un primo. Mostrar que     pa a ≡ (m´od p). pb b 2. Sea an el u ´ltimo d´ıgito distinto de cero en la representaci´on decimal de el n´ umero n!. ¿La secuencia a1 , a2 , a3 , . . . es eventualmente peri´odica? (1991 Lista Corta - Olimpiada Internacional de Matem´atica) 3. Encuentre todos los enteros positivos n tal que 2n | (3n − 1).

22

4. Encuentre el mayor entero k para el cual 1991k divide a 1992

19901991

1990

+ 19921991

.

(1991 Lista Corta - Olimpiada Internacional de Matem´atica) 5. Para un entero positivo n, sean a(n) y b(n) la cantidad de coeficientes en la n-´esima fila del Tri´angulo de Pascal que son congruentes con 1 y 2 m´odulo 3 respectivamente. Probar que a(n) − b(n) es siempre una potencia de 2. 6. Sea n un entero positivo. Probar que si el n´ umero de factores 2 en n! es n − 1, entonces n es una potencia de 2. 7. Para un enteros positivo n, sea   1 2n Cn = , n+1 n y S n = C1 + C2 + · · · + Cn . Probar que Sn ≡ 1 (m´od 3) si y s´olo si existe un 2 en la expansi´on en base 3 de n + 1.

23