Dado que el $p, q \equiv 3 \pmod 4$ ni $y$ ni $-y$ tiene una raíz cuadrada mod $pq$, $y$ es invertible mod $pq$, ¿cómo puedo demostrar que $y$ es un cuadrado mod uno de $p, q$ $-y$ es un cuadrado mod de la otra?
Respuesta
¿Demasiados anuncios?
Aunque la pregunta no se indica explícitamente que el $p$ $q$ es de los primeros, la notación sugiere que son. También, el resultado reivindicado no necesita tener si $p$ $q$ no sean de primera. Por lo que asumimos que el $p$ $q$ sre prime.
El número de $y$ es invertible modulo $pq$, de modo que ni $p$ ni $q$ divide $y$. En primer lugar mostramos que exactamente uno de $y$ $-y$ es una ecuación cuadrática de residuos de mod $p$, y exactamente uno de $y$ $-y$ es un residuo cuadrático de $q$.
Para probar esto, se utiliza un símbolo de Legendre de cálculo. Tenemos $$(-y/p)=(-1/p)(y/p)=-(y/p).$$ (We have $(-1/p)=-1$ because $p\equiv 3\pmod{4}$.) The same argument works for $p$.
Se nos dice que ni $y$ ni $-y$ es un cuadrado modulo $pq$. Supongamos primero que $y$ es un cuadrado modulo $p$. A continuación, $y$ no puede ser un cuadrado modulo $q$, otra cosa $y$ sería un cuadrado modulo ambos $p$$q$, y por lo tanto (Teorema del Resto Chino) modulo $pq$.
Por lo tanto si $y$ es un cuadrado modulo $p$, $-y$ es un cuadrado modulo $q$.
Del mismo modo, si $y$ no es un cuadrado modulo $p$, $-y$ es un cuadrado modulo $p$. Si $-y$ fueron una plaza modulo $q$, $-y$ sería un cuadrado modulo $pq$, contradiciendo el hecho de que no lo es. Por lo $y$ es un cuadrado modulo $q$. Esto completa la prueba.
