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, 26 de septiembre de 2011
Problema del día, Teoría de números (26 de Septiembre)
Sea p un primo, demostrar que $(p-1)!+1$ es potencia de $p$ si y solo si $p=2$, $p=3$ o $p=5$
primero, el regreso esta facil. con P=2 tenemos (P-1)!+1=1+1=2 y esto es 2^1. con P=3 tenemos 2+1=3 y es 3^1. con P=5 tenemos (2*3*4)+1=25 y es 5^2.
La ida no lo termino, pero esto llevo. (P-1)!=(P!)/P y digamos P^n la potencia, tenemos con lo anterior:
P!+P=P^(n+1)
tomando n=1 entonces P!=P^2-P=P(P-1) con esto, P no puede pasar 3 o el miembro derecho seria mucho mayor al otro. si n=2 entonces P!=P^3-P=P(P-1)(P+1) y P+1 es par y puede ponerse como (P+1)/2 y 2, entonces tenemos P!=P(P-1)((P+1)/2)(2) y P solo puede ser 5 por tener los mismos factores de un lado y el otro.
para n>2 P! seria mas grande. el argumento no es lo suficientemente fuerte, es lo ke llevo hasta ahora.
No tuve mucho tiempo de pensarlo por examenes pero tuve algunas ideas. Primero por wilson vemos que eso lo divide p, pero no necesariamente es potencia, asi que ya no pude hacer nada mas con eso. Pense en dar valores a las potencias pero ya no vi bien que pasaba, mañana sigo trabajando.
Solo pude demostrar que no es posible para p^2. Primero demostré que se podía para p=2,3,5. Si p=2 entonces (2-1)!+1=1+1=2^1; si p=3, (3-1)!+1=2+1=3^1 y si p=5, (5-1)!+1=24+1=5^2. Si p=7, (7-1)!+1=721 que no es potencia de 7, como el siguiente primo es 11, sólo consideraré 10<p. Como los primos son congruentes a 1,-1 mod 6, entonces un primo se puede escribir como 6k+1 o 6k-1 con k<p. Si (p-1)!+1=p^2, (p-1)!+1 es igual a (6k+1)^2 o (6k-1)^2. En el caso de que es igual a (6k+1)^2, es igual a 36k^2+12k+1, como (p-1)!+1=p^2, (p-1)!=p^2-1=36k^2+12k=12k(3k+1); como el siguiente primo es 11, al menos (p-1)!=1*2*3*(2*2)*5*(2*3)*7*(2*2*2)*(3*3)*(2*5) donde k es alguno de los factores y 12k=2*2*3*k. (p-1)!/12k=(1*2^6*3^3*5^2*7)/k=3k+1; como (p-1)!/12k tiene al menos un factor 3 no puede ser igual a 3k+1 y es una contradicción. Si (p-1)!+1=(6k-1)^2, es el mismo procedimiento y sólo se cambia 36k^2+12k+1 por 36k^2-12k+1, y 3k+1 por 3k-1. Pero no se como se demuestre para una potencia mayor a 2.
primero tenemos que con p=2enotnces (p-1)!+1=2=2^1 p=3 enotnces (p-1)!+1=3=3^1, p=5 entonces (p-1)!+1=25=5^2 aqui queda demostrada la ida. y en el regreso (p-1)!+1 va a terminar en 1 porque el caso de p=7 no cumple enotnces p> o = a 10 porque el proximo numero primo es 11 entonces (p-1)! se va a multiplicar por 10 y +1 entonces terminara en 1, y sabemos que p^n va a terminar en 1 para todo p>=11 y p^n debe ser multiplo de 1,2,3,...,10 porque en el (p-1)! se estaria incluyendo un 10! y 10!=3718800 y p^n va a ser igual a un multiplo de 3718801 entonces p^n=(3718801)(10k) el 10k porque p^n termian en 1 y 3718801 se debera de multiplicar por un multipli de 10 para que termine en 1 y aqui tenemos que 10k divide a p^n y llegamos a una contradiccion porque 10k solo va a dividir a numeros terminados en 0 y p^n termina en 1 enotnces p debe ser menor a 11 y nos quedan p=2,3,5,7 pero si lo hacemos con el caso p=7 no se cupmle entonces solamente p va a ser igual a 2,3 y 5
Llamemos $(p-1)! + 1$ como $Z$. Desarrollando un poco se puede afirmar que para cualquier $p>5$, $Z \equiv 1 \pmod{10}$, ya que a partir de $p>5$, $(p-1)! $ tendrá al menos un cero en el último digito (Al multiplicar 2 y 5), y al sumarle uno obtendremos esa congruencia. Entonces para que cualquier $p>5$ cumpla con que $Z$ es igual a potencia de $p$; la potencia de $p$ debe terminar en $1$. Dado que multiplicar $p- (p-1) = 1$ no afecta nuestro procedimiento, lo suprimiremos para un manejo más sencillo de datos. Por ejemplo cuando $p=5$, $(p-1)! + 1$ $= (5-1)(5-2)(5-3) + 1 = 25$ $= ( -1 \pmod{5}) (-2 \pmod{5}) (-3 \pmod{5}) + 1$ $= -6 \pmod{5} + 1 = -5 \pmod{5} = 25$ Observamos que al multiplicar las congruencias de módulos obtuvimos -6 \pmod{5}, y al sumarle el $1$ esta ecuación se volvió múltiplo de 5. Cuando $p>5$, ya estaba claro que $(p-1)!$ tendría al menos un cero como ultimo digito. Entonces al hacer lo mismo que con $p=5$, trabajar un poco con módulos, en el punto final obtendríamos algo así: $= -10k \pmod{p} + 1$ Donde $k$ es cualquier natural. Entonces a algún múltiplo de $p$ tendríamos que sumarle $-10k + 1$, donde esto último nos da un numero negativo que termina en $9$. Como ya habíamos dicho, si $p>5$, su potencia debe terminar en $1$ para cumplir con $Z$. Para que se cumpla esto, tendríamos que hacer, $p^n + (-10k + 1)$. (Donde $n$ es cualquier natural.) Y si la potencia de $p$ debe terminar en $1$, $p^n$ debe terminar en $0$ (Para que al sumarle $-10k + 1$ este termine en $1$). Lo que nos lleva a una contradicción, ya que no es posible que la potencia de un primo tenga un $0$ como ultimo digito. Entonces solo nos queda la opción donde, $p\le5$, y los únicos primos dentro de este rango son $2$, $3$ y $5$. Para $p=2$: $(2-1)! + 1 = 1 + 1 = 2$ Para $p=3$: $(3-2)! + 1 = (1)(2) + 1 = 2 + 1 = 3$ Para $p=5$: $(5-4)! + 1 = (1)(2)(3)(4) + 1 = 24 + 1 = 25$ Vemos entonces que, $Z$ es potencia de $p$, si y solo si, $p=2$, $p=3$ o $p=5$.
Bueno el regreso es facil: (2-1)!+1=2=2^1 (3-1)!+1=3=3^1 (5-1)!+1=25=5^2
Ahora lo dificil es la ida, primero e indentado bastante probarlo con wilson, que realmente creo que tiene mucho que ver por la semejanza de terminos que se dan, por el sabemos que (p-1)!+1≡0(mod p), por lo que p^n≡0(mod p) suponiendo que si cumple, pero realmente no lo e desarrollado lo suficiente para llegar a algo. Tambien intente desarrollar (p-1)!=p!/p, por lo que (p!/p)+1≡0(mod p). Hasta ahorita llevo esto, seguire intentando, no habia hecho mucho porque estaba en examenes pero espero reponerme con el blog rapido jeje
@Alberto Ponce: Bonitas observaciones, creo que es un buen comienzo… pero síguele que aun no te sale!! xD
@Alberto: Ya pasó una semana, inténtalo de verdad ¬¬
@Luis Chacón: ¿Qué pasa si k=3^3? ¿Por qué k no puede contener a todos los factores 3 que eliminen los existentes en (p-1)!/12 y eviten que sea múltiplo de 3?
@Antonio López: (p-1)! + 1 termina en 1 (p-1)! Es múltiplo de 10 cuando p mayor a 5 Pero (p-1)!+1 no necesariamente debe ser múltiplo de 10!+1, es como decir : ya que (6-1)!=120, entonces (7-1)!+1 es múltiplo de 121 lo que claramente no es cierto. El resto es mentira por lo anterior.
@Alejandro Reyes: No entiendo de qué manera va a salir el signo menos en 10 k (modp) +1 Si saliera, no puedes utilizarlo fuera del modulo, porque puedes llegar a cosas raras como 3=-7 (mod10) , entonces 5+3= 5-7= -2, lo que claramente no es cierto. ¿Por qué a algún múltiplo de p hay que sumarle -10k +1?
@Padilla: ammm no se que decir porque no hay mucho que revisar jeje
NOTA: Yo se que esto no es concurso de redacción, pero si fueran tan amables en la medida de lo posible de utilizar comas y revisar que al menos ustedes entiendan fácilmente lo que están diciendo, se los agradecería mucho jaja … de verdad que es difícil intentar adivinar que estaban pensando D:
primero, el regreso esta facil. con P=2 tenemos (P-1)!+1=1+1=2 y esto es 2^1. con P=3 tenemos 2+1=3 y es 3^1. con P=5 tenemos (2*3*4)+1=25 y es 5^2.
ResponderBorrarLa ida no lo termino, pero esto llevo. (P-1)!=(P!)/P y digamos P^n la potencia, tenemos con lo anterior:
P!+P=P^(n+1)
tomando n=1 entonces P!=P^2-P=P(P-1) con esto, P no puede pasar 3 o el miembro derecho seria mucho mayor al otro. si n=2 entonces P!=P^3-P=P(P-1)(P+1) y P+1 es par y puede ponerse como (P+1)/2 y 2, entonces tenemos P!=P(P-1)((P+1)/2)(2) y P solo puede ser 5 por tener los mismos factores de un lado y el otro.
para n>2 P! seria mas grande. el argumento no es lo suficientemente fuerte, es lo ke llevo hasta ahora.
No tuve mucho tiempo de pensarlo por examenes pero tuve algunas ideas. Primero por wilson vemos que eso lo divide p, pero no necesariamente es potencia, asi que ya no pude hacer nada mas con eso. Pense en dar valores a las potencias pero ya no vi bien que pasaba, mañana sigo trabajando.
ResponderBorrarSolo pude demostrar que no es posible para p^2. Primero demostré que se podía para p=2,3,5. Si p=2 entonces (2-1)!+1=1+1=2^1; si p=3, (3-1)!+1=2+1=3^1 y si p=5, (5-1)!+1=24+1=5^2. Si p=7, (7-1)!+1=721 que no es potencia de 7, como el siguiente primo es 11, sólo consideraré 10<p. Como los primos son congruentes a 1,-1 mod 6, entonces un primo se puede escribir como 6k+1 o 6k-1 con k<p. Si (p-1)!+1=p^2, (p-1)!+1 es igual a (6k+1)^2 o (6k-1)^2. En el caso de que es igual a (6k+1)^2, es igual a 36k^2+12k+1, como (p-1)!+1=p^2, (p-1)!=p^2-1=36k^2+12k=12k(3k+1); como el siguiente primo es 11, al menos (p-1)!=1*2*3*(2*2)*5*(2*3)*7*(2*2*2)*(3*3)*(2*5) donde k es alguno de los factores y 12k=2*2*3*k. (p-1)!/12k=(1*2^6*3^3*5^2*7)/k=3k+1; como (p-1)!/12k tiene al menos un factor 3 no puede ser igual a 3k+1 y es una contradicción. Si (p-1)!+1=(6k-1)^2, es el mismo procedimiento y sólo se cambia 36k^2+12k+1 por 36k^2-12k+1, y 3k+1 por 3k-1. Pero no se como se demuestre para una potencia mayor a 2.
ResponderBorrarprimero tenemos que con p=2enotnces (p-1)!+1=2=2^1
ResponderBorrarp=3 enotnces (p-1)!+1=3=3^1, p=5 entonces (p-1)!+1=25=5^2 aqui queda demostrada la ida.
y en el regreso (p-1)!+1 va a terminar en 1 porque el caso de p=7 no cumple enotnces p> o = a 10 porque el proximo numero primo es 11 entonces (p-1)! se va a multiplicar por 10 y +1 entonces terminara en 1, y sabemos que p^n va a terminar en 1 para todo p>=11 y p^n debe ser multiplo de 1,2,3,...,10 porque en el (p-1)! se estaria incluyendo un 10! y 10!=3718800 y p^n va a ser igual a un multiplo de 3718801 entonces
p^n=(3718801)(10k) el 10k porque p^n termian en 1 y 3718801 se debera de multiplicar por un multipli de 10 para que termine en 1 y aqui tenemos que 10k divide a p^n y llegamos a una contradiccion porque 10k solo va a dividir a numeros terminados en 0 y p^n termina en 1 enotnces p debe ser menor a 11 y nos quedan p=2,3,5,7 pero si lo hacemos con el caso p=7 no se cupmle entonces solamente p va a ser igual a 2,3 y 5
Llamemos $(p-1)! + 1$ como $Z$. Desarrollando un poco se puede afirmar que para cualquier $p>5$, $Z \equiv 1 \pmod{10}$, ya que a partir de $p>5$, $(p-1)! $ tendrá al menos un cero en el último digito (Al multiplicar 2 y 5), y al sumarle uno obtendremos esa congruencia. Entonces para que cualquier $p>5$ cumpla con que $Z$ es igual a potencia de $p$; la potencia de $p$ debe terminar en $1$.
ResponderBorrarDado que multiplicar $p- (p-1) = 1$ no afecta nuestro procedimiento, lo suprimiremos para un manejo más sencillo de datos. Por ejemplo cuando $p=5$,
$(p-1)! + 1$
$= (5-1)(5-2)(5-3) + 1 = 25$
$= ( -1 \pmod{5}) (-2 \pmod{5}) (-3 \pmod{5}) + 1$
$= -6 \pmod{5} + 1 = -5 \pmod{5} = 25$
Observamos que al multiplicar las congruencias de módulos obtuvimos -6 \pmod{5}, y al sumarle el $1$ esta ecuación se volvió múltiplo de 5.
Cuando $p>5$, ya estaba claro que $(p-1)!$ tendría al menos un cero como ultimo digito. Entonces al hacer lo mismo que con $p=5$, trabajar un poco con módulos, en el punto final obtendríamos algo así:
$= -10k \pmod{p} + 1$
Donde $k$ es cualquier natural. Entonces a algún múltiplo de $p$ tendríamos que sumarle $-10k + 1$, donde esto último nos da un numero negativo que termina en $9$.
Como ya habíamos dicho, si $p>5$, su potencia debe terminar en $1$ para cumplir con $Z$. Para que se cumpla esto, tendríamos que hacer, $p^n + (-10k + 1)$. (Donde $n$ es cualquier natural.) Y si la potencia de $p$ debe terminar en $1$, $p^n$ debe terminar en $0$ (Para que al sumarle $-10k + 1$ este termine en $1$). Lo que nos lleva a una contradicción, ya que no es posible que la potencia de un primo tenga un $0$ como ultimo digito.
Entonces solo nos queda la opción donde, $p\le5$, y los únicos primos dentro de este rango son $2$, $3$ y $5$.
Para $p=2$:
$(2-1)! + 1 = 1 + 1 = 2$
Para $p=3$:
$(3-2)! + 1 = (1)(2) + 1 = 2 + 1 = 3$
Para $p=5$:
$(5-4)! + 1 = (1)(2)(3)(4) + 1 = 24 + 1 = 25$
Vemos entonces que, $Z$ es potencia de $p$, si y solo si, $p=2$, $p=3$ o $p=5$.
una disculpa en el primer parrafo que puse en mi comentario era el regreso y el segundo parrafo era la ida, o sea al reves a como yo lo puse.
ResponderBorrarBueno el regreso es facil:
ResponderBorrar(2-1)!+1=2=2^1
(3-1)!+1=3=3^1
(5-1)!+1=25=5^2
Ahora lo dificil es la ida, primero e indentado bastante probarlo con wilson, que realmente creo que tiene mucho que ver por la semejanza de terminos que se dan, por el sabemos que (p-1)!+1≡0(mod p), por lo que p^n≡0(mod p) suponiendo que si cumple, pero realmente no lo e desarrollado lo suficiente para llegar a algo.
Tambien intente desarrollar (p-1)!=p!/p, por lo que (p!/p)+1≡0(mod p).
Hasta ahorita llevo esto, seguire intentando, no habia hecho mucho porque estaba en examenes pero espero reponerme con el blog rapido jeje
@Alberto Ponce: Bonitas observaciones, creo que es un buen comienzo… pero síguele que aun no te sale!! xD
ResponderBorrar@Alberto: Ya pasó una semana, inténtalo de verdad ¬¬
@Luis Chacón: ¿Qué pasa si k=3^3? ¿Por qué k no puede contener a todos los factores 3 que eliminen los existentes en (p-1)!/12 y eviten que sea múltiplo de 3?
@Antonio López:
(p-1)! + 1 termina en 1
(p-1)! Es múltiplo de 10 cuando p mayor a 5
Pero (p-1)!+1 no necesariamente debe ser múltiplo de 10!+1, es como decir : ya que (6-1)!=120, entonces (7-1)!+1 es múltiplo de 121 lo que claramente no es cierto.
El resto es mentira por lo anterior.
@Alejandro Reyes:
No entiendo de qué manera va a salir el signo menos en 10 k (modp) +1
Si saliera, no puedes utilizarlo fuera del modulo, porque puedes llegar a cosas raras como 3=-7 (mod10) , entonces 5+3= 5-7= -2, lo que claramente no es cierto.
¿Por qué a algún múltiplo de p hay que sumarle -10k +1?
@Padilla: ammm no se que decir porque no hay mucho que revisar jeje
NOTA: Yo se que esto no es concurso de redacción, pero si fueran tan amables en la medida de lo posible de utilizar comas y revisar que al menos ustedes entiendan fácilmente lo que están diciendo, se los agradecería mucho jaja … de verdad que es difícil intentar adivinar que estaban pensando D: