The Legendre symbol

The law of quadratic reciprocity is a beautiful result. It is also an excellent tool to answer the question: given an odd prime p, and given that a is an integer such that a and p are relatively prime, is a is a quadratic residue modulo p, in other words, is the equation x^2 \equiv a \ (\text{mod} \ p) solvable? Using the law of quadratic reciprocity requires the evaluation of the Legendre symbol. The focus of this post is on the Legendre symbol as well as related concepts of quadratic residues and the law of quadratic residues. The versatility of the law of quadratic reciprocity is demonstrated with examples.

____________________________________________________________________________

Quadratic Residues

The setting is that the modulus in question is an odd prime p. Consider an integer a such that a and p are relatively prime, i.e. having no common prime factor. The number a is said to be a quadratic residue modulo p if the equation x^2 \equiv a \ (\text{mod} \ p) has an integer solution in x. Another way to say this is that a is a quadratic residue modulo p if there exists a square root of a modulo p (a square root would be a solution to the equation). If the integer a is not a quadratic residue modulo p, we say that a is a quadratic nonresidue modulo p. If the context is clear, the word quadratic can be omitted. We can then say a is a residue modulo p or a is a nonresidue modulo p.

Since every integer is congruent modulo p to one of the numbers in the set \mathbb{Z}_p=\left\{0,1,2,\cdots,p-1 \right\}, the integers a can be considered from the set \mathbb{Z}_p^*=\left\{1,2,\cdots,p-1 \right\} (the non-zero elements of \mathbb{Z}_p).

Let’s look at a quick example. Let p=11. Squaring each number in \mathbb{Z}_{11} produces the set \left\{0^2,1^2,2^2,\cdots,10^2 \right\}. Reducing modulo 11 produces the set \left\{0,1,4,9,5,3 \right\}. Thus the integers 1, 3, 4, 5 and 9 are quadratic residues modulo 11. The square roots of each residue are the solutions to the equation x^2 \equiv a \ (\text{mod} \ 11). For a=3, the solutions are x = 5 and 6. There are two square roots of 3 modulo 11, namely 5 and 6.

When the modulus is small, it is easy to find all quadratic residues simply by squaring all the numbers in \mathbb{Z}_p^*. The focus in this post is on how to use the law of quadratic reciprocity to determine whether a given a is a quadratic residue modulo a large odd prime p.

To check whether the integer a is a quadratic residue modulo an odd prime p, the most important idea, before considering the law of reciprocity, is to check the modular exponentiation a^{(p-1)/2} \ (\text{mod} \ p). If the result is congruent to 1 modulo p, then a is a quadratic residue modulo p. If the result is congruent to -1 modulo p, then a is a quadratic nonresidue modulo p. This is called Euler’s Criterion (proved here). For clarity, it is stated below.

Theorem 1 (Euler’s Criterion)
Let p be an odd prime. Let a be an integer that is relatively prime to p. Then the integer a is a quadratic residue modulo p if and only if \displaystyle a^{(p-1)/2} \equiv 1 \ (\text{mod} \ p). On the other hand, the integer a is a quadratic nonresidue modulo p if and only if \displaystyle a^{(p-1)/2} \equiv -1 \ (\text{mod} \ p).

According to Euler’s Criterion, the task of checking for the status of quadratic residue is a matter of performing a modular exponentiation. This can be done using software or a calculator for modular arithmetic. If so desired, the exponentiation can also be programmed using the fast powering algorithm.

Though Euler’s Criterion (with a calculator for modular arithmetic) is a sure fire way for checking the status of quadratic residues, the law of quadratic reciprocity can simplify the task even further. As the examples below will show, checking the status of quadratic residues using the law of reciprocity may require no modular exponentiation at all and if exponentiation is required, it is of a much smaller size.

Euler’s Criterion also gives us several basic facts about quadratic residues.

Theorem 2
Let p be an odd prime. The following properties are true:

  • If a and b are both residues modulo p, then the product a \times b is a residue modulo p.
  • If If a and b are both nonresidues modulo p, then the product a \times b is a residue modulo p.
  • If a and b are such that one of them is a residue modulo p and the other is a nonresidue modulo p, then the product a \times b is a nonresidue modulo p.

Theorem 2 says that the product of two integers of the same types (both residues or both nonresidues) is always a residue modulo the odd prime p. The product of two integers of different types is always a nonresidue modulo the odd prime p. The theorem follows from Euler’s criterion and from the fact that (ab)^{(p-1)/2}=a^{(p-1)/2} \times b^{(p-1)/2}.

In arithmetic modulo a prime p, there exists a primitive root modulo p and that any primitive root generates by powering all the integers that are relatively prime to the modulus p. Let g be a primitive root modulo an odd prime p. It then follows that the quadratic residues modulo p are the even powers of g and the nonresidues are the odd powers of g. A related fact is that when p is an odd prime and when a and p are relatively prime, the equation x^2 \equiv a \ (\text{mod} \ p) either has two solutions or has no solutions.

Theorem 3
Let g be a primitive root modulo an odd prime p. For any a that is relatively prime to p, the following is true:

  • a is a quadratic residue modulo p if and only if a is of the form a \equiv g^{2k} \ (\text{mod} \ p) for some positive integer k,
  • a is a quadratic nonresidue modulo p if and only if a is of the form a \equiv g^{2k+1} \ (\text{mod} \ p) for some positive integer k.
  • (proved here)

Theorem 4
Let p be an odd prime. For any a that is relatively prime to p, the equation x^2 \equiv a \ (\text{mod} \ p) either has two solutions or has no solutions (proved here).

____________________________________________________________________________

Legendre Symbol

The law of quadratic reciprocity is stated using the Legendre symbol. For an odd prime p and for an integer a that is relatively prime to p, the symbol \displaystyle \biggl(\frac{a}{p}\biggr) is defined as follows:

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

One obvious and important observation is that Euler’s Criterion can be restated as follows:

Theorem 1a (Euler’s Criterion)
Let p be an odd prime. Let a be an integer that is relatively prime to p. Then \displaystyle \biggl(\frac{a}{p}\biggr) \equiv \displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p).

In the above definition, the lower argument of the Legendre symbol is always an odd prime and the upper argument is an integer that is relatively prime to the lower argument. To smooth out some statements involving the Legendre symbol and to make it easier to define the Jacobi symbol in the next post, we relax the Legendre symbol by making \displaystyle \biggl(\frac{a}{p}\biggr)=0 whenever a and p are not relatively prime, i.e. a \equiv 0 \ (\text{mod} \ p). The Legendre symbol can be broaden slightly by the following:

    \displaystyle  \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl}           0 &\ \text{if } a \equiv 0 \ (\text{mod} \ p) \\           1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a  \text{ is a quadratic residue modulo }p\\          -1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a  \text{ is a quadratic nonresidue modulo }p \end{array} \right.

Here’s some useful basic facts about the Legendre symbol.

Theorem 5
Let p be an odd prime. The following properties hold:

  • The Legendre symbol is periodic with respect to the top argument, i.e. if a \equiv b \ (\text{mod} \ p), then \displaystyle \biggl(\frac{a}{p}\biggr)=\biggl(\frac{b}{p}\biggr).
  • The Legendre symbol is multiplicative with respect to the top argument, i.e. \displaystyle \biggl(\frac{ab}{p}\biggr)=\biggl(\frac{a}{p}\biggr) \times \biggl(\frac{b}{p}\biggr).
  • If a \equiv 0 \ (\text{mod} \ p), then \displaystyle  \biggl(\frac{a^2}{p}\biggr)=0. If a \not \equiv 0 \ (\text{mod} \ p), then \displaystyle  \biggl(\frac{a^2}{p}\biggr)=1.

The first bullet point in Theorem 5 is easily verified based on the definition of the Legendre symbol. For the case a \equiv 0 \ (\text{mod} \ p), the other facts in Theorem 5 are easily verified. For the case a \not \equiv 0 \ (\text{mod} \ p), the second bullet point follows from Theorem 2, i.e. the fact that the product of two residues and the product of two nonresidues are both residues modulo an odd prime and that the product of a residue and a nonresidue is a nonresidue modulo an odd prime. The second part of the third bullet point is true since any integer that is a square is a quadratic residue.

____________________________________________________________________________

Law of Quadratic Reciprocity

The law of reciprocity can ease the calculation of the Legendre symbol when both the upper and lower arguments are distinct odd primes. Theorem 6 is the law of reciprocity and Theorem 7 and Theorem 8 are two supplements to the law that can round out the calculation. After stating the theorems, we demonstrate with some examples.

Theorem 6 (the law of quadratic reciprocity)

    Let p and q be two distinct odd prime numbers. Both of the following statements hold.

      \displaystyle  \biggl(\frac{q}{p}\biggr) \displaystyle \biggl(\frac{p}{q}\biggr)=(-1)^{(p-1)/2 \times (q-1)/2}

      Equivalently and more explicitly,

      \displaystyle  \biggl(\frac{q}{p}\biggr) = \left\{ \begin{array}{rl}                      \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{array} \right.

Theorem 7 (first supplement to the law of quadratic reciprocity)

    Let p be an odd prime number. The following statement holds.

      \displaystyle  \biggl(\frac{-1}{p}\biggr) = (-1)^{(p-1)/2} = \left\{ \begin{array}{rl}                      1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 4)\\          -1 &\ \text{if } p \equiv 3 \ (\text{mod} \ 4) \end{array} \right.

Theorem 8 (second supplement to the law of quadratic reciprocity)

    Let p be an odd prime number. The following statement holds.

      \displaystyle  \biggl(\frac{2}{p}\biggr) =(-1)^{(p^2-1)/8}= \left\{ \begin{array}{rl}                      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{array} \right.

Theorem 6 shows how to flip the Legendre symbol if both the upper and lower arguments are distinct odd primes. As long as one of the primes is congruent to 1 modulo 4, we can safely flip the symbol. If both primes are not congruent to 1 modulo 4, we can still flip the symbol except that we have to attach a minus sign. Theorem 7 (the first supplement) indicates when -1 (or p-1) is a quadratic residue an odd prime p. In words, -1 is a residue modulo p if dividing p by 4 gives the remainder of 1. Otherwise -1 is a nonresidue modulo p. Theorem 8 (the second supplement) indicates when 2 is a residue modulo an odd prime p. In words, 2 is a residue modulo p if dividing p by 8 leaves a remainder of 1 or 7. Otherwise 2 is a nonresidue modulo p.

____________________________________________________________________________

Examples

Example 1
Evaluate \displaystyle  \biggl(\frac{1783}{7523}\biggr), an example where both the upper and lower arguments in the Legendre symbol are primes.

    \displaystyle \begin{aligned} \biggl(\frac{1783}{7523}\biggr)&=-\biggl(\frac{7523}{1783}\biggr) \\&=-\biggl(\frac{391}{1783}\biggr) \\&=-\biggl(\frac{17}{1783}\biggr) \times \biggl(\frac{23}{1783}\biggr) \\&=-\biggl(\frac{1783}{17}\biggr) \times (-1) \biggl(\frac{1783}{23}\biggr) \\&=\biggl(\frac{15}{17}\biggr) \times \biggl(\frac{12}{23}\biggr) \\&=\biggl(\frac{3}{17}\biggr) \times \biggl(\frac{5}{17}\biggr) \times \biggl(\frac{2}{23}\biggr)^2 \times \biggl(\frac{3}{23}\biggr) \\&=\biggl(\frac{17}{3}\biggr) \times \biggl(\frac{17}{5}\biggr) \times \biggl(1\biggr)^2 \times (-1)\biggl(\frac{23}{3}\biggr) \\&=-\biggl(\frac{2}{3}\biggr) \times \biggl(\frac{2}{5}\biggr) \times  \biggl(\frac{2}{3}\biggr) \\&=-\biggl(\frac{2}{5}\biggr) \\&=-(-1) \\&=1 \end{aligned}

The above derivation is a repeated use of Theorems 5, 6 and 8. The idea is to flip the Legendre symbols to make the lower arguments smaller. Then reduce the upper arguments and then factor the upper arguments. Then flip again until reaching a Legendre symbol of \displaystyle \biggl(\frac{2}{5}\biggr), which is easy to solve.

It then follows that 1783 is a quadratic residue modulo the odd prime 7523. The answer can be confirmed by using Euler’s Criterion. Note that 1783^{3761} \equiv 1 \ (\text{mod} \ 7523). \square

Example 2
Evaluate \displaystyle  \biggl(\frac{a}{p}\biggr) where p= 1298351, an odd prime and a= 756479.

The number a is not a prime and is factored as a=353 \times 2143. We have the following derivation.

    \displaystyle \begin{aligned} \biggl(\frac{756479}{1298351}\biggr)&=\biggl(\frac{353}{1298351}\biggr) \times \biggl(\frac{2143}{1298351}\biggr) \\&=\biggl(\frac{1298351}{353}\biggr) \times (-1)\biggl(\frac{1298351}{2143}\biggr) \\&=-\biggl(\frac{17}{353}\biggr) \times \biggl(\frac{1836}{2143}\biggr) \\&=-\biggl(\frac{17}{353}\biggr) \times \biggl(\frac{2}{2143}\biggr)^2 \times \biggl(\frac{3}{2143}\biggr)^3 \times \biggl(\frac{17}{2143}\biggr)  \\&=-\biggl(\frac{353}{17}\biggr) \times \biggl(1\biggr)^2 \times (-1) \biggl(\frac{2143}{3}\biggr)^3 \times \biggl(\frac{2143}{17}\biggr) \\&=\biggl(\frac{13}{17}\biggr) \times  \biggl(\frac{1}{3}\biggr)^3 \times \biggl(\frac{1}{17}\biggr) \\&=\biggl(\frac{17}{13}\biggr) \times  \biggl(1\biggr)^3 \times \biggl(1\biggr) \\&=\biggl(\frac{4}{13}\biggr) \\&=1 \end{aligned}

The evaluation of the Legendre symbols in this example does not start with a flipping since the upper argument 756479 is not a prime. Instead, we start with factoring the upper argument into prime factors and then proceed with a series of flipping, reducing and factoring. \square

Example 3
Evaluate \displaystyle  \biggl(\frac{a}{p}\biggr) where p= 569, an odd prime and a= 1610280.

    \displaystyle \begin{aligned} \biggl(\frac{1610280}{569}\biggr)&=\biggl(\frac{3}{569}\biggr)^4 \times \biggl(\frac{5}{569}\biggr) \times \biggl(\frac{7}{569}\biggr) \times \biggl(\frac{568}{569}\biggr) \\&= \biggl(\frac{569}{3}\biggr)^4 \times \biggl(\frac{569}{5}\biggr) \times \biggl(\frac{569}{7}\biggr) \times \biggl(\frac{-1}{569}\biggr) \\&= \biggl(\frac{2}{3}\biggr)^4 \times \biggl(\frac{4}{5}\biggr) \times \biggl(\frac{2}{7}\biggr) \times \biggl(1\biggr) \\&= \biggl(-1\biggr)^4 \times \biggl(1\biggr) \times \biggl(1\biggr) \\&=1 \end{aligned}

This example can also be evaluated by first reducing 1610280 modulo 569. \square

____________________________________________________________________________

Comment

The law of quadratic reciprocity is a deep and powerful result. It guides the evaluation of Legendre symbols in an attempt to answer whether a number is a quadratic residue modulo an odd prime. The law of reciprocity as represented above requires that the lower argument in the Legendre symbol is an odd prime. When the upper argument is an odd number that is not a prime, there is no way to flip it (based on the law of reciprocity using the Legendre symbol). In Example 2, the evaluation of the Legendre symbol cannot begin until the top argument is factored. The factoring in Example 2 is possible since the number is small. When the number is large, factoring may not always be feasible. It turns out that the Legendre symbol has a generalization, called the Jacobi symbol, that is even more versatile and is defined in the next post.

____________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

Quadratic Residues

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

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.

    Theorem 5 (Quadratic Reciprocity)

      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

Euler’s Criterion

In this post we discuss a beautiful connection between Fermat’s little theorem and the solvability of a quadratic congruence equation. The discussion leads to a theorem that is commonly called Euler’s Criterion.

___________________________________________________________________________________________________________________

The Setting

Let p be an odd prime number. Let a be a positive integer that is relative prime to p. According to Fermat’s little theorem, we have \displaystyle a^{p-1} \equiv 1 \ (\text{mod} \ p), which can be written as \displaystyle (a^{\frac{p-1}{2}})^2 \equiv 1 \ (\text{mod} \ p). So the number \displaystyle a^{\frac{p-1}{2}} represent solutions to the equation y^2 \equiv 1 \ (\text{mod} \ p). It can be shown that the equation y^2 \equiv 1 \ (\text{mod} \ p) has exactly two solutions. The number \displaystyle a^{\frac{p-1}{2}} has two possibilities. They are:

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

The result we wish to highlight is that each of the above two cases corresponds to either the solvability or non-solvability of the following quadratic congruence equation.

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

___________________________________________________________________________________________________________________

Euler’s Criterion

The result indicated at the end of the preceding section is known as Euler’s Criterion. We have the following theorem.

    Theorem 1 (Euler’s Criterion)

    Let p be an odd prime number. Let a be a positive integer that is relative prime to p.

      1. The equation x^2 \equiv a \ (\text{mod} \ p) has solutions if and only if \displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p).
      2. \text{ }

      3. The equation x^2 \equiv a \ (\text{mod} \ p) has no solutions if and only if \displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p).

Examples
Take x^2 \equiv 899 \ (\text{mod} \ 50261) as an example. To determine whether this equation is solvable, we can check each integer in the interval 1 \le x <50261. Euler's Criterion reduces the solvability question to a modular exponential problem. It can be shown that \displaystyle 899^{\frac{50261-1}{2}}=899^{25130} \equiv 1 \ (\text{mod} \ p). Thus x^2 \equiv 899 \ (\text{mod} \ 50261) has solutions.

On the other hand, the equation x^2 \equiv 13961 \ (\text{mod} \ 50261) has no solutions since \displaystyle 13961^{25130} \equiv -1 \ (\text{mod} \ p).

Proof of Theorem 1
We prove the first bullet point. The two bullet points in Theorem 1 are equivalent. We need only prove one of them.

\Longrightarrow
Suppose that x^2 \equiv a \ (\text{mod} \ p) has solutions. Let x=t be one solution. Then we have t^2 \equiv a \ (\text{mod} \ p). The following derivation establishes the direction of \Longrightarrow.

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

Applying Fermat’s little theorem, which gives t^{p-1} \equiv 1 \ (\text{mod} \ p) (giving the last congruence in the above derivation). To apply Fermat’s theorem, we need to show that p \not \lvert \ t. Suppose that p \ \lvert \ t. Then p \ \lvert \ t^2 and t^2 \equiv 0 \ (\text{mod} \ p). It follows that a \equiv 0 \ (\text{mod} \ p), contradicting the fact that a is relatively prime to the modulus p.

\Longleftarrow
Suppose that x^2 \equiv a \ (\text{mod} \ p) has no solutions. we make the following claim.

    For each number h \in \left\{1,2,\cdots,p-1 \right\}, there exists a number k \in \left\{1,2,\cdots,p-1 \right\} with h \ne k such that hk=a.

To prove the above claim, let k=h^{-1}a. It is clear that hk=a. It remains to be shown that h \ne k. Suppose that h=h^{-1}a. Then h^2=a, implying that x^2 \equiv a \ (\text{mod} \ p) has a solution. Thus h \ne k.

It follows from the claim that the set \left\{1,2,\cdots,p-1 \right\} consists of \displaystyle \frac{p-1}{2} many pairs of numbers, each with product a. So we have the following:

    \displaystyle 1 \cdot 2 \cdots p-1 \equiv a^{\frac{p-1}{2}} \ (\text{mod} \ p)

According to Wilson’s theorem, \displaystyle 1 \cdot 2 \cdots p-1 \equiv -1 \ (\text{mod} \ p). Consequently, \displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p).

We have shown that if the equation x^2 \equiv a \ (\text{mod} \ p) has no solutions, then \displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p). Equivalently if \displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p), then the equation x^2 \equiv a \ (\text{mod} \ p) has solutions. \blacksquare

___________________________________________________________________________________________________________________

Quadratic Residue

The statement that the equation x^2 \equiv a \ (\text{mod} \ p) has solutions is commonly described by the term quadratic residue. We say that the number a is a quadratic reside modulo p if the equation x^2 \equiv a \ (\text{mod} \ p) has solutions. If the number a is not a quadratic reside modulo p, we say that it is a quadratic nonresidue modulo p. Whenever there is no need to make a distinction between quadratic and higher power, we will just omit the word quadratic and refer to residues and nonresidues.

Euler’s Criterion can be restated using the term quadratic residues.

    Theorem 1 (Euler’s Criterion)

    Let p be an odd prime number. Let a be a positive integer that is relative prime to p.

      1. The number a is a quadratic residue modulo p if and only if \displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p).
      2. \text{ }

      3. The number a is a quadratic nonresidue modulo p if and only if \displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p).

___________________________________________________________________________________________________________________

Legendre Symbol

For those who like to be economical in the statements of mathematical results, the Legendre symbol can be used. The Legendre symbol \displaystyle \biggl(\frac{a}{p}\biggr) 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.

Euler’s Criterion can be restated as follows:

    Theorem 1 (Euler’s Criterion)

    Let p be an odd prime number. Let a be a positive integer that is relative prime to p. Then the following property holds.

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

    ___________________________________________________________________________________________________________________

    \copyright \ 2013 \text{ by Dan Ma}