Prima divisores de $n-1$, $n$ es el primer

Question

¿Alguien me puede ayudar hacia fuera con esta pregunta número de teoría? Mi pregunta es la siguiente:

Si $n$ es un número entero positivo y un número entero $x$ existe tal que $x^{n-1}\equiv 1 \pmod n$ y $x^{\frac{n-1}{q}} \neq 1 \pmod n$ para todos los divisores primeros $q$ $n-1$, entonces el $n$ son primo.

Creo que tenemos que usar algún razonamiento $x$, pero no sé dónde empezar. ¡Gracias!

Answer 1

Sugerencia $\ \, $ Las condiciones implica que el orden de $\rm\:k\:$ $\rm\:x\:$ es un divisor de a$\rm\:n\!-\!1\:$, pero no una adecuada divisor, por lo tanto, $\rm\: k = n\!-\!1.\, $ Por Euler, $\rm\ k\, |\, \phi(n)\ $ $\rm\ n\!-\!1\: \le\: \phi(n).\, $ Esto implica que $\rm\:n\:$ es primo, ya que $\rm\, \phi(n) \le\ n\!-\!\color{#C00}{2}\ $ compuesto $\rm\:n,\:$ ya que ellos tienen, al menos, $\:\color{#C00}2\ $ menor naturales no coprime a $\rm\:n.$

Comentario $\ $ Esto es con frecuencia llamado el Lucas Prueba de Primalidad.