utilizando el lema de Euclides en la prueba mod.

Question

a) Utiliza el lema de Euclides para demostrar que para cada primo impar $p$ y cada entero $a$ , si $a \not\equiv 0 \pmod p$ entonces $$x^2 \equiv a \pmod p$$ tiene $0$ o $2$ soluciones modulo $p$ .

b) Generalice esto de la siguiente manera:

Dejemos que $m = p_1\cdots p_r$ con distintos primos Impares $p_1,\dots, p_r$ y que $a$ sea un número entero con $\gcd(a, m) = 1$ . Demostrar que $$x^2 a \pmod m$$ tiene $0$ o $2^r$ soluciones modulo $m$ .

Mi intento de parte a es el siguiente: supongamos que $$x^2 a \pmod p$$ $$y^2 a \pmod p$$ Entonces $$x^2 y^2 \pmod p$$ $$x^2 - y^2 0 \pmod p$$ $$(x+y)(x-y) 0 \pmod p$$

Así que ahora usando el lema de Euclides $p \mid (x+y)$ o $p\mid(x-y)$ Por lo tanto $y x \pmod p$ o $y -x \pmod p$

Esto significaría que las dos soluciones serían $x$ y $-x$ pero no estoy seguro de cómo demostrar que debe haber exactamente 2 o exactamente 0 soluciones. ¿Es suficiente decir que si $x^2 a \pmod p$ entonces $(-x^2) a \pmod p$ ?

¿Es también cierto y desde $x \neq-x$ ¿entonces debe haber dos soluciones? Eso tampoco cubre el caso de 0 soluciones.

Answer 1

Dejemos que $m=p_1...p_r$ y la ecuación $x^2\equiv a \pmod m$ con $\gcd(a,m)=1$

Observe que $0$ está dada por el hecho de que $a\not\equiv (\pm a')^2\pmod {m}$ ( $a$ no es un residuo cuadrático $\pmod m$ si lo prefiere).

Para cada $i\in \{1,...,r\}$ tenemos $p_i \mid (x-a')$ o $p_i \mid (x+a')$ (es el lema de Euclides).

Para el primer caso queremos demostrar que si cada $i\in \{1,...,r\},\ p_i \mid (x+a')$ entonces el producto divide también $(x+a')$ .

$(p_i)_{i\in\{1,...,r\}}$ son coprimas entre sí. Utilizando una contradicción y el lema de Euclides se puede deducir que $\gcd(p_2...p_r=P_1,...,p_1...p_{r-1}=P_r)=1$ . Por la identidad generalizada de Bachet Bezout se tiene la existencia de $u_1,...,u_r\in \mathbb{Z}$ tal que : $u_1P_1+...+u_rP_r=1$ . multiplicando esta identidad por $(x+a')$ se obtiene directamente el hecho de que el producto divide $(x+a')$ .

Por lo que se obtiene $(x+a')\equiv 0 \pmod m$ y el otro caso es similar. Pero te da $2$ soluciones. Acabamos de hacer los dos casos principales.

Y si consideramos dos sistemas de CRT (el de $a'$ y el otro para $-a'$ ), para cada uno obtenemos una solución única $\pmod m$ por lo que finalmente da las dos primeras soluciones.

Este es el segundo caso: podemos considerar que $p_k\mid(x+a')$ y $P_k=\frac{1}{p_k}\prod\limits_{i=1}^r p_i\mid (x-a')$ con $\gcd(p_k,P_k)=1$ . Por el CRT tiene el sistema $x\equiv -a' \pmod {p_k}$ y $x\equiv a' \pmod{P_k}$ y tener un único $x \pmod m$ . Y todavía tienes la otra solución si inviertes $p_k$ y $P_k$ . Así que da dos soluciones.

Luego se continúa, por ejemplo $p_kp_l \mid (x+a')$ (con $l,r\in\{1,...,r\}$ ) y $P_k \mid (x-a')$ y $P_l \mid (x-a')$ . Está claro que tienes $p_k,p_l,P_k,P_l$ coprima por pares (si quieres verlo puedes usar el lema de Euclides y la contradicción). Además el hecho de que $\gcd(p_k,p_l)=1=\gcd(P_k,P_l)$ por una consecuencia de la identidad Bachet-Bézout $p_k\mid (x+a')$ y $p_l \mid (x+a')$ (lo mismo para $P_k,P_l$ ). Por la TRC se obtiene un sistema de cuatro ecuaciones que dicen que existe un único $x\pmod m$ . Invirtiendo todavía tienes 2 soluciones.

Puedes iterar el proceso y te da $2^r$ soluciones.

Answer 2

Su prueba para (a) es esencialmente correcta. Se puede acortar observando que $\mathbb{Z}/p\mathbb{Z}$ es un campo, por lo que una ecuación de grado dos tiene como máximo dos soluciones. Como $p$ es un primo impar, la existencia de una solución implica que también su negativo es una solución distinta. Por tanto, o no hay solución o hay dos.

Para (b), se puede utilizar el hecho de que el teorema del resto chino demuestra que el mapa $$\newcommand\Z[2][]{\mathbb{Z}/#2_{#1}\mathbb{Z}} \varphi\colon\Z{m}\to \Z[1]{p}\times\Z[2]{p}\times\dots\times\Z[r]{p} \qquad [x]_m\mapsto\bigl([x]_{p_1},[x]_{p_2},\dots,[x]_{p_r}\bigr) $$ es un anillo isomorfismo (donde $[x]_n=x+n\mathbb{Z}$ ).

Por lo tanto, la existencia de una solución para $[x^2]_m=[a]_m$ implica, mediante proyecciones la existencia de una solución para $[x^2]_{p_i}=[a]_{p_i}$ ( $i=1,2,\dots,r$ ).

Por el contrario, si $[x_i]_{p_i}$ es una solución para $[x^2]_{p_i}=[a]_{p_i}$ en $\Z[i]{p}$ , para $i=1,2,\dots,r$ entonces $$ \varphi^{-1}\bigl([x_1]_{p_1},[x_2]_{p_2},\dots,[x_r]_{p_r}\bigr) $$ es una solución para $[x^2]_m=[a]_m$ . Por lo tanto, o bien no hay solución (porque $[x^2]_{p_i}=[a]_{p_i}$ no tiene ninguna por lo menos un $i$ ), o tenemos $2^r$ soluciones, eligiendo una entre las dos de cada componente.