$a \in \mathbb{Z}$ , $(a^{n-1}\equiv 1 (mod~n) $ y $\forall q|n-1$ , $q$ es primo, $a^q\not\equiv 1 (mod~n)$ entonces $ n$ es un número primo

Question

Considere un número entero $n \geq 2$ verificando: $$ \exists a \in \mathbb{Z}, (a^{n-1} \equiv 1 (\textrm{mod}\ n) \text{ and }\forall q|n-1, q\text { is prime numbre }, a^q\not\equiv 1 (\textrm{mod}\ n).$$ Demuestra que $ n$ es un número primo.

Dejemos que $m$ sea el orden de $\bar{a}$ en el grupo de invertibles de $\mathbb{Z}/n\mathbb{Z}$ . Demostraremos que $m = n-1$ . Supongamos que $m < n-1$ . Como $a^{n-1} \equiv 1 (\textrm{mod}\ n)$ , $m | n-1$ y por tanto existe un número primo $q$ dividiendo $n-1$ tal que $m | \frac{n-1}{q}$ . Esto implica que $a^{\frac{n-1}{q}} \equiv 1 (\textrm{mod}\ n)$ . Según esta prueba. ¿Puedo concluir una contradicción con los supuestos?

Answer 1

Un contraejemplo

Dejemos que $n=65$ , entonces el único valor de $q$ es $2$ .

Dejemos que $a=8$ entonces $8^2\ne 1$ (mod $65$ ) pero $8^{64}= 1$ (mod $65$ ).

Answer 2

Esto es incorrecto tal y como se indica, véase la respuesta de S. Dolan.

Sin embargo, podemos corregir esto y convertirlo en algo llamado criterio de Pocklington:

Si $\exists a\in\mathbb{Z}$ tal que $a^{n-1}\equiv 1 \mod n$ y $\forall q|n-1,$ $q$ de primera, $a^{\frac{n-1}{q}}\not\equiv 1\mod n$ entonces $n$ es primo.

Obsérvese que el poder de $a$ es $\frac{n-1}{q}$ no $q$ .

De hecho, esto es bicondicional. Daría una prueba aquí, pero hay varias fuentes en línea.