¿Si $ab \equiv r \pmod{p}$ y $x^2 \equiv a \pmod{p}$ y $y^2 \equiv b \pmod{p}$ para que condición del $r$?

Question

Para el caso especial $ab \equiv 1 \pmod{p}$, ya la tengo muy clara la explicación de Arturo Magidin y Quanta en este hilo Probar que si $ab \equiv 1 \pmod{p}$ $a$ es residuo cuadrático mod $p$, entonces también lo es $b$

Ahora si $ab \equiv r \pmod{p}$, ¿qué condición deben ser mantener en orden para que esto sea cierto, yo.e Si $a$ es residuo cuadrático módulo $p$, $b$ también es residuo cuadrático módulo $p$. Mi intento fue, hice un ejemplo concreto para observar el valor de $r$, dice $p = 7$. Los resultados son: 1, 4, 5 $$1^2 \equiv 1 \pmod{7}$$ $$2^2 \equiv 4 \pmod{7}$$ $$3^2 \equiv 2 \pmod{7}$$ $$4^2 \equiv 1 \pmod{7}$$ $$5^2 \equiv 4 \pmod{7}$$ $$6^2 \equiv 1 \pmod{7}$$

Por lo $r$ $1$, $2$, $4$, desde $4.4 \equiv 1 \pmod{7}$$4.2 \equiv 1 \pmod{7}$. A partir de estos resultados, vi que $r$ también fue residuo cuadrático módulo $p$. Otra idea que he probado es la adaptación de la prueba de la mención del hilo anterior: Si $ab \equiv r \pmod{p}$, luego $$aa^{-1}b \equiv ra^{-1} \pmod{p} \Leftrightarrow b \equiv ra^{-1} \pmod{p}$$ $$bb^{-1}a \equiv rb^{-1} \pmod{p} \Leftrightarrow a \equiv rb^{-1} \pmod{p}$$

Entonces traté de usar el hecho de que $x^2 \equiv a \pmod{p}$, e $a \equiv rb^{-1} \pmod{p}$ a venir con $x^2 \equiv rb^{-1} \pmod{p}$. Pero yo no podía encontrar una manera de expresar esto en términos de $y^2 \equiv b \pmod{p}$. Además, no sé si esta manipulación algebraica podría resolver la condición para $r$ o no. Alguna idea? Una sugerencia, sería muy apreciado.

Gracias

Answer 1

Los siguientes tres hechos relevantes.

• Si $a$ $b$ son plazas que a continuación, $r$ es un cuadrado.

• Si $a$ $b$ no son cuadrados, a continuación, $r$ es un cuadrado.

• Si uno de $a,b$ es un cuadrado y la otra no, a continuación, $r$ no es un cuadrado.

Es sencillo probar que el primero: Vamos a $a = x^2$, $b = y^2$ de modo que $r = ab = (xy)^2$.

En cuanto a los dos voy a dar un "hi-tech" de la prueba (Ver Martins comentario para una prueba directa).

Aritmética Modular $\mathbb{Z}/p\mathbb{Z}$ es un anillo, pero el grupo de unidades de $(\mathbb{Z}/p\mathbb{Z})^\times$ es un grupo: Es el multiplicativo parte del anillo. El único no-unidad de es $0$ así como un conjunto de es $\{1,2,\cdots,p-1\}$.

Este grupo es cíclica, es decir una muy fundamental y fuerte teorema, ver aquí alguna discusión sobre ella) y podemos usar esto para probar los teoremas: Vamos a $g$ generar el grupo, de modo que cada elemento es de la forma $g^k$ algunos $0 < k < p-1$,

• Primera nota de que $a$ es un cuadrado iff $a = g^{2k}$. (Fácil de probar).

Vamos $a = g^u$, $b = g^v$ por lo $r = ab = g^{u+v}$. Los tres hechos son una fácil deducción a partir de este. Usted puede probar ellos ahora, pero me gustaría definir algunos buenos notación.

Podemos introducir el símbolo de Legendre ahora: Definir un mapa de $\left(\tfrac{-}{p}\right)$ que se lleva a $g$$-1$, y la extendemos a todo el grupo: Es un grupo de homomorphism de las unidades del grupo de $\mathbb{Z}/p\mathbb{Z}$ a $\{1,-1\}$. Es $1$ exactamente cuando el número es un cuadrado y $0$ lo contrario.

Así que ahora tenemos:

• Si $a$ $b$ son plazas que a continuación, $r$ es un cuadrado porque $\left(\tfrac{r}{p}\right) = \left(\tfrac{ab}{p}\right) = \left(\tfrac{a}{p}\right)\left(\tfrac{b}{p}\right) = 1 \cdot 1 = 1$.

• Si $a$ $b$ no son cuadrados, a continuación, $r$ es un cuadrado porque $\left(\tfrac{r}{p}\right) = \left(\tfrac{ab}{p}\right) = \left(\tfrac{a}{p}\right)\left(\tfrac{b}{p}\right) = -1 \cdot -1 = 1$.

• Si uno de $a,b$ es un cuadrado y la otra no, a continuación, $r$ no es un cuadrado porque $\left(\tfrac{r}{p}\right) = \left(\tfrac{ab}{p}\right) = \left(\tfrac{a}{p}\right)\left(\tfrac{b}{p}\right) = 1 \cdot -1 = -1$.

Answer 2

Lo que se está observando, es simplemente la adición de tablas de $\rm\ \mathbb Z/2\ \cong G/G^2,\:\ G = \mathbb (Z/p)^{*}\:.\:$ Porque los cuadrados forman un subgrupo de índice $2$, se multiplican de la misma como la suma de mod $2\ $ (paridad de la suma). Más precisamente, con la notación: Plaza de la $\rm = S \to 0\in \mathbb Z/2\:,\ $ Rectangulares $\rm = N\to 1\in \mathbb Z/2\:,\: $ hemos

$$\rm S \:*\: S\:\ =\ \:S\:\ \ \iff\ \ \ 0 + 0\ \equiv\ 0 $$

$$\rm S \:* N\ =\ N\ \ \iff\ \ \ 0 + 1\ \equiv\ 1 $$

$$\rm N * N\ =\ S\ \ \iff\ \ \ 1 + 1\ \equiv\ 0 $$

Usted puede encontrar más ejemplos en mi post de hace un par de días, que describe varias formas de caracterización de subgrupos, incluyendo el complemento de vista de un subgrupo. Cuando usted está aprendiendo elementales de la teoría de números y teoría de grupos, con el fin de comprender mejor el resumen, estructuras algebraicas, es esencial para explorar muchos de los casos concretos de estas abstracciones. Como se puede ver en los muchos ejemplos en mi post vinculado, subgrupo leyes (y sus complementos) ya son conocidos de forma inconsciente en el familiar número de sistemas. El algebraicas abstracciones servir a "cosificar" este conocimiento intuitivo de una manera más formal estructurada. Esto es esencial para hacer frente a este tipo de estructura es cuando surge en mucho más complejos escenarios.

Answer 3

Estamos trabajando en el grupo multiplicativo $G=(\mathbb{Z}/p\mathbb{Z})^*$. Este grupo es cíclico con orden $p-1$, que es incluso para $p \neq 2$. Entonces $G^2$, que consiste en los cuadrados de los elementos en $G$, es un subgrupo del índice 2. El conjunto de nonsquares es sólo el coset de $G^2$ $G$.

Inmediatamente podemos concluir:

1. El producto de dos cuadrados es un cuadrado.
2. El producto de un cuadrado y un no de cuadrados es un no cuadrados.
3. El producto de dos nonsquares es un cuadrado.