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, 11 de enero de 2010
Problema
Demuestra que si (n-1)!=-1mod n entonces n es primo. Este resultado se considera de Gauss, yo lo resolvi hace poquito y no se me hizo muy dificil.
por el teorema de wilson tenemos que (p-1)!=-1 mod n si y solo si n es primo.. DEMOSTRADO!!jajaja ok ia se vio muy mamn... ahi va:
digamos que n no es primo,es decir, es compuesto (duuh), entonces n tiene un divisor k diferente de n y 1, asi, k>1, n>k.
mcm(n-1,n)=1, asi, tenemos que k divide a (n-1)!....
pero el teorema nos dice que (n-1)!=-1modn, lo que significa que (n-1)!+1=0modn, asi, tenemos que k tambien divide a (n-1)!+1, lo cual, nos lleva a que k debe ser 1, puesto que (n-1)! y (n-1)!+1 son primos relativos, luego aqui tenemos una contradiccion, ya que de un principio supusimos que n>k>1. por lo tanto, n es no compuesta.. N ES PRIMA!!!! (Q.E.D.)
saludos! (si hay un error avisen) P.S. (LA RAPADA STA PROXIMA)
***SPOILER*** Demostremoslo por contradiccion Supongamos que n es compuesto entonces n=p1^a1 * p2^a2 * ... pr^ar Entonces (n-1)!=-1mod n, es equivalente al sistema de congruencias: (n-1)!=-1mod p1^a1 (n-1)!=-1mod p2^a2 ... (n-1)!=-1mod pr^ar Pero por otro lado como pj^aj<n para cualquier j entonces (n-1)!=0 mod pj^aj ya que en el factorial aparece el numero pj^aj y pj^aj=0 mod pj^aj Y entonces tenemos una contradiccion.
Algo interesante siguiendo la idea de mi demostracion es que (n-1)!=0mod n si n es compuesto
Si n es compuesto entonces n=p1^a1 * p2^a2 * ... pr^ar Como pj^aj<n para cualquier j entonces (n-1)!=0 mod pj^aj ya que en el factorial aparece el numero pj^aj y pj^aj=0 mod pj^aj. Entonces tenemos el sistema de congruencias. (n-1)!=0mod p1^a1 (n-1)!=0mod p2^a2 ... (n-1)!=0mod pr^ar
aah ya vi que esta mal xD la sentencia: "como pj^aj<n para cualquier j" es cierta para numeros que no son de la forma p^k.
Corrigiendo Caso n=p^k subcaso n=4 4*3*2*1=2mod4 subcaso n= p^2 y 2<p
Es suficiente que los numeros p y 2p aparezcan en (n-1)! Sabemos que p<p^2 Ademas 2<p multiplicamos ambos lados por p 2p<p^2 por lo que p y 2p aparecen en (n-1)!
subcaso n=p^k con 3<=k Es suficiente que aparezcan p^i y p^(k-i) con i<=i en (n-1)! pero p^i<p^k y p^(i-k)<p^k, por lo que aparecen en el (n-1)!
Por lo tanto (n-1)!=0 mod n si n es compuesto y diferente de 4
otra correccion.. nada mas de escritura.. lo demas se ve bonito.. XD
dijiste :
Corrigiendo Caso n=p^k subcaso n=4 4*3*2*1=2mod4 subcaso n= p^2 y 2<p
pero, 4*3*2*1=0mod4 lo correcto seria, 3*2*1=2mod4...
ok... kreo la opcion de declararme remiso la tomare como LA PRIMERA K DESCARTE haha k weba ir despues.. isai..pon mas problemas.. hace un monton k no ponen d geometria.. o KIKE,.. k suba otros del PUTNAM.. jeje saludos pues!
un argumento mas sencillo para tu afirmacion (k a fin d cuentas es lo mismo k tudijiste) seria:
P.D. (n-1)!=0 mod n si n es compuesto y diferente de 4.
demostracion: (n-1)! contiene a todos los divisores de n (ya que n ES COMPUESTA). Entonces, si tiene a todos los divisores de n, excluyendo al mismo n, concluimos diciendo que la afirmacion es cierta. (el caso del 4 es facil de notar, ya que es de la forma p^p, con p prima, pero p=2 es el UNICO primo par, lo que nos garantiza que en otros numeros de la misma forma la sentencia sera "aplicable").
Es el inverso del teorema de wilson =O
ResponderBorrares el d wilson..
ResponderBorraraja..!!
tonz la demostracion aki va:
por el teorema de wilson tenemos que (p-1)!=-1 mod n si y solo si n es primo.. DEMOSTRADO!!jajaja
ok ia se vio muy mamn... ahi va:
digamos que n no es primo,es decir, es compuesto (duuh), entonces n tiene un divisor k diferente de n y 1, asi, k>1, n>k.
mcm(n-1,n)=1, asi, tenemos que k divide a (n-1)!....
pero el teorema nos dice que
(n-1)!=-1modn, lo que significa que (n-1)!+1=0modn, asi, tenemos que k tambien divide a (n-1)!+1, lo cual, nos lleva a que k debe ser 1, puesto que (n-1)! y (n-1)!+1 son primos relativos, luego aqui tenemos una contradiccion, ya que de un principio supusimos que n>k>1. por lo tanto, n es no compuesta.. N ES PRIMA!!!! (Q.E.D.)
saludos!
(si hay un error avisen)
P.S.
(LA RAPADA STA PROXIMA)
***SPOILER***
ResponderBorrarDemostremoslo por contradiccion
Supongamos que n es compuesto
entonces n=p1^a1 * p2^a2 * ... pr^ar
Entonces (n-1)!=-1mod n, es equivalente al sistema de congruencias:
(n-1)!=-1mod p1^a1
(n-1)!=-1mod p2^a2
...
(n-1)!=-1mod pr^ar
Pero por otro lado
como pj^aj<n para cualquier j
entonces
(n-1)!=0 mod pj^aj ya que en el factorial aparece el numero pj^aj y
pj^aj=0 mod pj^aj
Y entonces tenemos una contradiccion.
***END OF SPOILER***
ResponderBorrarwow daniel lo publico un minuto antes xD
ResponderBorrarNomas se conoce como teorema de wilson a (p-1)!=-1mod p
ResponderBorrarel inverso tiene otro nombre
Fuente:wikipedia xD
Y tu solucion es correcta daniel
ResponderBorraroooukei!! (y)
ResponderBorrarAlgo interesante siguiendo la idea de mi demostracion es que (n-1)!=0mod n si n es compuesto
ResponderBorrarSi n es compuesto
entonces n=p1^a1 * p2^a2 * ... pr^ar
Como pj^aj<n para cualquier j
entonces
(n-1)!=0 mod pj^aj ya que en el factorial aparece el numero pj^aj y
pj^aj=0 mod pj^aj.
Entonces tenemos el sistema de congruencias.
(n-1)!=0mod p1^a1
(n-1)!=0mod p2^a2
...
(n-1)!=0mod pr^ar
y por lo tanto
(n-1)!=0 mod n si n es compuesto.
Y diferente de 4...
ResponderBorraraah ya vi que esta mal xD
ResponderBorrarla sentencia:
"como pj^aj<n para cualquier j" es cierta para numeros que no son de la forma p^k.
Corrigiendo
Caso n=p^k
subcaso n=4
4*3*2*1=2mod4
subcaso n= p^2 y 2<p
Es suficiente que los numeros p y 2p aparezcan en (n-1)!
Sabemos que p<p^2
Ademas
2<p multiplicamos ambos lados por p
2p<p^2
por lo que p y 2p aparecen en (n-1)!
subcaso n=p^k con 3<=k
Es suficiente que aparezcan p^i y p^(k-i) con i<=i en (n-1)!
pero p^i<p^k
y p^(i-k)<p^k, por lo que aparecen en el (n-1)!
Por lo tanto (n-1)!=0 mod n si n es compuesto y diferente de 4
si las dos soluciones se ven correctas.Creo que debo poner problemas mas dificiles :)
ResponderBorrarjaja.. creo k si..
ResponderBorrarHECTOR!!!! NECESITO EL ACTA DE NACIMIENTO PARA SOLICITAR LA CARTILLA MILITAR!!!! dnd t encuentro???
saludos!
No la solicites xD, se un remiso como yo jajaj
ResponderBorrarotra correccion.. nada mas de escritura.. lo demas se ve bonito.. XD
ResponderBorrardijiste :
Corrigiendo
Caso n=p^k
subcaso n=4
4*3*2*1=2mod4
subcaso n= p^2 y 2<p
pero, 4*3*2*1=0mod4
lo correcto seria, 3*2*1=2mod4...
ok... kreo la opcion de declararme remiso la tomare como LA PRIMERA K DESCARTE haha k weba ir despues.. isai..pon mas problemas.. hace un monton k no ponen d geometria.. o KIKE,.. k suba otros del PUTNAM.. jeje saludos pues!
un argumento mas sencillo para tu afirmacion (k a fin d cuentas es lo mismo k tudijiste) seria:
ResponderBorrarP.D. (n-1)!=0 mod n si n es compuesto y diferente de 4.
demostracion:
(n-1)! contiene a todos los divisores de n (ya que n ES COMPUESTA). Entonces, si tiene a todos los divisores de n, excluyendo al mismo n, concluimos diciendo que la afirmacion es cierta. (el caso del 4 es facil de notar, ya que es de la forma p^p, con p prima, pero p=2 es el UNICO primo par, lo que nos garantiza que en otros numeros de la misma forma la sentencia sera "aplicable").
Buscare mas problemas, oye te has fijado que nomas tu y yo spameamos todo el blog xD
ResponderBorrarasi es.. shale.. weno.. tambien carlos
ResponderBorrar