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.
martes, 2 de octubre de 2012
Problema del día. Teoría de números. (2 de octubre)
Muestra que si $(n-1)!\equiv-1\pmod n$ entonces $n$ es primo.
yo lo que yebo hasta ahora es esto : si $(n-1)!\equiv -1(mod n)$ entonces $(n-1)!\equiv n-1(mod n)$ entonces $(n-2)!\equiv 1(mod n)$ osea que ninguno de los factores desde $n-2$ hasta 2 no divide a n entonces $n$ es primo (el unico caso ene el que $n-1/n$ es en el caso $n=2$ pero dos es primo )lo unico que me falta es demostrar que si n es primo entonces se cumple la congruencia
Me parece que no queda claro todavia el problema, Martin. Solo te pido demostrar que si la congruencia se cumple, entonces debe ser primo. No es necesario mostrar el reciproco aun cuando este es verdadero.
En cuanto a tu solucion, decir que ninguno de los los factores desde hasta no dividen a por medio de multiples analogias no es correcto, aparte de que la afirmacion tampoco lo es. Talvez no comprendi tu argumento. Me gustaria que lo detallaras, por favor.
Nos fijamos en que si n no fuera primo, entonces en (n-1)! habría almenos un factor k de n diferente de 1 y -1, y (n-1)! sería congruente a un múltiplo de k mod n. CONTRADICCIÓN QED
Para $n$ no primo, tenemos que: $\exists p:pq=n, 1\textless{p}\leq{q}\textless{n}$ Por lo que es facil ver que: $p|(n-1)!$ Se tiene que: $(n-1)!\equiv{-1}\pmod{n}\Rightarrow p|(n-1)!+1$ $p|(n-1)! , p|(n-1)!+1 \Rightarrow p|1 \Rightarrow p=1$ Lo cual es una contradicción pues $1\textless{p}$ De aquí que $n$ debe ser primo Q.E.D.
Supongamos que n no es primo, entonces hay un divisor k de n distinto de 1, y (n-1)! es múltiplo de k. Vemos las congruencias de los múltiplos de k mod n: $xk\equiv k,2k,3k,...,n-k,n \pmod{n}$ Cuando llega a 0 se van a ciclar y como k es distinto de 1 ningún múltiplo de k va a ser congruente a n-1, entonces como (n-1)! es múltiplo de k no puede ser congruente a -1 mod n, que es una contradicción, entonces n es primo.
supongo que $n$ no es primo entonces existe un numero $x$ tal que divide a $n$, ya que $x$ es un numero diferente a $1$, $-1$ ,$n$ , $-n$ , y es menor que $n$ podemos decir que se encuentra en algun factor de $(n-1)!$ por lo tanto $x$ divide a $(n-1)!$ entonces $x$ divide a $n$ y a $(n-1)!$ sabemos que $n$ divide a $(n-1)!+1$ por lo tanto $y$ a divide a $(n-1)!+1$ pero $(n-1)!+1$ y $(n-1)!$ son primos relativos por lo cual y no puede dividir a los dos contradiccion
tienes que si $n-1!\equiv-1(modn)$ entonces $n-2!\equiv1(modn)$ entonces ningun numero de $n-2$ hasta $2$ divide a n entonces como $n-1$ es primo relativo con $n$por ser consecutivos ningun numero de $2$ hasta $n-1$ entonces $n$ es primo $:)$
veo que si n no fuera primo entonces existe un factor k con 1<k<n tal que k divide a n. Entonces k divide a (n-1)! pero como (n-1)! es congruente a -1 modulo n. Entonces k divide a (n-1)! y a (n-1)!+1 entonces k debe dividir a 1, pero eso implica que k=1 lo cual es una contradiccion. Entonces n es primo.
Supongamos que $n$ no es primo, entonces existe un factor $p$ que divide a $n$, entonces $p|(n-1)!$, como $p|(n-1)!+1\equiv 0 mod n$ entonces $p|1$ $\therefore$ $p=1$. Llegamos a una contradicción ya que $p>1$ por lo tanto $n$ es primo
Suponemos que $n$ no es primo, entonces existe un factor $k$ que divide a $n$ , tal que $1<k<n$ . $\Rightarrow k \mid (n-1)!$ Tenemos que $(n-1)! \equiv -1 \pmod n$ $\Rightarrow n \mid (n-1)!+1$ $\Rightarrow k \mid (n-1)!+1$ Llegamos que $k \mid (n-1)!$ y $k \mid (n-1)!+1$ . Por lo tanto llegamos a una contradicción porque $(n-1)!$ y $(n-1)!+1$ son primos relativos. $\therefore n$ es primo.
Suponemos que $n$ no es primo. Entonces tendremos que $n=pk$, con $1<p\leq{q}<n-1<n$ Por lo tanto, $p$ y $k$ estaran en $(n-1)!$. Entonces $(n-1)!\equiv 0 (mod n)$ Entonces llegamos a una contradiccion. Por lo tanto, $n$ siempre sera primo para que cumpla.
yo lo que yebo hasta ahora es esto : si
ResponderBorrar$(n-1)!\equiv -1(mod n)$ entonces $(n-1)!\equiv n-1(mod n)$ entonces $(n-2)!\equiv 1(mod n)$ osea que ninguno de los factores desde $n-2$ hasta 2 no divide a n entonces $n$ es primo (el unico caso ene el que $n-1/n$ es en el caso $n=2$ pero dos es primo )lo unico que me falta es demostrar que si n es primo entonces se cumple la congruencia
Este comentario ha sido eliminado por el autor.
BorrarMe parece que no queda claro todavia el problema, Martin. Solo te pido demostrar que si la congruencia se cumple, entonces debe ser primo. No es necesario mostrar el reciproco aun cuando este es verdadero.
BorrarEn cuanto a tu solucion, decir que ninguno de los los factores desde hasta no dividen a por medio de multiples analogias no es correcto, aparte de que la afirmacion tampoco lo es. Talvez no comprendi tu argumento. Me gustaria que lo detallaras, por favor.
Nos fijamos en que si n no fuera primo, entonces en (n-1)! habría almenos un factor k de n diferente de 1 y -1, y (n-1)! sería congruente a un múltiplo de k mod n. CONTRADICCIÓN QED
ResponderBorrarcomo garantizas que ese multiplo de k, multiplicado por todo lo demas no te da 1 o -1?
BorrarPara $n$ no primo, tenemos que:
ResponderBorrar$\exists p:pq=n, 1\textless{p}\leq{q}\textless{n}$
Por lo que es facil ver que:
$p|(n-1)!$
Se tiene que:
$(n-1)!\equiv{-1}\pmod{n}\Rightarrow p|(n-1)!+1$
$p|(n-1)! , p|(n-1)!+1 \Rightarrow p|1 \Rightarrow p=1$
Lo cual es una contradicción pues $1\textless{p}$
De aquí que $n$ debe ser primo Q.E.D.
:)
BorrarMuy bien!
Supongamos que n no es primo, entonces hay un divisor k de n distinto de 1, y (n-1)! es múltiplo de k. Vemos las congruencias de los múltiplos de k mod n: $xk\equiv k,2k,3k,...,n-k,n \pmod{n}$ Cuando llega a 0 se van a ciclar y como k es distinto de 1 ningún múltiplo de k va a ser congruente a n-1, entonces como (n-1)! es múltiplo de k no puede ser congruente a -1 mod n, que es una contradicción, entonces n es primo.
ResponderBorrarsupongo que $n$ no es primo entonces existe un numero $x$ tal que divide a $n$, ya que $x$ es un numero diferente a $1$, $-1$ ,$n$ ,
ResponderBorrar$-n$ , y es menor que $n$ podemos decir que se encuentra en algun factor de $(n-1)!$ por lo tanto $x$ divide a $(n-1)!$ entonces $x$ divide a $n$ y a $(n-1)!$ sabemos que $n$ divide a $(n-1)!+1$ por lo tanto $y$ a divide a $(n-1)!+1$ pero $(n-1)!+1$ y $(n-1)!$ son primos relativos por lo cual y no puede dividir a los dos contradiccion
por lo tanto no puede dividir a los dos lo cual es una contradiccion
Borrartienes que si $n-1!\equiv-1(modn)$ entonces $n-2!\equiv1(modn)$ entonces ningun numero de $n-2$ hasta $2$ divide a n entonces como $n-1$ es primo relativo con $n$por ser consecutivos ningun numero de $2$ hasta $n-1$ entonces $n$ es primo $:)$
ResponderBorrarCómo es que sabes que ningu número desde $2$ hasta $n-2$ divide a $n$?
Borrarhttp://s739.photobucket.com/albums/xx34/leo0_9506/Ommch/?action=view¤t=CAM001371.jpg
ResponderBorrar:)
Borrar(por ahí tienes una declaración que no necesariamente es cierta, pero para este problema, no es útil, y no la usas).
http://www.facebook.com/photo.php?fbid=4705422677769&set=a.4586100454788.189149.1360331970&type=1&theater
ResponderBorrar:)
BorrarY de hecho el teorema de Wilson es una proposición "si y sólo si", es decir, este problema es el recíproco (o la "vuelva") de este teorema.
veo que si n no fuera primo entonces existe un factor k con 1<k<n tal que k divide a n. Entonces k divide a (n-1)! pero como (n-1)! es congruente a -1 modulo n. Entonces k divide a (n-1)! y a (n-1)!+1 entonces k debe dividir a 1, pero eso implica que k=1 lo cual es una contradiccion. Entonces n es primo.
ResponderBorrarSupongamos que $n$ no es primo, entonces existe un factor $p$ que divide a $n$, entonces $p|(n-1)!$, como $p|(n-1)!+1\equiv 0 mod n$ entonces $p|1$ $\therefore$ $p=1$. Llegamos a una contradicción ya que $p>1$ por lo tanto $n$ es primo
ResponderBorrar:)
Borrar(te faltó acotar $p$ para que finalmente puedas llegar correctamente a la contradicción, pero así se entiende)
Suponemos que $n$ no es primo, entonces existe un factor $k$ que divide a $n$ , tal que $1<k<n$ .
ResponderBorrar$\Rightarrow k \mid (n-1)!$
Tenemos que $(n-1)! \equiv -1 \pmod n$
$\Rightarrow n \mid (n-1)!+1$
$\Rightarrow k \mid (n-1)!+1$
Llegamos que $k \mid (n-1)!$ y $k \mid (n-1)!+1$ .
Por lo tanto llegamos a una contradicción porque $(n-1)!$ y $(n-1)!+1$ son primos relativos.
$\therefore n$ es primo.
La contradiccion no esta en que sean primos relativos, sino que k debe ser precisamente 1, pero eso no es posible porque k la tomaste entre 1 y n.
BorrarA fin de cuentas tu respuesta es correcta :)
Suponemos que $n$ no es primo. Entonces tendremos que $n=pk$, con $1<p\leq{q}<n-1<n$
ResponderBorrarPor lo tanto, $p$ y $k$ estaran en $(n-1)!$. Entonces $(n-1)!\equiv 0 (mod n)$
Entonces llegamos a una contradiccion. Por lo tanto, $n$ siempre sera primo para que cumpla.
http://www.facebook.com/photo.php?fbid=398849296852537&set=a.384382948299172.87730.100001824112299&type=1&theate
ResponderBorrarNo veo cómo es que a partir de decir que $(n-2)!\equiv 1 \mod n$ concluyes que $n$ deberá ser primo. Podrías ser más fino en tu argumento?
Borrar