Damos dos soluciones, la segunda mucho más hábil que la primera.
La primera forma: Supongamos que $1\le i\le p-1$ y $1\le j\le q-1$ . Por el Teorema Chino del Resto, existe un único $a$ en el intervalo $1\le a\le pq-1$ tal que $a\equiv i \pmod{p}$ y $a\equiv j \pmod{q}$ . Además, todos los $(p-1)(q-1)$ $a$ en este intervalo que son relativamente primos a $n$ surgen de esta manera.
Obtenemos el símbolo de Jacobi de $a$ es $1$ precisamente si $i$ es un QR de $p$ y $j$ es un QR de $q$ o si $i$ es un NR de $p$ y $j$ es un NR de $q$ . Hay $\frac{p-1}{2}\cdot\frac{q-1}{2}$ del primer tipo, y el mismo número del segundo tipo.
Esencialmente la misma idea funciona para el símbolo de Jacobi $-1$ . Sin embargo, es más rápido observar que nuestra respuesta para el símbolo de Jacobi $1$ se simplifica a $\frac{(p-1)(q-1)}{2}$ que es la mitad de $\varphi(pq)$ .
Segundo camino: Sin contar explícitamente, se puede demostrar que en el intervalo $[1,pq-1]$ hay el mismo número de $a$ con el símbolo de Jacobi $1$ y de $a$ con el símbolo de Jacobi $-1$ . Eso demuestra que hay $\varphi(pq)/2$ de cada tipo.
El argumento es el siguiente. Hay una $c$ con el símbolo de Jacobi $-1$ . Mira todo $x$ que pertenece a una clase de residuo reducido módulo $pq$ , digamos que todos los números entre $1$ y $pq$ relativamente primo a $pq$ . Considere todos los $cx$ . Esto nos da una clase de residuo reducido modulo $pq$ . Pero el mapeo que toma $x$ a $cx$ transforma los números con el símbolo de Jacobi $1$ a los números con símbolo de Jacobi $-1$ y viceversa. Así que debe haber igual número de cada tipo.
Observación: Para la segunda forma, tenemos que demostrar que hay es a $c$ con el símbolo de Jacobi $-1$ . Para ello, dejemos que $b$ sea un no-residuo cuadrático de $p$ y utilizar el Teorema del Resto Chino para demostrar que existe un $c$ que es congruente con $b$ modulo $p$ y decir a $1$ modulo $q$ .
Tenga en cuenta que si $p_1,p_2,\dots p_k$ son primos Impares distintos, y $m$ es su producto, el mismo El argumento muestra que hay $\varphi(m)/2$ números en el intervalo $[1,m]$ que tienen el símbolo de Jacobi módulo $m$ igual a $1$ y $\varphi(m)/2$ que tienen el símbolo de Jacobi $-1$ .
