Primero una "demostración" con un ejemplo. Sea $p=11$.
k------1 2 3 4 5 6 7 8 9 10
k^2----1 4 9 5 3 3 5 9 4 1
¿Qué vemos? Una simetría en los residuos cuadráticos ¿no es cierto?
Bueno, pues esta simetría se puede demostrar así: Sea $k$ uno de los elementos del sistema de residuos. Entonces $k^2$ es equiresidual con $(p-k)^2$ en la división entre $p$. Para verlo basta con desarrollar el binomio: $(p-k)^2=p^2-2kp+k^2.$ En otras palabras, hay $(p-1)/2$ pares equiresiduales en $1^2,2^2,\ldots,(p-1)^2$.
En resumen, el número de residuos cuadráticos es a lo más $(p-1)/2$ (son los primeros $(p-1)/2$ o menos).
Veamos si entre los primeros $(p-1)/2$ hay dos equiresiduales. Para ello supongamos que $j^2$ es equiresidual con $k^2$, con $j,k$ cualesquiera dos de $1,2,\ldots,(p-1)/2$. Esto significaría que $k^2-j^2$ es múltiplo de $p$. Y como $k^2-j^2=(k-j)(k+j)$, entonces $p$ divide a uno de los factores. Pero $k+j$ es menor que $p$ (cada sumando es a lo más $(p-1)/2$) . Luego, es primo con $p$. De aquí que $k-j$ sea múltiplo de $p$. Así que $j=k$. Se concluye que ningún par de cuadrados entre los primeros $(p-1)/2$ de $1^2,2^2,\ldots,(p-1)^2$ son congruentes entre sí. Y como entre esos primeros $(p-1)/2$ residuos no hay dos equiresiduales, entonces el número de residuos cuadráticos en $1,2,\ldots,p-1$ es al menos $(p-1)/2$. Pero ya habíamos demostrado que eran a lo más $(p-1)/2$. Luego, su número es
$(p-1)/2$.
