# ...sum of all quadratic residues modulo p...

• Mar 21st 2010, 04:12 PM
NikoBellic
...sum of all quadratic residues modulo p...
Let p be a prime > 3. Show that the sum of all the quadratic residues modulo p is divisible by p.
• Mar 21st 2010, 04:49 PM
chiph588@
Quote:

Originally Posted by NikoBellic
Let p be a prime > 3. Show that the sum of all the quadratic residues modulo p is divisible by p.

Let $\displaystyle g$ be a primitive root modulo $\displaystyle p$.

$\displaystyle A_p=\{1,g^2,g^4,\cdot\cdot\cdot, g^{p-3}\}$ is the collection of all quadratic residues.
This is because $\displaystyle |A_p| = \frac{p-1}{2}$ and every element in $\displaystyle A_p$ is a square due to the even exponent. Since there are only $\displaystyle \frac{p-1}{2}$ quadratic residues, $\displaystyle A_p$ must be the list of quadratic residues modulo $\displaystyle p$.

$\displaystyle 1+g^2+g^4+\cdot\cdot\cdot+g^{p-3} = \frac{1-g^{p-1}}{1-g^2} \equiv 0 \mod{p}$.

$\displaystyle p>3$, otherwise $\displaystyle (1-g^2)^{-1}$ doesn't exist.