Find the sum of quadratic residues modulo $101$

contest-mathelementary-number-theorymodular arithmeticprimitive-rootsquadratic-residues

Given that $2$ is a primitive root (mod $101$), find the remainder when the sum of all the quadratic residues (mod $101$) is divided by $101$. A quadratic residue $r$ is a residue (mod $101$) such that there exists some $x$ such that $x^2\equiv r \;(\bmod 101)$.

I know there's a formula for this, but I don't know how to prove it. $p*(p-1)/4,$ I think. Also, I'm pretty sure the answer to this question is $0$ but when I submitted $0$, it was wrong.

Best Answer

I'm pretty sure it's $0$ too.

One way to see this: given $2$ is a primitive root,

the quadratic residues (besides $0$) are $2^2, 2^4, 2^6, \dots$, and $2^{100}$,

so their sum is $2^2+2^4+2^6+\cdots+2^{100}=\dfrac{2^{102}-2^2}{2^2-1}=\dfrac23(2^{101}-2),$

which is a multiple of $101$ by Fermat's little theorem.

Another way to see this: since $101\equiv1\pmod4,$ $-1$ is a quadratic residue mod $101$,

so for every quadratic residue in the sum,

its additive inverse $\bmod 101$ is also a quadratic residue in the sum,

so the sum is $0$.