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.

18 comentarios:

  1. Es el inverso del teorema de wilson =O

    ResponderBorrar
  2. es el d wilson..

    aja..!!
    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)

    ResponderBorrar
  3. ***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.

    ResponderBorrar
  4. wow daniel lo publico un minuto antes xD

    ResponderBorrar
  5. Nomas se conoce como teorema de wilson a (p-1)!=-1mod p
    el inverso tiene otro nombre
    Fuente:wikipedia xD

    ResponderBorrar
  6. 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

    y por lo tanto
    (n-1)!=0 mod n si n es compuesto.

    ResponderBorrar
  7. 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

    ResponderBorrar
  8. si las dos soluciones se ven correctas.Creo que debo poner problemas mas dificiles :)

    ResponderBorrar
  9. jaja.. creo k si..

    HECTOR!!!! NECESITO EL ACTA DE NACIMIENTO PARA SOLICITAR LA CARTILLA MILITAR!!!! dnd t encuentro???

    saludos!

    ResponderBorrar
  10. No la solicites xD, se un remiso como yo jajaj

    ResponderBorrar
  11. 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!

    ResponderBorrar
  12. 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").

    ResponderBorrar
  13. Buscare mas problemas, oye te has fijado que nomas tu y yo spameamos todo el blog xD

    ResponderBorrar
  14. asi es.. shale.. weno.. tambien carlos

    ResponderBorrar