Mostrar que hay exactamente dos valores en $\{0, 1, ..., N - 1\}$ satisfacción $x^{2} \equiv a \pmod{N}$.

Question

Fijar un entero positivo $N > 1$. Decimos que $a$ es un residuo cuadrático módulo $N$ si existe $x$ tal que $a \equiv x^{2} \pmod{N}$.

Deje $N$ ser impar el primer y $a$ ser un no-cero residuo cuadrático módulo $N$. Mostrar que hay exactamente dos valores en $\{0, 1, ..., N - 1\}$ satisfacción $x^{2} \equiv a \pmod{N}$.

Esto significa que para demostrar que hay exactamente dos valores de $x$ que satisfacer $x^{2} \equiv a \pmod{N}$.

Creo que debería probar que existen en la mayoría de los dos valores y, al menos, dos valores que satisfacen las restricciones anteriores.

Sé que debido a $a$ es un residuo cuadrático módulo $N$, $a \equiv x^{2} \pmod{N}$, y dados en el problema es $x^{2} = a \pmod{N}$.

Puedo combinar estas dos ecuaciones usando aritmética modular a $x^{2}a = x^{2}a \pmod{N}$ o $x^{2} + a = x^{2} + a \pmod{N}$.

No sé si esto está en el camino correcto o cómo continuar la prueba.

Esta es una tarea de la pregunta, así que me gustaría ser un agradecido por una sugerencia de algún tipo que me mueven en la dirección correcta.

Answer 1

Descripción detallada: vamos a utilizar el hecho de que cualquier número entero es congruente, precisamente, uno de $0,1,2, \dots, N-1$ modulo $N$.

Supongamos que $b^2\equiv a \pmod{p}$. A continuación,$(-b)^2\equiv a\pmod{p}$. Si usted demuestra que $-b$ no es congruente a $b$ modulo $N$, han demostrado que existen al menos dos soluciones.

Supongamos que $b^2\equiv a\pmod{N}$$x^2\equiv a \pmod{N}$. A continuación, $N$ divide $x^2-b^2$, $N$ divide $(x-b)(x+b)$. Recordemos que si un primo divide a un producto, se divide al menos uno de los términos.

Answer 2

Algunas observaciones sólo para recordar algunos teoremas sobre congruencias cuando el módulo es el primer:

1 - Si $p$ es un número primo y $P(x)$ es un polinomio de grado $k$, $P(x) \equiv 0 \pmod{p}$ tiene más de $k$ número de soluciones.

2 - al $p$ es un número primo, $\mathbb{Z}/p\mathbb{Z}$ es una parte integral de dominio. Eso significa que cada vez que $a.b \equiv 0 \pmod{p}$ $a \equiv 0 \pmod{p}$ o $b \equiv 0 \pmod{p}$. Esto puede ser equivalentemente, dijo como $p \mid ab \implies p \mid a$ o $p \mid b$.

3 - Cada finito integral de dominio es un campo (Esto es más relacionados con el álgebra abstracta de primaria de la teoría de números).

4 - Observe que si $n\neq 1>0$ $2 \equiv 0 \pmod{n}$ si y sólo $n=2$. Como corrolary, $-1 \equiv 1 \pmod{n}$ si y sólo si $n=2$.

El resto está claro ahora como André Nicolas ha dicho:

Si $a$ es una ecuación cuadrática de los residuos, entonces, por definición, existe al menos un $x$ tal que $x^2 \equiv a \pmod{N}$. Pero también se $(-x)^2 \equiv a \pmod{N}$. Por lo tanto, si $x$ $-x$ son diferentes, hemos encontrado al menos dos soluciones, también a causa de la observación 1 sabemos que podemos tener en la mayoría de las 2 soluciones debido a que $P(x)=x^2-a$ es de degreee 2 y que demuestra que hay exactamente 2 soluciones.

Para mostrar que $x \not\equiv -x \pmod{N}$ asumir lo contrario. Si $x \equiv -x \pmod{N}$$2x \equiv 0 \pmod{N}$, pero $2 \not\equiv 0 \pmod{N}$ porque $N \neq 2$. Que implica $x \equiv 0 \pmod{N}$.Pero que las fuerzas de $a$ $0$ modulo $N$ que es la contradicción.