$p=2^n+1$ . Demuestran que cada módulo cuadrático de no residuo $p$ es un módulo de raíz primitiva $p$

Question

Este es otro de los problemas de la teoría de los números con los que he estado luchando últimamente (¡esperemos que no esté publicando demasiadas preguntas a la vez!).

Deje que $n$ ser un entero positivo y dejar $p=2^n+1$ ser un número primo. Demuestra que cada módulo cuadrático no residual $p$ es una raíz primitiva modulo $p$ .

Supongamos que $a$ es un no-residuo cuadrático y $r$ un muódulo de raíz primitiva $p$ . Entonces no existe $x$ de tal manera que $x^2 \equiv a \mod p$ . Debemos determinar el orden de $a$ . Sabemos que $a$ debe ser congruente con algún poder de $r$ digamos $m$ ya que $\{r^1,r^2, \ldots ,r^{2^n}\}$ es un módulo de sistema de residuos reducido $p$ . Supongamos que $ \mathrm {ord}_p a=b$ . Luego $a^b \equiv r^{mb} \equiv 1 \mod p$ . Debemos mostrar que $b=2^n$ desde $ \phi (p)=2n$ . Pero $r$ es una raíz primitiva y por lo tanto $mb \equiv 0 \mod {2^n}$ (o $ \equiv 2^n \mod {2^n}$ ). Por lo tanto $mb = 2^n k$ . ¿Cómo puedo terminarlo?

Answer 1

Utilizaremos resultados estándar con los que usted pueda estar familiarizado. Hay $2^{n-1}$ los no residuos cuadráticos de $p$ .

Hay $ \varphi ( \varphi (p))$ raíces primitivas de $p$ . Así que hay $2^{n-1}$ raíces primitivas de $p$ .

De ello se deduce que cada no-residuo cuadrático es una raíz primitiva.

Answer 2

Si conoces los fundamentos de los grupos cíclicos y sus subgrupos, entonces se sugiere el siguiente enfoque.

El grupo $ \Bbb {Z}_p^*$ es cíclico de orden $p-1=2^n$ . Si $a$ es un elemento de orden $2^n$ entonces es primitivo. OTOH si el orden de $a$ es un factor de $2^{n-1}$ entonces es un cuadrado, porque los cuadrados forman el único subgrupo de orden $2^{n-1}$ . Con el mismo argumento un squre no puede ser primitivo.

Answer 3

Un poco diferente: Con $r$ una raíz primitiva, podemos escribir $a \equiv r^m$ para algunos $m$ . Si $a$ es un no-residuo cuadrático, claramente $m$ debe ser impar. Entonces $ \gcd (m,2^n)=1$ y existen $u,v \in\mathbb Z$ con $um+v2^n=1$ . Thius implica $a^u=r^{um+v2^n} \equiv r$ y por lo tanto que $a$ es primitivo.