Ayuda sobre el residuo cuadrático

Question

¿Es resolver la congruencia $x^2 \equiv 1 (\mod n)$ equivalente a la resolución de $x \equiv 1(\ mod p)$ , $x \equiv -1 (\mod q)$ et $x \equiv -1(\ mod p)$ , $x \equiv 1 (\mod q)$ ? Aquí $n=pq$ donde $p,q$ son primos. No estoy considerando las soluciones triviales $1,-1$

Answer 1

Resolver para $x^2\equiv1 \mod n$ es lo mismo que resolver el sistema $x^2\equiv1 \mod p$ et $x^2\equiv1 \mod q$ por CRT. Así que para cada una de las 2 congruencias, el polinomio es de grado 2, por lo que cada una de las congruencias $x^2-1\equiv0 \mod p$ y $x^2-1\equiv0 \mod q$ tiene como máximo 2 raíces. Pero sabemos que $1,-1$ son raíces, por lo que son las únicas raíces. Esto significa que tenemos 2 soluciones para cada congruencia, y por CRT, podríamos generar 4 soluciones a la pregunta original. Es decir, esas 4 que has enumerado: $x \equiv 1(\ mod p)$ , $x \equiv -1 (\mod q)$ et $x \equiv -1(\ mod p)$ $x \equiv 1 (\mod q)$