Quadratic Residues

Let $a\in {\mathbb{Z}}_n$. We say $a$ is a quadratic residue if there exists some $x$ such that $x^2=a$. We shall focus on the case when $n$ is prime.

Let $p$ be a prime. From now assume $p>2$. The case $p=2$ is easy anyway. Let $g$ be a generator of ${\mathbb{Z}}_p^{*}$. Any $a\in {\mathbb{Z}}_p^{*}$ can be written as $g^k$ for some $k\in \{1,...,p-1\}$.

Say $k$ is even. Write $k=2m$. Then $(g^m{)}^2=a$, so $a$ is a quadratic residue. Exactly half of $\{1,...,p-1\}$ is even (since $p$ is odd), hence at least half of the elements of ${\mathbb{Z}}_p^{*}$ are quadratic residues.

Suppose we have $b^2=a$. Then $(-b{)}^2=a$ as well, and since $b\ne -b$ (since $p>2$) every quadratic residue has at least two square roots (actually we know from before there can be at most two), thus at most half the elements of ${\mathbb{Z}}_p^{*}$ are quadratic residues. (Otherwise there are more square roots than elements!)

Thus exactly half of ${\mathbb{Z}}_p^{*}$ are quadratic residues, and they are the even powers of $g$.

Given $a=g^k$, consider the effect of exponentiating by $(p-1)/2$. If $k$ is odd, say $k=2m+1$, we get $$a^{(p-1)/2}=g^{(2m+1)(p-1)/2}={g^{(p-1)}}^m{g}^{(p-1)/2}=g^{(p-1)/2}$$

The square of $g^{(p-1)/2}$ is $g^{p-1}=1$, so $g^{(p-1)/2}$ is $1$ or $-1$. But $g$ has order $p-1$ ($g$ is a generator) thus we must have $g^{(p-1)/2}=-1$.

If $k$ is even, say $k=2m$, then $a^{(p-1)/2}={g^{(p-1)}}^m=1$.

Thus one way to tell if $a$ is a quadratic residue is to compute $a^{(p-1)/2}$: if the result is $1$, then $a$ is a quadratic residue, otherwise the result is $-1$ and $a$ is a quadratic nonresidue.

Example: In ${\mathbb{Z}}_p$, if $(p-1)/2$ is even (so $p=1(mod4)$), then $-1$ is a quadratic residue, otherwise $-1$ is a quadratic nonresidue.

The Legendre Symbol

This fact (sometimes called Euler's Criterion) is so useful that we define the Legendre symbol for odd primes $p$ and integers $a$ by $$(\frac{a}{p})=a^{(p-1)/2}.$$ The symbol can also be written as $(a\mid p)$.

Thus:

• $(\frac{a}{p})=1$ if $a$ is a quadratic residue of $p$

• $(\frac{a}{p})=-1$ if $a$ is a quadratic nonresidue of $p$

• $(\frac{a}{p})=0$ if $a=0$ modulo $p$

It is not hard to see that for any integer $b$ $$(\frac{a}{p})(\frac{b}{p})=(\frac{ab}{p})$$ and for any $r$ coprime to $p$ $$(\frac{a}{p})(\frac{a{r}^2}{p})=(\frac{a}{p})$$

Gauss' Lemma

There is a less obvious way to compute the Legendre symbol. This method allows us to easily evaluate $(\frac{2}{p})$, among other things. Before stating the method formally, we demonstrate it with an example.

Let $p=17$, and $a=7$. There are $16$ nonzero elements $\{\mathrm{1,...,16}\}$. Consider the first half $\{\mathrm{1,...,8}\}$ and multiply them all by $7$ to get $7,14,4,11,1\mathrm{,8},15,5$. As integers, let us count the number of them that are greater than $p/2$ (that is, $9$ or higher).

Note: even though there is no way to define inequalities modulo $p$, we can view elements of ${\mathbb{Z}}_p$ as integers in $\{0,...,p-1\}$ and look at sizes there, though it is not yet clear why we want to do this.

$14,11$ and $15$ are the only ones in the set that are greater than $p/2$, so there are exactly $3$ of them. Then Gauss' Lemma states that if we take this $3$ and raise $-1$ to this power, then we have $(\frac{a}{p})$, that is: $$(\frac{7}{17})=(-1{)}^3=-1.$$

Theorem: Let $p$ be an odd prime, $q$ be an integer coprime to $p$. Consider the set $\{q,2q,...,q(p-1)/2\}$ and view each member is an integer in $\{0,...,p-1\}$. Let $u$ be the number of members in this set that are greater than $p/2$. Then $$(\frac{q}{p})=(-1{)}^u.$$

Proof: Let $b_1,...,b_t$ be the members of the set less than $p/2$, and $c_1,...,c_u$ be the members greater than $p/2$. Then $u+t=(p-1)/2$. Consider the sequence $$0<b_1,...,b_t,p-c_1,...,p-c_u<p/2$$

Each of these are distinct: clearly $b_i\ne b_j$ and $c_i\ne c_j$ whenever $i\ne j$ (since $q$ is invertible), and if $b_i=p-c_j$, then let $b_i=rq,c_j=sq$. Then $r+s=0$, which is a contradiction since $$0<r,s<p/2.$$ Hence they must be precisely the numbers $1,...,(p-1)/2$ in some order, thus $$\begin{array}{ccc}q(2q)...(q(p-1)/2)& =& b_1...b_t{c}_1...c_u\\ & =& (-1{)}^u{b}_1...b_t(p-c_1)...(p-c_u)& =& (-1{)}^u(\frac{p-1}{2})!\end{array}$$ Dividing both sides by $((p-1)/2))!$ completes the proof.$\blacksquare$

For example, let $p$ be an odd prime and take $q=2$. Consider the sequence $2,2\times \mathrm{2,...,2}(p-1)/2$. Note these are positive least residues. Now $p=8x+y$ for some integer $x$ and $y\in \{\mathrm{1,3,5,7}\}$. By considering each case we see that the number of elements greater than $p/2$ is even when $p=1,7(mod8)$ and odd when $p=3,5(mod8)$. We can restate this as follows.

Theorem: Let $p$ be an odd prime. $$(\frac{2}{p})=(-1{)}^{\frac{p^2-1}{8}}=(-1{)}^{\lfloor \frac{p+1}{4}\rfloor }$$

Proof: See the last paragraph, and note that $(p^2-1)/8$ is even when $p=\pm 1(mod8)$ and odd otherwise. Similarly for $\lfloor (p+1)/4\rfloor$. $\blacksquare$

Example: By Gauss' Lemma, $(\frac{3}{p})=1$ if $p=\pm 1(mod12)$ and $-1$ otherwise ($p=\pm 5(mod12)$). Combining this with the above result for $-1(modp)$ we have $(\frac{-3}{p})=1$ if $p=1(mod6)$ and $-1$ otherwise ($p=-1(mod6)$).