Lema de Euclides, mod, prueba gcd

Question

(a) Que $p$ sea un primo impar y $a$ sea un número entero con $\gcd(a, p) = 1$ . Demostrar que $x^2 - a \equiv 0 \mod p$ tiene $0$ o $2$ soluciones modulo $p$

b) Generaliza la parte a) de la siguiente manera: Sea $m = p_{1} · · · p_{r}$ con distintos primos Impares $p_{1} · · · p_{r}$ y que $a$ sea un número entero con gcd(a, m) = 1. Demuestre que $x_{2} a \bmod m$ tiene $0$ o $2^r$ soluciones módulo m.

Respuesta: (a) Si $p=2$ no hay solución. Si $p>2$ y $\gcd(a,p)=1$ y si existe una solución, también existirá una segunda solución porque $(-x)^2 \equiv x^2\bmod p$ y $-x\not\equiv x \bmod p$ .

$(-x)^2\equiv y^2\bmod p$ significa $x^2-y^2=(x-y)(x+y)\equiv0\bmod p$ . Por el lema de Euclides, esto implica $p|x-y$ o $p|x+y$ . Por lo tanto, o bien $y \equiv x\bmod p$ o $y \equiv -x\bmod p$ y no hay posibilidad de una tercera solución.

Esto demuestra que $x^2\equiv a\bmod p$ no tiene soluciones o tiene exactamente dos soluciones.

Sin embargo, no estoy seguro de cómo hacer la parte b.

Answer 1

Una pista:

Por el Teorema del resto chino : $$\mathbf Z/m\mathbf Z\simeq \mathbf Z/p_1\mathbf Z\times \dots\times \mathbf Z/p_r\mathbf Z\times,$$ así que $x^2\equiv a\mod m$ tiene una solución si y sólo si tiene dos módulos cada uno $p_i$ .