Demuestre que es primo

Question

Supongamos $n = 2^{m}k +1 $ donde m es un entero y k es un entero positivo impar menor que $2^m$ . Supongamos que existe un entero $a$ tal que $a^{\frac{1}{2}(n-1)}\equiv -1\mod n$. Demostrar que $n$ debe ser un primo.

Me ha sorprendido sobre esta cuestión durante un tiempo. Hay una sugerencia adicional:

Demuestra en primer lugar que si $p$ es cualquier divisor primo de $n$ $ord_p(a)$ debe ser un divisor de a $n-1=2^mk$ y no es un divisor de a $\frac{1}{2}(n-1) = 2^{m-1}k$, y el uso de Fermat Poco Teorema deducir que $p\equiv1\mod2^m$.

Ni siquiera estoy seguro de cómo hacer la primera parte de la pista. Tengo que desde $a^n\mod p$ serán periódicos, $ord_p(a)|n$. Pero luego no se que implican $ord_p(a)|(2^mk+1) \implies2^mk+1\equiv0\mod ord_p(a)$? Pensé que estábamos tratando de mostrar a $2^mk\equiv0\mod ord_p(a)$.

Cualquier ayuda en cualquier parte de esta pregunta o sugerencia, sería muy apreciado!

Answer 1

Si $p$ es un divisor primo de $n$ vamos $\text{ord}_p(a)=x$...... A continuación, $a^{(n-1)/2}\equiv -1 \pmod n$ implica $a^{(n-1)/2 } \equiv -1 \pmod p$, lo que implica $a^{(n-1)/2} \not \equiv 1 \pmod p$ (debido a $p$ debe ser impar) lo que implica $x \not | (n-1)/2.$..... Pero $a^{n-1} \equiv 1 \pmod n$ implica $x|(n-1)=2^m k$ $x=2^b c$ donde $b \le m$ $c$ es impar (debido a $k$ es impar) y $c|k.$.... Por lo $y=(n-1)/x=2^{m-b}(k/c)$ es un número entero, sino $y/2$ no lo es.Y debido a que $k/c$ es un entero impar, esto requiere que el $b=m.$.... Por lo tanto $2^m c=x=\text{ord}_p(a)|(p-1)$, lo que implica $ p=2^m j+1$ para algún entero positivo $j.$..... Ahora si $n$ no es primo, a continuación, $ n/p$ es divisible por un primo $p^*$ pero entonces, aplicando el argumento anterior para $ p^*$ tenemos$ p^*=2^m j^*+1$ por entero positivo $j^*$...... Pero $k<2^m$ así que si $n$ no es primo, a continuación, $4^m+1>n\ge p p^*>4^m j j^*+1 \ge 4^m+1$ lo cual es absurdo. Usted escribió "$\text{ord_p(a)}|n$ " (después de la sugerencia),que es un error.