Wilson ' s teorema: (n-1)! es congruente con -1 (mod n) implica que n es primo.

Question

He investigado Wilson del teorema varias veces a lo largo de intercambio de la pila. Sólo quisiera probar una dirección. Esta parece ser una buena explicación: Demostrar que $(n-1)! \equiv -1 \pmod{n}$ fib $n$ es el prime

Sin embargo, en su explicación, el autor afirma que el $k|(n-1)!$ implica que el $k$ es congruente a $1$(mod $n$). No veo su salto en la lógica. Estoy en busca de una explicación o una referencia a un teorema si es posible. Cualquier ayuda es apreciada. Gracias

Answer 1

Esto no es cierto en general. Por ejemplo, no es congruente a $2 | (3-1)! = 2$ $2$ $1 \pmod 3$. Lo que el autor de la pregunta que se hace referencia dice que de las condiciones del teorema de Wilson, $k | (n-1)!$y $k$ es congruente a $1 \pmod n$, no que $k | (n-1)!$ implica es congruente a $k$ $1 \pmod n$.

Answer 2

No estoy seguro de cómo deriva la respuesta en el post enlazado %#% $ #%

En cambio, como una forma alternativa para completar la prueba. Como en la respuesta vinculada, asumimos que tenemos un entero $$ k \equiv 1 \pmod n $ tal que $k$ y $k<n as="" desde="" el="" n="" que="" sabemos="" y="">Desde $$ (n-1)! \equiv -1 \pmod k$, tenemos $k

Esto nos da %#% $ #% y tan $n>1$ como afirmó en la respuesta vinculada.

</n>

Answer 3

Como se mencionó anteriormente, la implicación como interpretación es incorrecta. $k\mid (n-1)!$ no implica que $k\equiv 1\pmod{n}$. Tomar cualquier contraejemplo a usted, como $k=3,n=5$.

Aquí espero a repasar algunos de los detalles de esa sección de la prueba en el intento de aclarar algunos de los puntos.

Supongamos que $(n-1)!\equiv -1\pmod{n}$

Se argumenta que las $n$ debe ser un primo. Para lograr esto, supongamos que al contrario que $n$ es en el hecho de compuesto. En este caso, $n=km$ algunos $k,m\in\mathbb{N}\setminus\{1\}$ lo que implica que $k<n$.

En este caso, $k$ a continuación, debe ser igual a uno de $\{2,3,4,\dots,n-2,n-1\}$. Esto implica que $k\mid (n-1)!$ desde $(n-1)!=\prod\limits_{i=1}^{n-1} i = k\prod\limits_{i=1~~~i\neq k}^{n-1} i$.

Sin embargo, desde la $(n-1)!\equiv -1\pmod{n}$$k\mid n$$k\mid (n-1)!$, todas estas cosas juntas implican que $k\equiv 1\pmod{n}$

Por qué? Desde $k\mid n$$k\mid (n-1)!$, usted tiene que $k\mid \gcd((n-1)!,n)$, pero desde $(n-1)!\equiv -1\pmod{n}$ que implica que $(n-1)!$ es coprime a $n$ (ya que esto implica que hay algún múltiplo de $n$ que es exactamente una distancia de $(n-1)!$). Por lo tanto,$\gcd((n-1)!,n)=1$$k\mid 1$. Esta es, sin embargo, una contradicción ya que nos dijo que $k\in\mathbb{N}\setminus \{1\}$.