# 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.

• +1 for a nice answer! However, it's not using the argument the O.P. talked about, so you're not answering his precise question. – Daniel May 3 '15 at 21:36
• @Solid Snake Oh I was under the impression that the OP was was asking about the last step in the proof. of the statement given in Question. – jgon May 3 '15 at 21:38
• Me too, I just noticed he says "How do we deduce from this...", I think he's referring to the equality above. However, I'm not sure now. In any case, your answer is great :) – Daniel May 3 '15 at 21:41
• @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.