La comunidad de olímpicos, ex-olímpicos, entrenadores y seguidores de la Olimpiada en Chihuahua, wherever they are in the world.
Por supuesto cualquier olímpico mexicano (para que parar ahí, de todo el mundo pues), esta invitado a comentar.
lunes, 8 de febrero de 2010
Problema del dia (Feb-8)
Ahí les va un problema de teoría de números:
Sea p un primo, demostrar que hay infinitos enteros positivos n tal que p divide a 2^n - n
Para p > 2, 2^(p-1) = 1 mod p, por lo tanto si n=0 mod p-1, 2^n = 1 mod p. Entonces s n = 1 mod p, tenemos 2^n = n mod p. Como p-1 y p son primos relativos, por el teorema chino del residuo existe una solución modulo (p-1)(p) para n. Por lo tanto hay infinitas soluciones mod p a la ecuación 2^n = n mod p, que implica que hay infinitos n tales que p divide a 2^n - n.
*** SPOILER *** Para p = 2, agarrar n par (como lo hizo kiks jeje)
Caso p>=3 Fijemonos en la secuencia de congruencias 2^n mod p. Es claro que 2^n =/= 0 mod p (si no les queda claro estan muy mal jaja). Ahora busquemos un ciclo en la secuencia de congruencias, pero es suficiente con que se repita una, y como tenemos un numero finito de congruencias entonces esto sucede. Entonces en la secuencia hay un ciclo de tamaño menor que p. ( que de hecho es de p-1, pero no supe como demostrarlo).
Ahora fijemonos en la secuencia de congruencias n mod p. Es claro que esta secuencia es 1,2,3,...,p,1,2,3,...,p,...
(Ahora viene un paso que no estoy seguro si esta bien explicado) Ahora como gcd(p,k)=1 (k es el tamaño del ciclo de las 2^n), y el segundo ciclo tiene todas las congruencias que pudiera tener el primer ciclo, entonces hay infinitas coincidencias entre los dos ciclos. Y por lo tanto infinitas n que cumplen que 2^n=n mod p para una p dada. *** END OF SPOILER ***
Isai: Tu segundo paso es correcto. Puedes usar el teorema chino del rediduo u otros argumentos, pero está bien. Donde dices que el ciclo es de p-1, eso es incorrecto. Se puede decir que es un divisor de p-1, pero no se puede decir que es p-1. De hecho, uno de los problemas más famosos de teoría de números, es demostrar que para infinitos primos, el ciclo tiene tamaño p-1. Se llama la conjetura de Artin. La conjetura es un poco más general, porque dice que para cualquier a no cuadrado, a^n tiene ciclo de p-1 para infinitos primos p. Heath-Brown demostró que hay a lo más dos enteros a, tales que no cumplen la infinidad de primos, pero no se sabe de ningún número en particular que cumpla la infinidad de primos.
ooh que interesante!, es que como vi algunos casos y vi que era p-1 en esos casos dije, ha de ser p-1 jajaja, pero como era irrelevante en mi arugmento entonces no me preocupo mucho eso jeje, mas bien en mi parentesis debi haber dicho "parece que es p-1".
SPOILER:
ResponderBorrarPara p = 2, agarra n par y listo.
Para p > 2, 2^(p-1) = 1 mod p, por lo tanto si n=0 mod p-1, 2^n = 1 mod p. Entonces s n = 1 mod p, tenemos 2^n = n mod p.
Como p-1 y p son primos relativos, por el teorema chino del residuo existe una solución modulo (p-1)(p) para n. Por lo tanto hay infinitas soluciones mod p a la ecuación 2^n = n mod p, que implica que hay infinitos n tales que p divide a 2^n - n.
*** SPOILER ***
ResponderBorrarPara p = 2, agarrar n par (como lo hizo kiks jeje)
Caso p>=3
Fijemonos en la secuencia de congruencias 2^n mod p. Es claro que 2^n =/= 0 mod p (si no les queda claro estan muy mal jaja). Ahora busquemos un ciclo en la secuencia de congruencias, pero es suficiente con que se repita una, y como tenemos un numero finito de congruencias entonces esto sucede. Entonces en la secuencia hay un ciclo de tamaño menor que p. ( que de hecho es de p-1, pero no supe como demostrarlo).
Ahora fijemonos en la secuencia de congruencias n mod p. Es claro que esta secuencia es 1,2,3,...,p,1,2,3,...,p,...
(Ahora viene un paso que no estoy seguro si esta bien explicado)
Ahora como gcd(p,k)=1 (k es el tamaño del ciclo de las 2^n), y el segundo ciclo tiene todas las congruencias que pudiera tener el primer ciclo, entonces hay infinitas coincidencias entre los dos ciclos. Y por lo tanto infinitas n que cumplen que 2^n=n mod p para una p dada.
*** END OF SPOILER ***
Isai:
ResponderBorrarTu segundo paso es correcto. Puedes usar el teorema chino del rediduo u otros argumentos, pero está bien.
Donde dices que el ciclo es de p-1, eso es incorrecto. Se puede decir que es un divisor de p-1, pero no se puede decir que es p-1. De hecho, uno de los problemas más famosos de teoría de números, es demostrar que para infinitos primos, el ciclo tiene tamaño p-1. Se llama la conjetura de Artin.
La conjetura es un poco más general, porque dice que para cualquier a no cuadrado, a^n tiene ciclo de p-1 para infinitos primos p.
Heath-Brown demostró que hay a lo más dos enteros a, tales que no cumplen la infinidad de primos, pero no se sabe de ningún número en particular que cumpla la infinidad de primos.
ooh que interesante!, es que como vi algunos casos y vi que era p-1 en esos casos dije, ha de ser p-1 jajaja, pero como era irrelevante en mi arugmento entonces no me preocupo mucho eso jeje, mas bien en mi parentesis debi haber dicho "parece que es p-1".
ResponderBorrarToma un unemro par 2k entonces para n=(p-1)^(2k) tenemos 2^n=1=n mod p QED.
ResponderBorrar