Si $-a$ orden $(p-1)/2$ mod $p$, entonces, ¿por qué es $a$ una raíz primitiva?

Question

Estoy tratando de resolver un poco de ejercicio acerca de las raíces primitivas.

Considere la posibilidad de un primer $p$ de la forma $4q+3$. Demostrar que $a$ es una raíz primitiva módulo $p$ si y sólo si $-a$ orden $(p-1)/2$.

---

Yo era capaz de demostrar el avance implicación. Para probar la otra, estoy asumiendo $(-a)^{(p-1)/2}\equiv 1\pmod{p}$, y tratando de demostrar si $a^k\equiv 1\pmod{p}$, $p-1|k$ al ve $a$ es una raíz primitiva. Si $k$ es par, entonces $$a^k\equiv (-a)^k\equiv 1\pmod{p},$$ por lo $(p-1)/2|k$ o $p-1|2k$. Si $k$ es impar, luego me sale que $$ a^k\equiv -(-a)^k\equiv 1\pmod{p},$$ por lo $(-a)^{2k}\equiv 1\pmod{p}$. A continuación,$p-1|4k$. No estoy seguro de que me estoy dirigiendo en la dirección correcta. ¿Cómo puedo terminar este argumento, si es posible? Gracias.

Answer 1

La clave de este problema es que el $\frac{p-1}{2}$ es impar.

Por definición, $a$ es una raíz primitiva de mod $p$ fib el orden de $a$$p-1$.

El orden de $-a$$\frac{p-1}{2}=2q+1$, lo cual es extraño. El orden de $-1$ mod $p$$2$, lo que es aún. Supongamos que $$a^k=(-1)^k(-a)^k\equiv1\bmod p.$$ Si $k$ es incluso, a continuación,$a^{k}=(-a)^k\equiv 1\bmod p$, por lo tanto $k$ debe ser un múltiplo de $\frac{p-1}{2}$. Pero los múltiplos de $\frac{p-1}{2}$ son precisamente los múltiplos de $p-1$ sí, por lo $k$ debe ser un múltiplo de $p-1$.

Si $k$ es impar, entonces $(-a)^k\equiv -1\bmod p$. Pero si $x^r=y$ algunos $r\in\mathbb{N}$, luego el orden de $y$ divide el orden de $x$, por lo que el orden de $-1$ (2) divide el orden de $-a$,$\frac{p-1}{2}=2q+1$, un número impar; contradicción.

Por lo tanto, el orden de $a$ debe $p-1$.

Answer 2

Lo que estamos haciendo básicamente funciona... apenas asumen $k$ es el orden de $a$ (es decir, el menos $k$ tal que $a^k \equiv 1 \pmod p$). Como en el problema, escriba $p = 4q + 3$. Al $k$ es incluso, ha mostrado $2k$ es un múltiplo de a $4q + 2$, por lo que el $k$ es un múltiplo de a $2q + 1$. Desde $k$ es aún, debe tener $k = 4q + 2$ y listo.

Si $k$ es impar, ha mostrado $4k$ es un múltiplo de a $4q + 2$, por lo que el $2k$ es un múltiplo de a $2q + 1$. Desde $2q + 1$ es impar, $k$ es un múltiplo de a$2q + 1$. Desde $k$ es el orden de $a$ se divide $p - 1 = 4q + 2$. El único impar, múltiplo de $2q + 1$ haciendo que el es $k = 2q + 1$ sí. Pero en este caso $(-a)^k \equiv -a^k \equiv -1 \pmod p$ por virtud del hecho de que $-a$ es de orden $2q + 1$ aquí. Así una contradicción surge; esta situación no puede suceder y listo.

Answer 3

¿Conoces el teorema que dice que si las órdenes de $c$ $d$ son primos relativos, entonces el orden de $cd$ es el producto de las órdenes de $c$$d$?

El resultado anterior se tiene el cuidado de su problema. Para suponer que $-a$ orden $(p-1)/2$. Desde $p$ es de la forma $4k+3$, $(p-1)/2$ es impar.

También, $-1$ orden $2$. Por lo tanto el orden de $(-1)(-a)$$p-1$.

Apéndice: vamos a comprobar el resultado útil acerca de la orden de un producto. Supongamos que $h$ es el orden de $c$, e $k$ es el orden de $d$.

Deje $r$ ser el orden de $cd$. Claramente $$(cd)^{hk}=(c^h)^k (d^k)^h \equiv 1 \pmod{p}$$ y, por tanto,$r\mid hk$.

También, $$d^{rh}\equiv (c^h)^rd^{rh}\equiv (cd)^{rh}\equiv 1 \pmod{p}$$ y, por tanto,$k \mid rh$. Desde $(h,k)=1$, se deduce que el $k \mid r$. Del mismo modo, $h \mid r$, y por lo tanto $hk \mid r$, ya que el $(h,k)=1$.

Desde $r \mid hk$$k \mid r$, llegamos a la conclusión de que $r=hk$.

Añadido: sólo hicimos una dirección, desde el OP escribió que había hecho en la otra dirección. Pero para su integridad, y en respuesta a una petición, podemos escribir la parte de la OP no tenía ningún problema con el. Deje $p$ ser una de las primeras de la forma $4k+3$, y supongamos que $a$ es una raíz primitiva de $p$. Nos muestran que $-a$ orden $(p-1)/2$.

Debido a $a$ es una raíz primitiva, es una ecuación cuadrática no residuo. Pero $p$ forma $4k+3$, lo $-1$ es una ecuación cuadrática no residuo. Por lo $(-1)a$ es una ecuación cuadrática de residuos. De ello se deduce que el orden de $-a$ no puede ser $p-1$. Si el orden de $-a$$e$,$(-a)^{2e}=a^{2e}\equiv 1\pmod{p}$. Por lo tanto $p-1$ divide $2e$, y por lo tanto $e=(p-1)/2$.