# Show the number of quadratic residues $a$ modulo $p$ with $1\leq a\leq p-1$ is $(p-1)/2$

Question: When $p$ is an odd prime, show that the number of quadratic residues $a$ modulo $p$ with $1\leq a\leq p-1$ is $(p-1)/2$

Answer: From Euler's criterion $\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod{p}$

When we apply Lagrange's theorem, the congruence $a^{(p-1)/2}\equiv 1\pmod{p}$ has at most $(p-1)/2$ solutions

By Fermat's little theorem, we have $a^{p-1}\equiv 1\pmod{p}$, so

$a^{p-1}-1\equiv(a^{(p-1)/2}-1)(a^{(p-1)/2}+1)\equiv 0\pmod{p}$

The answer then says this "has precisely $p-1$ solutions"

How do we deduce from this that this $a^{p-1}-1$ has precisely $p-1$ solutions?

By Fermat's little theorem, $a^{p-1}-1\equiv 0\pmod{p}$ has at least $p-1$ solutions, and since these are solutions to a polynomial over a field of degree $p-1$, it has at most $p-1$ solutions. This gives exactly $p-1$ solutions.
• @jgon How does this deduce at least $p-1$ solutions? Is it a standard result that $a^k-1\equiv 0\pmod{p}$ has at least $k$ solutions $\pmod{p}$? – Sam Houston May 4 '15 at 9:45
• @Dan smith No, but Fermat's little theorem says that for $1\le a\le p-1$, $a^{p-1}\equiv 1\pmod{p}$. Which is $p-1$ solutions right there. – jgon May 4 '15 at 16:26
Observe that each two of the numbers $1^2,2^2,\dotsc,(\frac{p-1}2)^2$ are non-equivalent modulo $p$ and are quadratic residues.