TEORIA DE NUMEROS

Teor´ıa de Nu´meros

Naoki Sato <sato@artofproblemsolving.com>

22 de julio de 2012

Resumen

Estas notas sobre teor´ıa de nu´meros fueron originariamente escri- tas 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 familiariza- do. Este texto se pens´o como una referencia no como un reemplazo, sino como un suplemento para un libro de teor´ıa de nu´meros; varios libros son sugeridos al final. Hay algunas demostraciones cuando sea apropiado o para ilustrar un punto o una idea importante. Los pro- blemas son tomados de varias fuentes, muchos de concursos existentes u olimp´ıadas, y en general son bastante dif´ıciles. El autor agradece cualquier correccion 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 mu´ltiplo 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

n

a | X bi ci

i=1

Teorema 1.1. El Algoritmo de la Division. 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 solo si a | b.

Teorema 1.2. El Teorema Fundamental de la Aritm´etica. Cada entero ma- yor que 1 puede ser escrito de manera u´nica en la forma

pe1 e2 ek

1 p2 • • • pk

donde los pi son primos distintos y los ei son enteros positivos. Teorema 1.3. Euclides. Existen una infinitud de nu´meros primos. Demostracion. Supongamos que hay una cantidad finita de nu´meros pri-

mos, digamos p1, p2, . . . , pn . Sea N = p1p2 • • • pn + 1. Por el teorema funda-

mental de la aritm´etica, N es divisible por algu´n 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 , contradiccion.

Ejemplo 1.1. Sea x e y enteros. Probar que 2x + 3y es divisible por 17 si y solo 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 simultaneamente a n2 + 1 y a (n + 1)2 + 1 para algu´n entero n.

Solucion. 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 solo 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 solucion entera r. Pruebe que

a1 + a2 + • • • + a2n

r = .

2n

(1984 Lista Corta - Olimpiada Internacional de Matematica)

Soluci´on. Claramente r = 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 Matematica Putnam)

Soluci´on. Para cada i, 1 ≤ i ≤ mn + 1, sea ni la longitud de la secuencia mas larga que empieza con ai donde cada t´ermino divide el siguiente, entre los enteros ai , ai+1 , . . . , amn+1 . Si para algu´n 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

U´ tiles

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.

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

1 n

a + +

2

1 n

b +

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.

...