Question

Show that if p is an odd prime, then there are exactly $(p-1)/2$quadratic residues of p among the integers 1, 2,...,p-1.

Short answer

If p is an odd prime, then there are exactly $(p-1)/2$quadratic residues of p among the integers 1, 2,...,p-1.

Step-by-step solution

Step: 1

The quadratic residue of p is an integer $a\text{if}\gcd (a,p)=1$and the congruence $x^2\equiv a(modp)$has a solution.

Consider the list $x^{2}modp\text{for every}x\in \{1,2,\dots p-1\}$that gives p-1 numbers between 1 and p-1. It implies that every p-1 in this list appears exactly twice.

It can be concluded that exactly half of the p-1 numbers must appear. As a result, there are exactly $\frac{p-1}{2}$quadratic residues of p.