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 k2 es equiresidual con (p−k)2 en la división entre p. Para verlo basta con desarrollar el binomio: (p−k)2=p2−2kp+k2. En otras palabras, hay (p−1)/2 pares equiresiduales en 12,22,…,(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 j2 es equiresidual con k2, con j,k cualesquiera dos de 1,2,…,(p−1)/2. Esto significaría que k2−j2 es múltiplo de p. Y como k2−j2=(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 12,22,…,(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,…,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.