Download Olimpiada Mexicana de Matemáticas

Olimpiada Mexicana de Matemáticas
[Pequeño] Teorema de Fermat.
Si a es un entero y p es un número primo con (a, p)=1, entonces ap-1≡1 (mod p).
Demostración 1. Se puede hacer por inducción sobre a y utilizando el binomio de Newton
para demostrar la hipótesis de inducción. Se deja como ejercicio.
Demostración 2. Consideremos los p-1 enteros a, 2a,…, (p-1)a. Aseguramos que:
1. Entre todos ellos NO hay dos que tengan el mismo residuo módulo n (¿por qué?).
2. Todos ellos son, en algún orden, congruentes a los números 1, 2, …, p-1 (¿por
qué?).
Con esto, el resultado ya es directo:
(a)(2a)…(p-1)a≡(1)(2)…(p-1)
(mod p)
(p-1)!(ap-1) ≡(p-1)!
(mod p)
Como ((p-1)!, p)=1, se puede “cancelar” (p-1)!, quedando ap-1≡1 (mod p).
Demostración 3. Se puede utilizar el Teorema de Euler haciendo n=p. Se deja como
ejercicio.
Demostración 4. Existe una demostración usando teoría de grupos, que utiliza teoremas
ligeramente más avanzados, pero no es muy difícil de entender; se deja como ejercicio de
investigación.
A menudo, el Teorema de Fermat se puede expresar de una manera un poco más general
como sigue:
Si a es un entero y p es un número primo, entonces ap≡a (mod p).
Se puede ver fácilmente así, dividiendo en dos casos:
Caso 1: p|a; entonces ap≡0≡a (mod p).
Caso 2: (a,p)=1; entonces ap-1≡1 (mod p), y multiplicando ambos lados por a se
obtiene el resultado deseado.
Teorema de Euler.
Si a y n son enteros con (a, n)=1, entonces aɸ(n) ≡1 (mod p).
Puede verse como un caso muy general del Teorema de Fermat (en ocasiones se le llama
Teorema de Fermat-Euler). ɸ(n) es la función de Euler (se lee “fi de n”), que especifica el
número de enteros positivos menores que n y primos relativos con n. Así, por ejemplo,
ɸ(5)=4, ɸ(10)=4 y ɸ(15)=8. La función de Euler tiene propiedades muy interesantes (por
ejemplo, ɸ(ab)= ɸ(a) ɸ(b)), y vale la pena darle una revisada a su teoría más adelante.
Demostración 1. La demostración es similar a la demostración 2 del pequeño Teorema de
Fermat, y se deja como ejercicio.
Ejercicios resueltos.
La aplicación de estos teoremas en ejercicios de Olimpiada es obvia en muchos problemas
de congruencias en los que se manejan potencias o series de potencias.
1. ¿Qué residuo deja 21000006 al dividirse entre 101?
Solución: Se puede analizar las potencias de 2, y encontrar un patrón en sus residuos
(que eventualmente se repetirán, pues sólo hay 101 residuos mód 101), pero esto
Delegación Querétaro – Roberto Hernández Jiménez
Page 1
Olimpiada Mexicana de Matemáticas
podría resultar un poco tedioso y, tardado y un poco difícil de conseguir. Una
solución más directa la da el PTF, aprovechando que 101 es primo:
2100≡1 (mod 101)  21000006=26(2100)10000≡26(110000)≡26≡64
Por tanto, el residuo buscado es 64.
2. Encuentra la última cifra de N=3n+2 de acuerdo a una clasificación propuesta de n.
Solución: Nos interesa encontrar N (mód 10). Para ello, observemos que ɸ(10)=4,
de modo que 3 ɸ(10) ≡1 (mod 10), lo que nos garantiza que los residuos se repetirán a
lo más cada 4 veces (pues al final, una de las potencias será congruente a 1 mód 10,
y ahí se empieza a repetir todo nuevamente); luego, 34≡1 (mod 10), 35≡3 (mod 10),
36≡9 (mod 10) y 37≡7 (mod 10), y a partir de aquí se repiten 38≡1 (mod 10), etc.
Luego, la solución es:
3n+2≡3, 5, 1 y 0 (mod 10) si n≡0, 1, 2 y 3 (mod 4), respectivamente.
3. Demuestra que para todo primo p, p|abp-bap.
Solución 1: abp-bap=ab(bp-1-ap-1). Si a ó b son divisibles entre p, terminamos.
Supongamos entonces que (a, p)=(b, p)=1; con esto, bp-1≡1≡ap-1, por el PTF, de
modo que bp-1-ap-1≡0 , (mod p), y también terminamos.
Solución 2: Por el PTF, bp≡b (mod p) y ap≡a (mod p); así, abp-bap≡ab-ab≡0 (mod
p).
Los siguientes ejercicios pueden resolverse usando Fermat/Euler.
4. Encuentra todos los primos p tales que p|2p+1.
5. Demuestra que para todo entero a, 728|a27-a3.
6. Demuestra que 11|52011-5.
7. ¿Qué residuo deja 21000000 al dividirse entre 7?
8. ¿Qué residuo deja 2333+3222 al dividirse entre 5?
9. Sea p>5 un número primo. Demuestra que p|11…111 (p-1 dígitos)
10. Si p>5 es un número primo, demuestra que 240|p8-1.
11. Demuestra que n2-1|2n!-1, con n>1 entero positivo.
12. (IMO 2005) La secuencia infinita de enteros a1, a2, a3,… se calcula como sigue:
an=2n+3n+6n-1
Determina todos los enteros positivos que son primos relativos con cada uno de los
términos de la serie.
13. Demuestra que 49|3105+4105.
14. Encuentra el residuo de dividir a) 272011 entre 77, b) 2741 entre 77.
15. Sean p y q dos números primos. Demuestra que pq|pq-1+qp-1-1
16. Demuestra que ab|aɸ(b)+ bɸ(a)-1.
17. (IMO 2003). Sea p un número primo. Demuestra que existe un número primo q tal
que, para todo entero n, el número np-p no es divisible por q.
Delegación Querétaro – Roberto Hernández Jiménez
Page 2