He leído que la fórmula para el número de residuos cuadráticos $\pmod{pq}$ impar prepara $p$ y $q$ $\frac{(p-1)(q-1)}{4}$. Este es el caso, y si es así, ¿por qué es el caso y ¿cómo podría uno va sobre probándolo? Más en general, existe una fórmula para el número de residuos cuadráticos para cualquier módulo compuesto $m$ (y si es así, ¿por qué es así y cómo sería demostrar que la fórmula contiene)?
Respuestas
¿Demasiados anuncios?
Para cualquier $x$$1$$pq-1$, que es relativamente primer a $pq$, vamos a $f(x)$ el resto al $x^2$ se divide por $pq$. Nos muestran que la función $f$ $4$a-$1$. Que los rendimientos de su fórmula.
Para mostrar que $f$ $4$a-$1$, tenga en cuenta que $x^2\equiv y^2 \pmod{pq}$ si y sólo si $(zx)^2\equiv 1\pmod{pq}$ donde $z$ es el inverso multiplicativo de a $y$.
Ahora todo lo que tenemos que hacer es mostrar que la congruencia $w^2\equiv 1\pmod{pq}$ tiene exactamente $4$ soluciones. Tenga en cuenta que $w$ es una solución de la congruencia si y sólo si $w^2\equiv 1\pmod{p}$$w^2\equiv 1\pmod{q}$. Cada una de estas congruencias ha $2$ solutions, así que, usando el Teorema del Resto Chino nos encontramos con que la congruencia $w^2\equiv 1\pmod{q}$ $4$ soluciones.
Esencialmente el mismo argumento muestra que si $n=p_1^{a_1}\cdots p_k^{a_k}$, donde el $p_i$ son distintos de los números primos impares, hay $\frac{\varphi(n)}{2^k}$ números de $x$ en el intervalo de $[1,n-1]$, relativamente primer a $n$, que son cuadrados módulo $n$. Aquí $\varphi$ es el de Euler $\varphi$-función.
Comentario: Aun $n$ son un poco más complicados, uno tiene que tratar por separado los casos en que el mayor poder de $2$ que divide $n$ $2^1$ o $2^2$ y los casos en los que la potencia máxima es de $2^k$ algunos $k\ge 3$.
Añadido: En caso de que la reducción a la congruencia $w^2\equiv 1 \pmod{pq}$ parece misterioso, aquí es un más acercamiento elemental. Deje $a$ ser fijo. Queremos saber cuántas soluciones hay a la congruencia $x^2\equiv a^2\pmod{pq}$.
Reescribir esto como $(x-a)(x+a)\equiv 0 \pmod{pq}$. La congruencia tiene si uno de $x-a$ o $x+a$ es divisible por $p$, y uno de $x-a$ o $x+a$ es divisible por $q$. El $4$ soluciones se obtienen mediante el establecimiento de (1) $x\equiv a \pmod{p}$, $x\equiv a \pmod{q}$; (2) $x\equiv -a \pmod{p}$, $x\equiv -a \pmod{q}$; (3) $x\equiv a \pmod{p}$, $x\equiv -a \pmod{q}$; (4) $x\equiv -a \pmod{p}$, $x\equiv a \pmod{q}$. Cada uno de estos sistemas de $2$ congruencias tiene una única solución modulo $pq$ por el Teorema del Resto Chino.
ND Geek
Puntos
880
Esta respuesta no es tan buena como la de André Nicolás respuesta, porque él hizo su muy accesible, mientras que yo voy a ser un poco más abstracto. Sin embargo, si usted quiere entender la cantidad de residuos cuadráticos para general compuesto módulo de $m$, entonces esta es la manera de ir sobre ella.
Primero de todos, el teorema del resto Chino dice (entre otras cosas) que la (abelian) grupo multiplicativo $(\mathbb Z/pq\mathbb Z)^\times$ es isomorfo al producto directo de $(\mathbb Z/p\mathbb Z)^\times \times (\mathbb Z/q\mathbb Z)^\times$.
Luego, la existencia de raíces primitivas modulo de los números primos nos dice que cada uno de estos grupos multiplicativos son cíclicos; es decir, $(\mathbb Z/p\mathbb Z)^\times \cong \mathbb Z/(p-1)\mathbb Z$ (donde el último es un aditivo grupo abelian) y $(\mathbb Z/q\mathbb Z)^\times \cong \mathbb Z/(q-1)\mathbb Z$. Ya estamos de conmutación de la notación multiplicativa aditivo de la notación, sqaruing elementos en $(\mathbb Z/p\mathbb Z)^\times$ corresponde a duplicar elementos en $\mathbb Z/(p-1)\mathbb Z$.
Para las plazas en $(\mathbb Z/pq\mathbb Z)^\times$ (es decir, los residuos cuadráticos módulo $pq$) corresponden a los elementos de $\mathbb Z/(p-1)\mathbb Z \oplus \mathbb Z/(q-1)\mathbb Z$ donde ambos "coordenadas" son aún. Y hay exactamente $\frac{p-1}2 \frac{q-1}2$ de estos.
Para hacer el caso general, usted todavía utilizar el teorema del resto Chino; en el segundo paso, tendría que utilizar la existencia de raíces primitivas modulo cualquier extraño de potencia principal (y el leve complicación André mencionado al $8\mid m$); en el tercer paso, tendría que utilizar lo que usted sabe acerca de grupos cíclicos.
