Símbolo de Legendre - ¿qué es la prueba que es un homomorfismo?

Question

Sé que una de las propiedades del símbolo de Legendre es que es un homomorphism. Sin embargo, no he sido capaz de encontrar una prueba de que este es el caso. Si alguien me podría dar o muéstrame a una exhaustiva prueba de ello, eso sería genial.

Me voy con la definición:

$\sigma(x) = 1$ al $ x=y^2$

$\sigma(x)= -1 $ lo contrario

donde $\sigma$ es un mapa de st $\sigma: {\mathbb{Z}_p}^{\times} \rightarrow (-1,1)$

---

EDIT: ¿Cómo podemos esbozar una prueba de que el símbolo es un homomorphism el uso que

si $(G, *)$ es un grupo finito y $H\subset G$ es un subgrupo, y tenemos una relación de equivalencia en $G: x \sim y$ fib $\exists h \in H$ st $y= x*h$, e $P$ es una relación de equivalencia: entonces sabemos $\# P = \# H$ $\# H$ divide $\# G$.

Básicamente, ¿cómo podemos demostrar, utilizando este hecho, que el conjunto de plazas en $\mathbb{Z}_p$ es un subgrupo de $\mathbb{Z}_p$?

Answer 1

Deje $p$ ser un fijo impar prime. A continuación, para $a$ $b$ relativamente primer a$p$, $(ab/p)=(a/p)(b/p)$ (el producto de dos residuos o no de los residuos es un residuo, el producto de un no y un residuo residuo es un no-residuo). Por lo tanto el símbolo de Legendre induce un homomorphism de la multiplicación de los subgrupos de $\mathbb{Z}_p$ a su multiplicativo subgrupo $\{1,-1\}$.

Comentario: boceto de una prueba de los hechos clave sobre los productos de los residuos y/o no residuos. Vamos a necesitar el hecho de que no se $(p-1)/2$ residuos, y por lo tanto $(p-1)/2$ sin residuos.

(a) Deje $f(x)$ ser el mapa que lleva a $x$$x^2$. Para cualquier $a\in \mathbb{Z}_p$, la ecuación de $f(x)=a$ tiene dos soluciones o ninguna solución. Para suponer que $b^2\equiv a \pmod{p}$. A continuación,$(-b)^2\equiv a \pmod{p}$, así que hay al menos dos soluciones. Pero si $c^2-b^2\equiv 0\pmod{p}$, $(c-b)(c+b)$ es divisible por $p$, y por lo tanto $c\equiv b\pmod{p}$ o $c\equiv -b\pmod{p}$, por lo que no hay más de $2$ soluciones.

Desde la asignación $f$ es de dos a uno, su rango de tamaño de $(p-1)/2$, lo $p$ $(p-1)/2$ QR.

(b) Deje $a$ ser un QR y deje $b$ ser un NR. Nos muestran que $ab$ es un NR. Supongamos que al contrario que $ab$ es un QR. Tenemos por supuesto que $a\equiv c^2\pmod{p}$ algunos $c$, $ab\equiv d^2\pmod{p}$ algunos $d$. Por lo tanto $c^2b\equiv d^2\pmod{p}$. Multiplicar dos veces por la inversa de a $c$ modulo $p$. Tenemos que $b\equiv (c^{-1}d)^2\pmod{p}$, contradiciendo el hecho de que $b$ es un NR.

La prueba de que un producto de QR es un código QR es aún más fácil.

(c) Para mostrar que un NR veces un NR es un QR, vamos a $b$ ser un NR. Entonces como $x$ rangos de la multiplicación de los subgrupos de $\mathbb{Z_p}$, por lo que no $bx$. Desde $b$ veces un código QR es un NR, y hay el mismo número de QR y NR, debemos tener la $bx$ es un QR siempre $x$ es un NR.

Answer 2

Me pregunto si está permitido el uso de las raíces primitivas modulo de un primer $p$.
Supongamos que es así, y, a continuación, nos fijamos en la definición de un símbolo de Legendre, y luego dar una prueba de que es un homomorphism. Por lo tanto, fijar un primer $p$ primera.
Deje $x$ ser un número no divisible por $p$. Supongamos que ya tenemos a su disposición una raíz primitiva módulo $p$, que se denota por a $g$. Entonces es fácil ver que $g$ es un no residuo de $p$, y que todo entero es congruente a $g^n$ algunos $n$. Por otra parte, $x$ es un residuo si y sólo si $x\equiv g^{2k}$ algunos $k$. A continuación, el hecho de que el símbolo de Legendre es un homomorphism sigue las reglas que incluso+aun=, incluso+impar=impar, y que impar+impar=par.
Supongamos que no estamos frente a la existencia de una raíz primitiva módulo $p$. A continuación, se utiliza otro enfoque:
Deje $p$ ser un extraño prime. Definir un homomorphism de $\mathbb Z_p^*={1, \cdot\cdot\cdot,p-1}$ a sí mismo, elevando al cuadrado: enviamos $x$$x^2$. Su núcleo, es decir, {$x: x^2\equiv 1\pmod p$}, consta de dos números: $1$$p-1$. Su imagen es el conjunto de residuos modulo $p$, que es también un grupo de $\mathbb S_p$ bajo la multiplicación. Desde la multiplicación de números enteros es abelian, el grupo $\mathbb S_p$ es un subgrupo normal de $\mathbb Z_p^*$. Así podemos formar un cociente $\mathbb Z_p^*/\mathbb S_p$. Es de orden $2$, por lo tanto isomorfo con el grupo cíclico de orden $2$, {$1,-1$}. Y enviamos $x\in \mathbb Z_p^*$ a su imagen en $\mathbb Z_p^*/\mathbb S_p$: este es el símbolo de Legendre. Por esta definición, es evidente que el símbolo de Legendre es un homomorphism.
Me pregunto también si podemos hablar de la maravillosa interpretación debido a Zolotarev: no es nada, pero la teoría de permutaciones, sin embargo, es una magia de observación.

Answer 3

Siento que debo añadir aquí un resultado estándar de la teoría de grupo: un subconjunto de un grupo finito cerrado bajo la multiplicación es un subgrupo. Desde $(\Bbb Z_p)^{\times}$ es claramente finito, es suficiente para mostrar que un QR veces un código QR es un código QR, y el resto de los casos son innecesarios.

Tenga en cuenta que el mapa de $x \to x^2$ es una EN multiplicativo homomorphism de $(\Bbb Z_p)^{\times}$ para el conjunto de residuos cuadráticos (mod $p$) que ha kernel $\{1,p-1\}$. Esto muestra que el índice del subgrupo de residuos cuadráticos es $2$, lo que significa que no debe ser $\dfrac{p-1}{2}$ residuos cuadráticos (asumiendo $p$ es una extraña prime, esta fórmula se rompe por $p = 2$).

Desde NR es así que el "otro coset", las otras normas para los productos:

NR*NR NR*QR

siga las reglas de la coset multiplicación en $(\Bbb Z_p)^{\times}/QR$