Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

4 Answers 4

up vote 4 down vote accepted

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

share|improve this answer

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}. $$

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.