# Number of quadratic residues mod $p$

I saw in a comment to this question that there are exactly $\frac{p-1}{2}$ quadratic redidues in $\mathbb{F}_p$, but I cannot find the proof by myself (it's been ages since I last touched this kind of problems). Can anyone provide some hints, or (it would be even better, I suppose), some reference, preferably available online, concerning this kind of algebra?

-

Let $p$ be an odd prime. If $a$ not congruent to $0$ modulo $p$, the congruence $x^2\equiv a\pmod {p}$ has two solutions or none.

This means that viewed as a function on the non-zero elements of $\mathbb{Z}_p$, the squaring function is $2$ to $1$, meaning that its range has cardinality $(p-1)/2$.

Remark: The fact that if there is a solution, there are exactly $2$, is true in all fields $F$ of characteristic different from $2$. For suppose that in the field $F$, we have $a=b^2$, where $a\ne 0$. Then the equation $x^2=b^2$ can be rewritten as $(x-b)(x+b)=0$, so its only solutions are $b$ and $-b$, which are different unless $F$ has characteristic $2$.

-

Let $p>2$. The map $f:\Bbb Z_p^\times\rightarrow\Bbb Z_p^\times$ given by $f(x)=x^2$ is an homomorphism, because $f(xy)=(xy)^2=x^2y^2=f(x)f(y)$. By the isomorphism theorem we know that $${\rm Im}(f)\simeq \Bbb Z_p^\times/\ker(f).$$ Since $\ker(f)$ is just the set of roots of $x^2-1$, it is immediate that $\ker(f)=\{\pm1\}$ and $|{\rm Im}(f)|=(p-1)/2$, thus showing that there are exactly $(p-1)/2$ non zero classes that are squares.

Also, using the fact that $\Bbb Z_p^\times$ is cyclic it is easy to show that $x\in\Bbb Z_p^\times$ is a square if and only if $$x^{\frac{p-1}2}=1.$$ This links the above to the fact that $$\left(\frac xp\right)=(-1)^{\frac{p-1}2}.$$

-

Let $p>2$ be a prime and consider the following map: $$\psi : (\mathbb{F}_p)^\times \to (\mathbb{F}_p)^\times$$ that sends $\psi(x)\equiv x^2 \bmod p$. This is a homomorphism of groups. Indeed: $$\psi(x\cdot y) \equiv (x\cdot y)^2 \equiv x^2\cdot y^2 \equiv \psi(x)\cdot \psi(y)\bmod p.$$ Moreover, the kernel has order $2$, because $\psi(x)\equiv 1 \bmod p$ if and only if $x^2\equiv 1 \bmod p$ if and only if $x\equiv \pm 1\bmod p$. (Note: a prime $p$ divides $x^2-1=(x-1)(x+1)$ if and only if $p$ divides $x+1$ or $x-1$.)

Hence, the image of $\psi$ is isomorphic to $\mathbb{F}_p^\times/\{\pm 1\}$, which has order $\frac{p-1}{2}$. Since the image of $\psi$ is exactly the subgroup of quadratic residues modulo $p$, we obtain the desired result.

-

Let $g$ be a primitive root modulo $p$, i.e. $1,g,g^2,\ldots,g^{p-2}$ are the nonzero elements of $\mathbb F_p$. Show that $g^n$ is a quadratic residue iff $n$ is even, so $1,g^2,\ldots,g^{p-3}$ are all quadratic residues and their number is $(p-1)/2$.

Alternatively, consider $$\prod_{a\in\mathbb F_p^\times}(X-a) = X^{p-1}-1 = (X^\frac{p-1}{2}-1)(X^\frac{p-1}{2}+1).$$ By Euler's criterion, $a\in \mathbb F_p^\times$ is a quadratic residue iff $a^\frac{p-1}{2} \equiv 1\pmod p$, i.e. iff $a$ is a root of $X^\frac{p-1}{2}-1$. The above factorisation shows that the number of those roots is exactly $(p-1)/2$.

-