Mostrando un número $n$ es primo si $(n-2)! \equiv 1 \pmod n$

Question

Necesito demostrar eso si $(n-2)! \equiv 1 \pmod n$ $n$ es primer.
Creo que si $n$ es compuesto, entonces vamos a tener cada factor de $n$ $(n-2)!$ y produciría que $(n-2)! \equiv 0 \pmod n$.
Sin embargo, no utilizo el hecho de que lo específicamente congruente a $1 \bmod n$, así que creo que me estoy poniendo mal algo fundamental. ¿Es correcta mi solución? ¿Por qué exigimos congruencia a $1 \bmod n$?

Answer 1

Su solución es correcta dejando de lado el pequeño detalle de 4!, que ya ha sido señalado en los comentarios. 4 es algo especial, siendo el primer número compuesto, y la plaza de la "extraña" prime. Así que no creo que este pequeño error es "fundamental".

Aún así, creo que es mejor usar el hecho de $1 \bmod n$, ya que garantiza $\gcd((n! - 2), n) = 1$. Al menos el primer factor de $n$ si $n$ sí no es primo, es menor o igual a $\sqrt n$, e $\sqrt n < (n - 2)$ todos los $n > 4$. Por lo tanto, si $n$ es compuesto, entonces $(n - 2)!$ es divisible por al menos el primer factor de $n$ $(n - 2)! \equiv 1 \bmod n$ imposible.

Sin embargo, otra manera que usted puede ir sobre esto es la siguiente: Si $n$ es aún compuesto y, a continuación, $n - 2$ es también y, por tanto, $(n - 2)! \equiv 2k \bmod n$ donde $k$ es algún número entero no negativo no nos importa mucho acerca de. Pero 1 no es ni siquiera, demostrando $n$ no es incluso un número compuesto. Si $n$ es impar y compuesto, es divisible por alguna extraña prime $p \leq \sqrt n$. Y desde $p \leq \sqrt n < (n - 2)$, se deduce que el $p \mid (n - 2)!$$(n - 2)! \equiv pk \bmod n$. Y $pk \neq 1$, demostrando $n$ no es un extraño número compuesto.

Y, sin embargo, otra forma es el uso del teorema de Wilson, pero entonces yo no sería más que la reformulación de una o dos de las otras respuestas.

Answer 2

Si $n=p^2$ donde $p>2$ es un número primo, $(n-2)!$ contiene $p$ $2p$ dentro de él, por lo que es $0$ modulo $p^2$. Si $n=2^2$,$(n-2)!\equiv 2$. En todos los demás casos es fácil ver que el composite $n=ab$ donde $a\ne b$, y, a continuación, $(n-2)!$ contiene $a$ $b$ $0$ modulo $n$. Si $p$ es primo, entonces $(-1)(n-2)!\equiv(n-1)!\equiv -1$ por Wilson del teorema y por lo $(n-2)!\equiv 1$.

Por lo general se utiliza el hecho de que $(n-2)!$ no $0$ o $2$, no es necesario saber que es exactamente $1$. Causa justa no puede ser cualquier cosa, excepto $0,1,2$.

Answer 3

Como $\mathbb{Z}_n$ es un unitario comutativo anillo, todos tenemos que demostrar es que cada elemento tiene inverso, por lo que sería un campo y entonces $n$ sería primer. Es fácil ver de la hipótesis de que para cualquier $k\leq n-2$ tenemos el inverso. A continuación, sólo tenga en cuenta que $-(n-2)!\mod n$ es el inverso del $(n-1)$, porque: $$-(n-1)(n-2)!=-(n-1)\dot{}1=1\mod n$ $

Answer 4

Deje $n = a*b; n > 4$ ni $b$ ni $a$$1$.

Primero: tanto en $b$ $a$ son de menos de $n-2$. Este debe ser claro cuando se considera si $b \ge n-2$$a = \frac nb \le \frac n{n-2} < \frac n{n- \frac 12 n} = 2$$a < 2$, lo que contradice nuestra hipótesis. (Nota: se necesita la $n > 4$ saber que $n- 2 > n- (\frac 12 n)$)

Si $a \ne b$$(n-2)! = \prod_{k \le n-2;k \in \mathbb N} k$$\frac {(n-2)!}{ab} = \prod_{k \le n-2;k \ne a; k\ne b;e \in \mathbb N}k \in \mathbb Z$$(n-2)! \equiv 0 \mod ab = n$.

Si $a = b$ $n = a*b$ es la única posible factorización, a continuación, $n = a^2$ $a$ es primo.

Pero como $n > 4$ tenemos $a > 2$, por lo que tenemos $a < 2a < a^2 - 2 < a^2$$\frac{(a^2 - 2)!}{a^2} = 2*\prod_{k\le a^2 -2; k \ne a; k \ne 2a k \in \mathbb N}k$.

Por lo $(n-2)! \equiv 0 \mod n$ si $n$ es compuesto.

Así que si $(n-2)! \not \equiv 0 \mod n$ $n > 4$ $n$ debe ser un primo.

Por supuesto, no hemos probado que $(p-2)! \ne 0 \mod p$ (a pesar de que es obvio), o que hay alguna $(p-2)! \equiv 1 \mod p$ (no tan obvio).