In a previous post called Solving Quadratic Congruences, we discuss the solvability of the quadratic congruence

$x^2 \equiv a \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

where $p$ is an odd prime and $a$ is relatively prime to $p$. In this post, we continue to discuss the solvability of equation (1) from the view point of quadratic residues. In this subsequent post, we discuss specific algorithms that produce solutions to such equations.

____________________________________________________________________________

Definition

Let $p$ be an odd prime. Let $a$ be an integer that is not divisible by $p$ (equivalently relatively prime to $p$). Whenever equation (1) has solutions, we say that the number $a$ is a quadratic residue modulo $p$. Otherwise, we say that the number $a$ is a quadratic nonresidue modulo $p$. When the context is clear, the word quadratic is sometimes omitted.

The term quadratic residues is more convenient to use. Instead of saying the equation $x^2 \equiv a \ (\text{mod} \ p)$ has a solution, we say the number $a$ is a quadratic residue for the modulus in question. The significance of the notion of quadratic residue extends beyond the convenience of having a shorter name. It and and the Legendre symbol lead to a large body of beautiful and deep results in number theory, the quadratic reciprocity theorem being one of them.

One property of the quadratic congruence equation (1) is that when equation (1) has solutions, it has exactly two solutions among the set $\left\{1,2,3,\cdots,p-1 \right\}$ (see Lemma 1 in the post Solving Quadratic Congruences). Thus among the integers in the set $\left\{1,2,3,\cdots,p-1 \right\}$, $\displaystyle \frac{p-1}{2}$ of them are quadratic residues and the other half are quadratic nonresidues modulo $p$.

For example, consider the modulus $p=11$. Among the numbers in the set $\left\{1,2,3,\cdots,10 \right\}$, the numbers $1,3,4,5,9$ are quadratic residues and the numbers $2,6,7,8,10$ are quadratic nonresidues. See the following two tables.

$\displaystyle \begin{bmatrix} x&\text{ }&x^2 \equiv \ (\text{mod} \ 11) \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1 \\ 2&\text{ }&4 \\ 3&\text{ }&9 \\ 4&\text{ }&5 \\ 5&\text{ }&3 \\ 6&\text{ }&3 \\ 7&\text{ }&5 \\ 8&\text{ }&9 \\ 9&\text{ }&4 \\ 10&\text{ }&1 \end{bmatrix}$

The above table shows the least residues of $x^2$ for $x \in \left\{1,2,3,\cdots,10 \right\}$. It shows that there $x^2$ can only be $1,3,4,5,9$. Thus these are the quadratic residues. The table below shows the status of residue/nonresidue among the integers in $\left\{1,2,3,\cdots,10 \right\}$.

$\displaystyle \begin{bmatrix} x&\text{ }&\text{residue or nonresidue mod } 11 \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&\text{residue} \\ 2&\text{ }&\text{nonresidue} \\ 3&\text{ }&\text{residue} \\ 4&\text{ }&\text{residue} \\ 5&\text{ }&\text{residue} \\ 6&\text{ }&\text{nonresidue} \\ 7&\text{ }&\text{nonresidue} \\ 8&\text{ }&\text{nonresidue} \\ 9&\text{ }&\text{residue} \\ 10&\text{ }&\text{nonresidue} \end{bmatrix}$

____________________________________________________________________________

Legendre Symbol

The notion of quadratic residues is often expressed using the Legendre symbol, which is defined as follows:

$\displaystyle \biggl(\frac{a}{p}\biggr)=\left\{\begin{matrix}1&\ \text{if } a \text{ is a quadratic residue modulo }p \\{-1}&\ \text{if } a \text{ is a quadratic nonresidue modulo }p \end{matrix}\right.$

The bottom number $p$ in the above notation is an odd prime. The top number $a$ is an integer that is not divisible by $p$ (equivalently relatively prime to $p$). Despite the appearance, the Legendre symbol is not the fraction of $a$ over $p$. It follows from the definition that the symbol has the value of one if the equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions. It has the value of negative one if the equation $x^2 \equiv a \ (\text{mod} \ p)$ has no solutions.

For example, $\displaystyle \biggl(\frac{a}{11}\biggr)=1$ for $a=1,3,4,5,9$ and and $\displaystyle \biggl(\frac{a}{11}\biggr)=-1$ for $a=2,6,7,8,10$. To evaluate $\displaystyle \biggl(\frac{11}{3}\biggr)$, consider the equation $x^2 \equiv 11 \ (\text{mod} \ 3)$, which is equivalent to the equation $x^2 \equiv 2 \ (\text{mod} \ 3)$. This last equation has no solutions. Thus $\displaystyle \biggl(\frac{11}{3}\biggr)=-1$.

The quadratic reciprocity law discussed below allows us to calculate $\displaystyle \biggl(\frac{11}{3}\biggr)$ by flipping $\displaystyle \biggl(\frac{3}{11}\biggr)$. In certain cases, flipping the symbol keeps the same sign. In other cases, flipping introduces a negative sign (as in this example).

____________________________________________________________________________

Basic Properties

Euler’s Criterion is a formula that determines whether an integer is a quadratic residue modulo an odd prime. We have the following theorem. A proof of Euler’s Criterion is found in this post.

Theorem 1 (Euler’s Criterion)

Let $p$ be an odd prime number. Let $a$ be a positive integer that is not divisible by $p$. Then the following property holds.

$\displaystyle \biggl(\frac{a}{p}\biggr) \equiv \displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p)$

The following lemma shows a connection between the notion of quadratic residue and the notion of primitive roots.

Lemma 2

Let $p$ be an odd prime. Let $g$ be a primitive root modulo $p$. Let $a$ be a positive integer that is not divisible by $p$. Then we have the following equivalence.

1. The number $a$ is a quadratic residue modulo $p$ if and only if $a \equiv g^{2k} \ (\text{mod} \ p)$ for some integer $k$.
2. Or equivalently, the number $a$ is a quadratic nonresidue modulo $p$ if and only if $a \equiv g^{2k+1} \ (\text{mod} \ p)$ for some integer $k$.

Proof of Lemma 2
A primitive root $g$ exists since the modulus $p$ is prime (see Theorem 1 in the post Primitive roots of prime moduli). Furthermore, any integer that is not divisible by $p$ is congruent to a unique element of the set $\left\{g^1,g^2,g^3,\cdots,g^{p-1} \right\}$. Thus for the number $a$ in question, either $a \equiv g^{2k}$ or $a \equiv g^{2k+1}$. We can conclude that the first bullet point in the lemma is equivalent to the second bullet point.

We prove the first bullet point. First we show the direction $\Longleftarrow$. Suppose $a \equiv g^{2k} \ (\text{mod} \ p)$. Clearly the equation $x^2 \equiv a \ (\text{mod} \ p)$ has a solution since $(g^k)^2 \equiv a \equiv g^{2k} \ (\text{mod} \ p)$.

Now we show the direction $\Longrightarrow$. We prove the contrapositive. Suppose that $a \equiv g^{2k+1} \ (\text{mod} \ p)$. We wish to show that $a$ is a quadratic nonresidue modulo $p$. Suppose not. Then $t^2 \equiv a \ (\text{mod} \ p)$ for some $t$. It follows that $p \not \lvert \ t$. Note that if $p \ \lvert \ t$, $p \ \lvert \ a$, which is not true. By Fermat’s little theorem, we have $t^{p-1} \equiv 1 \ (\text{mod} \ p)$. We have the following derivation.

$\displaystyle (g^{2k+1})^{\frac{p-1}{2}} \equiv (t^{2})^{\frac{p-1}{2}} \equiv t^{p-1} \equiv 1 \ (\text{mod} \ p)$

On the other hand, we can express $\displaystyle (g^{2k+1})^{\frac{p-1}{2}}$ as follows:

$\displaystyle (g^{2k+1})^{\frac{p-1}{2}} \equiv g^{k(p-1)} \cdot g^{\frac{p-1}{2}} \equiv (g^{p-1})^k \cdot g^{\frac{p-1}{2}} \equiv 1^k \cdot g^{\frac{p-1}{2}} \equiv g^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$

Note that the last congruence $g^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$ contradicts the fact that $g$ is a primitive root modulo $p$ since $p-1$ is the least exponent that such that $g^{p-1} \equiv 1 \ (\text{mod} \ p)$. So $a$ cannot be a quadratic residue modulo $p$. We have proved that if $a \equiv g^{2k+1} \ (\text{mod} \ p)$, then $a$ is a quadratic nonresidue modulo $p$. Equivalently, if $a$ is a quadratic residue modulo $p$, then $a \equiv g^{2k} \ (\text{mod} \ p)$. Thus the lemma is established. $\blacksquare$

We can also obtain an alternative proof by using Theorem 1 (Euler’s Criterion). We show $\Longleftarrow$ of both bullet points.

First, $\Longleftarrow$ of the first bullet point. Suppose $a \equiv g^{2k} \ (\text{mod} \ p)$. Then $\displaystyle (g^{2k})^{\frac{p-1}{2}} \equiv (g^{p-1})^k \equiv 1^k \equiv 1 \ (\text{mod} \ p)$. Thus $\displaystyle \biggl(\frac{a}{p}\biggr)=1$ and $a$ is a quadratic residue modulo $p$ by Euler’s Criterion.

Now $\Longleftarrow$ of the second bullet point. Suppose $a \equiv g^{2k+1} \ (\text{mod} \ p)$. Then $\displaystyle (g^{2k+1})^{\frac{p-1}{2}} \equiv (g^{p-1})^k \cdot g^{\frac{p-1}{2}} \equiv g^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$. The last congruence $g^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$ because $g$ is a primitive root. Thus $\displaystyle \biggl(\frac{a}{p}\biggr)=-1$ and $a$ is a quadratic nonresidue modulo $p$ by Euler’s Criterion. $\blacksquare$

Remark
Each number in the set $\left\{1,2,3,\cdots,p-1 \right\}$ is congruent to a power of the primitive root $g$ in question. Lemma 2 indicates that the even powers are the quadratic residues while the odd powers are the quadratic nonresidues. The following lemma is a corollary of Lemma 2.

Lemma 3

Let $p$ be an odd prime. Then we have the following.

1. If $a$ and $b$ are quadratic residues modulo $p$, then $ab$ is a quadratic residue modulo $p$.
2. If $a$ is a quadratic residue and $b$ is a quadratic nonresidue modulo $p$, then $ab$ is a quadratic nonresidue modulo $p$.
3. If $a$ and $b$ are quadratic nonresidues modulo $p$, then $ab$ is a quadratic residue modulo $p$.

Proof of Lemma 3
Let $g$ be a primitive root modulo $p$. Then we express each residue or nonresidue as a power of $g$ and then multiply the two powers of $g$ by adding the exponents as in the following.

$\displaystyle g^{2j} \cdot g^{2k}=g^{2(j+k)}$

$\displaystyle g^{2j} \cdot g^{2k+1}=g^{2(j+k)+1}$

$\displaystyle g^{2j+1} \cdot g^{2k+1}=g^{2(j+k+1)}$

The first product above has an even exponent. Thus the product of two quadratic residues is a quadratic residue (the first bullet point). The second product above has an odd exponent. Thus the product of a quadratic residue and a quadratic nonresidue is a nonresidue (second bullet point). The third product above has an even exponent. Thus the product of two nonresidues is a residue. $\blacksquare$

One part of the following theorem is a corollary of Lemma 3.

Theorem 4

Let $p$ be an odd prime. Then we have the following results.

1. If $p \not \lvert \ a$ and $a \equiv b \ (\text{mod} \ p)$, then $\displaystyle \biggl(\frac{a}{p}\biggr)=\biggl(\frac{b}{p}\biggr)$.
2. If $p \not \lvert \ a$, then $\displaystyle \biggl(\frac{a^2}{p}\biggr)=1$.
3. if $p \not \lvert \ a$ and $p \not \lvert \ b$, then $\displaystyle \biggl(\frac{a}{p}\biggr) \cdot \biggl(\frac{b}{p}\biggr)=\biggl(\frac{ab}{p}\biggr)$.

Proof of Theorem 4
The first and second bullets points are straightforward. We prove the third bullet point, which follows from Lemma 3. Given $a$ and $b$, they would fall into one of the three cases of Lemma 3. Translating each case of Lemma 3 will give the correct statement in Legendre symbol. $\blacksquare$

____________________________________________________________________________

Quadratic reciprocity is a property that indicates how $\displaystyle \biggl(\frac{p}{q}\biggr)$ and $\displaystyle \biggl(\frac{q}{p}\biggr)$ are related when both $p$ and $q$ are odd prime. Even thought the statement of the theorem is easy to state and understand, it is an unexpected and profound result. Our goal here is quite simple – state the theorem and demonstrate how it can be used to simplify calculations. We have the following theorems.

Let $p$ and $q$ be two distinct odd prime numbers. The following statement holds.

$\displaystyle \biggl(\frac{q}{p}\biggr)=\left\{\begin{matrix} \displaystyle \biggl(\frac{p}{q}\biggr) &\ \text{if } p \equiv 1 \ (\text{mod} \ 4) \text{ or } q \equiv 1 \ (\text{mod} \ 4) \\{\displaystyle -\biggl(\frac{p}{q}\biggr)}&\ \text{if } p \equiv q \equiv 3 \ (\text{mod} \ 4) \end{matrix}\right.$

Theorem 6

Let $p$ and $q$ be two distinct odd prime numbers. The following statement holds.

$\displaystyle \biggl(\frac{2}{p}\biggr)=\left\{\begin{matrix} 1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 8) \text{ or } p \equiv 7 \ (\text{mod} \ 8) \\{-1}&\ \text{if } p \equiv 3 \ (\text{mod} \ 8) \text{ or } p \equiv 5 \ (\text{mod} \ 8) \end{matrix}\right.$

Theorem 7

Let $p$ and $q$ be two distinct odd prime numbers. The following statement holds.

$\displaystyle \biggl(\frac{-1}{p}\biggr)=\left\{\begin{matrix} 1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 4) \\{-1}&\ \text{if } p \equiv 3 \ (\text{mod} \ 4) \end{matrix}\right.$

Theorems 4, 5, 6 and 7 are tools for evaluating Legendre symbols. We demonstrate with examples.

____________________________________________________________________________

Examples

Example 1
Is $1776$ a quadratic residue modulo the prime $1777$?

We evaluate the symbol $\displaystyle \biggl(\frac{1776}{1777}\biggr)=\biggl(\frac{-1}{1777}\biggr)$. Note that $1777 \equiv 1 \ (\text{mod} \ 4)$. By Theorem 7, $\displaystyle \biggl(\frac{-1}{1777}\biggr)=1$. It follows that $1776$ is a quadratic residue modulo the prime $1777$. Furthermore, $x^2 \equiv 1776 \ (\text{mod} \ 1777)$ has solutions.

Example 2
Solve $x^2 \equiv 899 \ (\text{mod} \ 50261)$.

Note that $50261$ is a prime while $899$ is not since $899=29 \cdot 31$. After applying Theorem 4, we have:

$\displaystyle \biggl(\frac{899}{50261}\biggr)=\displaystyle \biggl(\frac{29}{50261}\biggr) \displaystyle \biggl(\frac{31}{50261}\biggr)$.

Now we can start using quadratic reciprocity.

\displaystyle \begin{aligned} \displaystyle \biggl(\frac{899}{50261}\biggr)&=\displaystyle \biggl(\frac{29}{50261}\biggr) \biggl(\frac{31}{50261}\biggr) \\&=\displaystyle \biggl(\frac{50261}{29}\biggr) \biggl(\frac{50261}{31}\biggr) \\&=\displaystyle \biggl(\frac{4}{29}\biggr) \biggl(\frac{10}{31}\biggr) \\&=\displaystyle \biggl(\frac{2}{29}\biggr)^2 \biggl(\frac{2}{31}\biggr) \biggl(\frac{5}{31}\biggr) \\&=(-1)^2 \cdot 1 \cdot 1 \\&=1 \end{aligned}

The above derivation is the result of applying Theorems 4, 5 and 7. Of particular importance is the repeated applications of Theorem 5 (Quadratic Reciprocity) so that the numbers in the Legendre symbols are much smaller than the ones we start with.

As useful as it is, the theorem for quadratic reciprocity does not show us how to solve the equation $x^2 \equiv 899 \ (\text{mod} \ 50261)$. See Example 2 in the post Solving Quadratic Congruences to see how it can be solved.

____________________________________________________________________________

$\copyright \ 2013 - 2015 \text{ by Dan Ma}$
Revised December 9, 2015