Quadratic Residues

$$\legendre a p = \cases{1 & if a \hbox{ is a quadratic residue mod p} \cr -1 & if a \hbox{ is a quadratic nonresidue mod p} \cr}.$$

$$\legendre a p = a^{(p-1)/2} \mod{p}.$$


Gauss considered the proofs he gave of quadratic reciprocity one of his crowning achievements; in fact, he gave 6 distinct proofs during his lifetime. Reciprocity is a deep result: Proofs eluded both Euler and Legendre.

The reciprocity law is simple to state. For p and q odd primes, it relates solutions to the two congruences

$$x^2 = p \mod{q} \quad\hbox{and}\quad x^2 = q \mod{p}.$$

(Note how p and q switch places: This explains why it's called a reciprocity law.) The law of quadratic reciprocity says:

The congruences are either both solvable or both unsolvable, unless both primes are congruent to 3 mod 4. In that case, one is solvable while the other is not.

Gauss first gave a proof of this when he was 19!

Gauss's masterwork, the Disquisitiones Arithmeticae, was published in 1801 when Gauss was 24. It changed the course of number theory, collecting scattered results into a unified theory.

Definition. Let $(a,m) = 1$ , $m > 0$ . a is a quadratic residue mod m if the following equation has a solution:

$$x^2 = a \mod{m}.$$

Otherwise, a is a quadratic nonresidue mod m.


Example. 8 is a quadratic residue mod 17, since

$$5^2 = 8 \mod{17}.$$

However, 8 is a quadratic nonresidue mod 11, because $x^2 = 8 \mod{11}$ has no solutions.

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & n & & 0 & & 1 & & 2 & & 3 & & 4 & & 5 & & 6 & & 7 & & 8 & & 9 & & 10 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $n^2 \mod{11}$ & & 0 & & 1 & & 4 & & 9 & & 5 & & 3 & & 3 & & 5 & & 9 & & 4 & & 1 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

As the table shows, 1, 3, 4, 5, and 9 are quadratic residues mod 11. (0 is not considered a quadratic residue, since $(0,11) = 11 \ne 1$ .) But 8 is a quadratic nonresidue mod 11.

Notice the symmetry in the nonzero elements of the table. Do you see why this is happening?


Lemma. Let p be an odd prime. The congruence

$$x^2 = a \mod{p}$$

has:

(a) Only the solution $x =
   0$ if $a = 0$ .

(b) Exactly 0 or 2 solutions if $p \notdiv a$ .

Proof. $x = 0$ solves $x^2 = 0 \mod{p}$ . Conversely, if $x^2 = 0 \mod{p}$ , then $p \mid x^2$ , so $p \mid x$ , and hence $x = 0 \mod{p}$ .

Suppose $p \notdiv a$ . To show there are 0 or 2 solutions, suppose there is at least one solution b. Then $b^2 = a \mod{p}$ , so $(-b)^2 = a \mod{p}$ . I claim that b and $-b$ are distinct.

If not, then $b = -b
   \mod{p}$ , so $p \mid 2b$ . p is an odd prime, so $p \notdiv 2$ . Therefore, $p \mid b$ , $b = 0 \mod{p}$ , $b^2 = 0 \mod{p}$ , and finally $a = 0 \mod{p}$ --- contradicting $p \notdiv a$ . Hence, $b
   \ne -b \mod{p}$ .

Now I have two distinct solutions; since a quadratic equation mod p has at most two solutions (Prove it!), there are exactly two.


Example. $x^2 = 8 \mod{17}$ has 5 and 12 as solutions, and $5
   = -12 \mod{17}$ .

But note that the result is false if $p = 2$ : $x^2 = 1
   \mod{2}$ has exactly one solution ($x = 1 \mod{2}$ ).


Example. Take $p = 7$ .

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & k & & 0 & & 1 & & 2 & & 3 & & 4 & & 5 & & 6 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $k^2 \mod{7}$ & & 0 & & 1 & & 4 & & 2 & & 2 & & 4 & & 1 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

Thus, 1, 2, 4 are quadratic residues mod 7. Notice that there are equal numbers of residues and nonresidues.


Corollary. Let p be an odd prime. There are $\dfrac{p-1}{2}$ quadratic residues and $\dfrac{p-1}{2}$ quadratic nonresidues mod p in $\{1, \ldots, p - 1\}$ .

Proof. k and $-k = p - k$ have the same square mod p. That is, 1 and $p - 1$ have the same square, 2 and $p - 2$ have the same square, ..., and $\dfrac{p - 1}{2}$ and $\dfrac{p - 1}{2} + 1$ have the same square.

Thus, the number of different squares is $\dfrac{p - 1}{2}$ --- these squares are the quadratic residues, and the other $\dfrac{p - 1}{2}$ numbers in $\{1, 2, \ldots, p -
   1\}$ are quadratic nonresidues.

The fact observed in the first sentence of the proof explains the symmetries in the table of squares mod 11 and mod 7 that I gave above.

Definition. Let p be an odd prime, and let $(a,p) = 1$ . The Legendre symbol $\legendre a p$ is defined by

$$\legendre a p = \cases{1 & if a \hbox{ is a quadratic residue mod p} \cr -1 & if a \hbox{ is a quadratic nonresidue mod p} \cr}$$

Note that $a = 0$ is disallowed (since $(0,p) = p \ne 1$ ) even though $x^2 = 0 \mod{p}$ has a solution.


Example. $(5,11) = 1$ . $\legendre 5 {11} = 1$ , since $4^2 = 5 \mod{11}$ . Likewise, $\legendre {11} 5
   = 1$ , since $6^2 = 11 \mod{5}$ .

Note that 5 is congruent to 1 mod 4; as predicted by reciprocity, both of the following the congruences have solutions:

$$x^2 = 5 \mod{11} \quad\hbox{and}\quad x^2 = 11 \mod{5}. \quad\halmos$$


You might wonder about the case where $p = 2$ , or the case where the modulus is composite. For $p = 2$ , there are only two quadratic congruences:

$$x^2 = 0 \mod{2} \quad\hbox{and}\quad x^2 = 1 \mod{2}.$$

These have the solutions $x
   = 0 \mod{2}$ and $x = 1 \mod{2}$ --- nothing much is going on.

If the modulus has prime factorization $n = p_1^{r_1}\cdots p_k^{r_k}$ , then relative primality implies that it's enough to solve the congruences $x^2 = a \mod{p_i^{r_i}}$ for each i. It turns out that solving such a congruence reduces to determining whether a is a quadratic residue mod $p_i$ . Therefore, there is little harm in concentrating on the case of a single prime.


Example. $x^2 = 14 \mod{35}$ can be reduced to the simultaneous congruences

$$x^2 = 14 \mod{5} \quad\hbox{and}\quad x^2 = 14 \mod{7}.$$

These can be rewritten as

$$x^2 = 4 \mod{5} \quad\hbox{and}\quad x^2 = 0 \mod{7}.$$

The first equation has solutions $x = 2 \mod{5}$ or $x = 3 \mod{5}$ . The second equation has the single solution $x = 0 \mod{7}$ . So I have two cases.

If $x = 2 \mod{5}$ and $x = 0 \mod{7}$ , the Chinese Remainder Theorem gives $x = 7 \mod{35}$ .

If $x = 3 \mod{5}$ and $x = 0 \mod{7}$ , the Chinese Remainder Theorem gives $x = 28 \mod{35}$ .

Thus, I have two solutions mod 35 to the original quadratic congruence.


Here are some tools for computing Legendre symbols.

Theorem. (Euler) Let p be an odd prime, $a > 0$ , $(a,p) =
   1$ . Then

$$\legendre a p = a^{(p-1)/2} \mod{p}.$$

Proof. There are two cases. Suppose that $\legendre a p = 1$ . Then there is a number b such that $b^2 = a \mod{p}$ . So

$$(b^2)^{(p-1)/2} = a^{(p-1)/2} \mod{p}, \quad b^{p-1} = a^{(p-1)/2} \mod{p}.$$

If $p \mid b$ , then $p \mid b^2 = a$ \contra. So $p \notdiv b$ , and little Fermat implies that $b^{p-1} = 1 \mod{p}$ . So

$$a^{(p-1)/2} = 1 \mod{p}, \quad\hbox{and}\quad \legendre a p = a^{(p-1)/2} \mod{p}.$$

The other possibility is $\legendre a p = -1$ . In this case, consider the set $\{1, 2, \ldots, p - 1\}$ . I claim that these integers occur in pairs s, t, such that $st = a$ .

First, if $s \in \{1, 2,
   \ldots, p - 1\}$ , then s is invertible mod p. So I can write $s(s^{-1}a) = a$ , and the pair s, $s^{-1}a$ , multiplies to a.

Moreover, s and $s^{-1}a$ are distinct. If not, $s = s^{-1}a$ , or $s^2 = a$ , which contradicts $\legendre a p
   = -1$ .

Since the integers $\{1, 2,
   \ldots, p - 1\}$ divide up into pairs, each multiplying to a, and since there are $\dfrac{p-1}{2}$ pairs, I have

$$1\cdot 2\cdots (p - 1) = a^{(p-1)/2} \mod{p}.$$

By Wilson's theorem,

$$-1 = a^{(p-1)/2} \mod{p}, \quad\hbox{so}\quad \legendre a p = a^{(p-1)/2} \mod{p}.\quad\halmos$$


Example. Suppose $p = 13$ and $a =
   10$ . Then

$$a^{(p-1)/2} = 10^6 = 1 \mod{13}.$$

Hence, $\legendre{10}{13} =
   1$ , and $x^2 = 10 \mod{13}$ should have a solution. Indeed,

$$7^2 = 49 = 10 \mod{13}.\quad\halmos$$


Lemma. If $a = b \mod{p}$ , then $\legendre a p = \legendre b p$ .

Proof. If $a = b \mod{p}$ , then $x^2 = a \mod{p}$ if and only if $x^2 = b \mod{p}$ . Thus, one of these equations is solvable or not solvable if and only if the same is true for the other --- which means $\legendre a p = \legendre b p$ .

Note that I can use this result to apply Euler's formula to $\legendre a p$ for $a < 0$ by simply replacing a with $b > 0$ such that $a = b \mod{p}$ .

Lemma. Let p be an odd prime, $a, b > 0$ , $(a,p) =
   (b,p) = 1$ . Then

$$\legendre a p \legendre b p = \legendre {ab} p.$$

Proof. By Euler,

$$\legendre a p \legendre b p = a^{(p-1)/2} b^{(p-1)/2} \mod{p}, \quad\hbox{and}\quad \legendre {ab} p = (ab)^{(p-1)/2} \mod{p}.$$

Therefore,

$$\legendre a p \legendre b p = \legendre {ab} p \mod{p}.$$

The two sides of this equation are $\pm 1$ . Since p is an odd prime, the two sides can't differ by 2. Hence, they must be equal as integers:

$$\legendre a p \legendre b p = \legendre {ab} p.\quad\halmos$$

Corollary. Let p be an odd prime, $a > 0$ , $(a,p) =
   1$ . Then

$$\legendre {a^2} p = 1.\quad\halmos$$

You can use the results above to compute $\legendre a p$ for specific values of a and arbitrary p.

Lemma.

$$\legendre {-1} p = \cases{1 & if $p = 4k+ 1$ \cr -1 & if p = 4k + 3 \cr}.$$

Proof. By Euler's formula,

$$\legendre {-1} p = \legendre {p - 1} p = (p - 1)^{(p-1)/2} = (-1)^{(p-1)/2} =$$

$$\cases{(-1)^{2k} & if $p = 4k + 1$ \cr (-1)^{2k+1} & if p = 4k + 3 \cr} = \cases{1 & if $p = 4k + 1$ \cr -1 & if p = 4k + 3 \cr}.\quad\halmos$$

Using Gauss's lemma, which I'll prove shortly, you can also show that

$$\legendre {2} p = (-1)^{(p^2-1)/8}.$$

Note that the exponent on the right is actually an integer: Since $p = 2k + 1$ , $p^2 - 1 = 4k(k + 1)$ . And $4k(k + 1)$ is divisible by 8, because one of k, $k + 1$ , must be even.


Example. $\legendre {-1} {13} = 1$ , because $13 = 4\cdot 3 + 1$ . Thus, $x^2 = -1 \mod{13}$ has solutions. And in fact,

$$5^2 = 25 = 12 = -1 \mod{13}.$$

Likewise, $\legendre {-1}
   {23} = -1$ , because $23 = 4\cdot 5 + 3$ . Hence, $x^2 = -1 \mod{23}$ has no solutions.

Finally,

$$\legendre 2 7 = (-1)^{(7^2-1)/8} = 1.$$

Therefore, $x^2 = 2
   \mod{7}$ has solutions. $x = 3$ works, for instance.


Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Bruce Ikenaga's Home Page

Copyright 2013 by Bruce Ikenaga