¿Con qué rapidez podemos detectar si $\sqrt{(-1)}$ existe módulo de un primo $p$ ?

Question

¿Con qué rapidez podemos detectar si $\sqrt{(-1)}$ existe módulo de un primo $p$ ? En otras palabras, ¿con qué rapidez podemos determinar si un $n$ existe donde $n^2 \equiv -1 \bmod p$ ?

NOTA

Este $n$ es esencialmente la unidad imaginaria módulo $p$ .

Answer 1

Para $p>2$ de primera, $-1$ es un residuo cuadrático módulo $p$ si y sólo si $p \equiv 1 \bmod 4$ . Así podrá determinar si $-1$ es un residuo cuadrático módulo $p$ tan rápido como puedas encontrar el resto de $p$ al dividir por $4$ .

Answer 2

Si $p = 2$ entonces $-1$ es un cuadrado mod $p$ por lo que ahora podemos suponer que $p$ es impar. Supongamos que $n^2 \equiv -1 \bmod p$ para algunos $n \in \mathbb{N}$ . Entonces, utilizando esa $\mathbb{Z}/p\mathbb{Z}$ es un campo, $$ 1 \equiv n^{p-1} \equiv (n^2)^{\frac{p-1}{2}} \equiv (-1)^{\frac{p - 1}{2}} \bmod p $$ lo que implica que $\frac{p-1}{2}$ es uniforme, por lo tanto, que $p \equiv 1 \bmod 4$ . A la inversa, supongamos que $p \equiv 1 \bmod 4$ . Entonces $\frac{p-1}{2}$ es par. Usando eso $\mathbb{Z}/p\mathbb{Z}$ es un campo, elige un generador $x$ de $\mathbb{Z}/p\mathbb{Z}^\times$ . $x^{\frac{p-1}{2}}$ es una raíz de $T^2 - 1$ diferente de $1$ , de tal manera que $$ -1 \equiv x^{\frac{p-1}{2}} \equiv (x^{\frac{p-1}{4}})^2. $$ Hemos demostrado que $-1$ es un cuadrado mod $p$ si y sólo si $p \equiv 1 \bmod 4$ o $p = 2$ .

Esta observación puede generalizarse a $\mathbb{Z}/p^n\mathbb{Z}$ para un primer $p$ es decir $-1$ es un cuadrado mod $p^n$ si y sólo si $p \equiv 1 \bmod 4$ (o $p = 2$ Y $n = 1$ ). Utilizando el Teorema Chino del Resto entonces, se puede concluir fácilmente que $-1$ es un cuadrado módulo $n$ si y sólo si $n$ es divisible por $2$ como máximo una vez y todos los primos Impares $p$ dividiendo $n$ satisfacer $p \equiv 1 \bmod 4$ .

Answer 3

$\mathbb{Z}/p\mathbb{Z}$ es un campo, por lo que su grupo multiplicativo es cíclico. En particular, si $p$ es un primo impar y si $g$ es cualquier generador, entonces $-1 = g^{(p-1)/2}$ que es una raíz cuadrada si $(p-1)/2$ está en paz.

Si $p=2$ entonces $-1 = 1 = 1^2$ por lo que se sostiene de forma bastante trivial.

Answer 4

Hagamos algunos experimentos.

$p = 3$ No.

$p = 5$ Sí, $2^2 \equiv -1$ .

$p = 7$ No.

$p = 11$ No.

$p = 13$ Sí, $5^2 \equiv -1$ .

$p = 17$ Sí, $4^2 \equiv -1$ .

$p = 19$ No.

$p = 23$ No.

Parece que sólo los números primos que son congruentes con $1$ modulo $4$ tienen esta propiedad.