Pregunta sobre prueba de test de primalidad de Lucas

Question

Lucas primalidad test supongo que $n > 1$ y $a$ son números enteros con $a^{n-1} \equiv 1 \mod n$ y $a^{(n-1)/p} \not\equiv 1$ para todos los primos $p \mid n-1.$ % entonces $n$es primo.

De la prueba. Supongamos que es de la orden de $a \in (\mathbb{Z} / n \mathbb{Z})^{\ast}$ $k.$ $a^{n-1} \equiv 1\mod n$ implica $k \mid n-1$ y $a^{(n-1)/p} \not\equiv 1$ implica que el $k$ no es un divisor apropiado de $n-1 \Rightarrow k = n-1$ y $|(\mathbb{Z} / n \mathbb{Z})^{\ast}| \geqslant n-1 \Rightarrow n$ prime. $\Box$

Entiendo la prueba excepto este paso: "$a^{(n-1)/p} \not\equiv 1$ implica que el $k$ no es un divisor apropiado de $n-1.$" ¿por qué ocurre esto?

Answer 1

La prueba se indica a menudo en una manera que ofusca la esencia de la materia. $\,a^{n-1}\equiv 1,\,$ La orden $\,d\,$ $\,a\,$ es un divisor de $\,n!-!1\,$ por lo tanto $\,d\neq n!-!1\,$iff $\,d\,$ es un divisor apropiado de $\,n!-!1.\,$ de factorización única, estos divisores apropiados se presentan mediante la eliminación de al menos un primer $\,p\,$ de la factorización de $\,n.\,$ pues $\ d\mid n!-!1$ correctamente $\iff$ $d\mid (n!-!1)/p,\,$ % primer $\,p\mid n$.

Nota $\ $ comparar a la teoría de conjuntos analógica $\ S\subsetneq P!\iff! S\subseteq P\backslash{p}\,$ $\,p\in P$

Answer 2

Supongo que por el contrario que $k$ es un divisor apropiado de $n-1$. Entonces $kd=n-1$ $d\ge 2$. Sea $p$ un primer divisor de $d$. Entonces divide a $k$ $\frac{n-1}{p}$. Ya que $a$ $k$ de la orden, tenemos que $a^{(n-1)/p}\equiv 1\pmod{n}$, contradiciendo el hecho de que $a^{(n-1)/p}\not\equiv 1\pmod{n}$.