More about checking for primitive roots

Finding primitive roots modulo a number is of great interest in number theory, both in a theoretical standpoint and in a computational standpoint. In this post we compare and contrast three different ways of checking for primitive roots, continuing a discussion in an earlier post An elementary algorithm for finding primitive roots.

___________________________________________________________________________________________________________________

Background

Let m be a positive integer. Let a be a positive integer that is relative prime to m. Let \phi be Euler’s phi function, which counts the number of least residues that are relatively prime to the modulus. For example, \phi(6)=2 as 1 and 5 are the only numbers relatively prime to 6 (out of the numbers 0,1,2,3,4,5). Furthermore, \phi(p)=p-1 for any prime number p. Previous posts on the phi function: Euler’s phi function, part 1 and Euler’s phi function, part 2.

Euler’s theorem tells us that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m). By the order of a modulo m we mean the least positive exponent k such that a^{k} \equiv 1 \ (\text{mod} \ m) (Euler’s theorem indicates that this notion of order is well defined). The number a is said to be a primitive root modulo m if the order of a modulo m is \phi(m).

___________________________________________________________________________________________________________________

Three Checks

Let m be a positive integer. Let a be a positive integer that is relative prime to m. How can we determine whether the number a is a primitive root modulo m? We discuss three ways of answering this question.

    ____________________________________________________________________________________________
    Check # 1

      Check a^j \ (\text{mod} \ m) for all positive integers j<\phi(m).

      If each such congruence \not \equiv 1, then the number a is a primitive root modulo m.

    ____________________________________________________________________________________________

Check # 1 is merely a restatement of the definition of primitive root. It is a dumb test as it requires too much calculation. For large moduli, it would be an inefficient method of checking for primitive roots. The following is a much better test.

    ____________________________________________________________________________________________
    Check # 2

      Check a^j \ (\text{mod} \ m) for all positive divisors j of \phi(m) with j<\phi(m).

      If each such congruence \not \equiv 1, then the number a is a primitive root modulo m.

    ____________________________________________________________________________________________

Check # 2 narrows down the checking by quite a bit – simply checking a^j among the divisors of \phi(m). This works because the only possible numbers for the order modulo m of the number a are the divisors of \phi(m). So we can skip all j that are not divisors of \phi(m). The following lemma shows why this is so. Actually, the lemma proves something more general. It shows that if a^n \equiv 1 \ (\text{mod} \ m), then the order of a must be a divisor of n. Euler’s theorem says that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m). So the order of a must be a divisor of \phi(m).

    Lemma 1

      Let k be the order of a modulo m. If a^n \equiv 1 \ (\text{mod} \ m), then k \ \lvert \ n.

Proof of Lemma 1
We have k \le n since k is least with the property a^k \equiv 1 \ (\text{mod} \ m). By the division algorithm, we have n=q \cdot k+r where q is some integer and 0 \le r <k. We have the following:

    1 \equiv a^{n} \equiv a^{q \cdot k+r} \equiv (a^k)^q \cdot a^r \equiv a^r \ (\text{mod} \ m)

With a^r \equiv 1 \ (\text{mod} \ m) and r < k, it follows that r=0 and n=q \cdot k. Thus k is a divisor of n. \blacksquare

Though Check # 2 is definitely an improvement over Check # 1, the following further narrows the list of exponents to check.

    ____________________________________________________________________________________________
    Check # 3

      Find all prime divisors q of \phi(m). Then compute \displaystyle j=\frac{\phi(m)}{q} over all q.

      Check a^j \ (\text{mod} \ m) for all j calculated above.

      If each such congruence \not \equiv 1, then the number a is a primitive root modulo m.

    ____________________________________________________________________________________________

Check # 3 further eliminates the exponents to try when we check a^j \ (\text{mod} \ m). Instead of checking over all the divisors of \phi(m), we only need to try the divisors of the form \displaystyle \frac{\phi(m)}{q} where q is a prime divisor of \phi(m). The following lemma shows why this works.

    Lemma 2

      The number a is a primitive root modulo m if and only if \displaystyle a^{\frac{\phi(m)}{q}} \not \equiv 1 \ (\text{mod} \ m) for all prime divisors q of \phi(m).

Proof of Lemma 2
The direction \Longrightarrow is clear.

To show \Longleftarrow, suppose a is not a primitive root modulo m. Then
\displaystyle a^{t} \equiv 1 \ (\text{mod} \ m) for some t that is a divisor of \phi(m). We have \phi(m)=t \cdot y for some integer y. Let q be a prime factor of y. Then \phi(m)=t \cdot q \cdot b for some integer b. Consider the following derivation.

    \displaystyle 1 \equiv (a^t)^b =(a^{\frac{\phi(m)}{qb}})^b \equiv a^{\frac{\phi(m)}{q}} \ (\text{mod} \ m)

Thus if \displaystyle a^{\frac{\phi(m)}{q}} \not \equiv 1 \ (\text{mod} \ m) for all prime divisors q of \phi(m), then a must be a primitive root modulo m. \blacksquare

___________________________________________________________________________________________________________________

Examples

We now work some examples using Check # 3. The modular arithmetic is done using an online calculator. It can also be done using the fast powering algorithm (discussed in the post Congruence Arithmetic and Fast Powering Algorithm).

Example 1
Consider m=37. Find all primitive roots modulo m=37.

First \phi(37)=36. The divisors of 36 are:

    1,2,3,4,6,9,12,18,36

To use Check # 2, in order to find out if a is a primitive root, we would need to calculate a^j nine times, one for each of the above divisors of \phi(37)=36.

To use Check # 3, only two of these nine divisors are needed. There are two prime divisors of 36, namely 2 and 3. We use \displaystyle \frac{36}{2}=18 and \displaystyle \frac{36}{3}=12. So we check a^{12} and a^{18} modulo 37. The calculation is presented in the following tables.

    \displaystyle \begin{bmatrix} a&\text{ }&a^{12}&\text{ }&a^{18}  \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1&\text{ }&1  \\ 2&\text{ }&26&\text{ }&36  \\ 3&\text{ }&10&\text{ }&1  \\ 4&\text{ }&10&\text{ }&1  \\ 5&\text{ }&10&\text{ }&36  \\ 6&\text{ }&1&\text{ }&36 \\ 7&\text{ }&10&\text{ }&1 \\ 8&\text{ }&1&\text{ }&36 \\ 9&\text{ }&26&\text{ }&1 \\ 10&\text{ }&1&\text{ }&1   \end{bmatrix} \ \ \ \ \ \displaystyle \begin{bmatrix} a&\text{ }&a^{12}&\text{ }&a^{18}  \\\text{ }&\text{ }&\text{ } \\ 11&\text{ }&1&\text{ }&1  \\ 12&\text{ }&26&\text{ }&1  \\ 13&\text{ }&10&\text{ }&36  \\ 14&\text{ }&1&\text{ }&36  \\ 15&\text{ }&26&\text{ }&36  \\ 16&\text{ }&26&\text{ }&1 \\ 17&\text{ }&26&\text{ }&36 \\ 18&\text{ }&10&\text{ }&36 \\ 19&\text{ }&10&\text{ }&36 \\ 20&\text{ }&26&\text{ }&36   \end{bmatrix}

    \displaystyle \begin{bmatrix} a&\text{ }&a^{12}&\text{ }&a^{18}  \\\text{ }&\text{ }&\text{ } \\ 21&\text{ }&26&\text{ }&1  \\ 22&\text{ }&26&\text{ }&36  \\ 23&\text{ }&1&\text{ }&36  \\ 24&\text{ }&10&\text{ }&36  \\ 25&\text{ }&26&\text{ }&1  \\ 26&\text{ }&1&\text{ }&1 \\ 27&\text{ }&1&\text{ }&1 \\ 28&\text{ }&26&\text{ }&1 \\ 29&\text{ }&1&\text{ }&36 \\ 30&\text{ }&10&\text{ }&1   \end{bmatrix} \ \ \ \ \ \displaystyle \begin{bmatrix} a&\text{ }&a^{12}&\text{ }&a^{18}  \\\text{ }&\text{ }&\text{ } \\ 31&\text{ }&1&\text{ }&36  \\ 32&\text{ }&10&\text{ }&36  \\ 33&\text{ }&10&\text{ }&1  \\ 34&\text{ }&10&\text{ }&1  \\ 35&\text{ }&26&\text{ }&36  \\ 36&\text{ }&1&\text{ }&1 \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ }  \end{bmatrix}

The primitive roots are the rows with both congruences \not \equiv 1. They are:

    2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35

One comment about the above tables. The non-one values in the above table seem to follow a pattern. In the columns for the calculation for a^{18}, the values are either 1 or 36. The non-one value is 36. It turns out that it has order 2 modulo 37. The non-one values in the columns for a^{12} are 10 and 26. It turns out that they have order 3 modulo 37. See the exercise stated below.

Example 2
Consider m=17. Find all primitive roots modulo m=17.

Since \phi(17)=16=2^4, the only prime divisor of $latex \phi(17) is 2. We use \displaystyle \frac{16}{2}=8. For any a, we only need to calculate a^8.

    \displaystyle \begin{bmatrix} a&\text{ }&a^{8}&\text{ }&a&\text{ }&a^{8}  \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1&\text{ }&11&\text{ }&16  \\ 2&\text{ }&1&\text{ }&12&\text{ }&16  \\ 3&\text{ }&16&\text{ }&13&\text{ }&1  \\ 4&\text{ }&1&\text{ }&14&\text{ }&16  \\ 5&\text{ }&16&\text{ }&15&\text{ }&1  \\ 6&\text{ }&16&\text{ }&16&\text{ }&1 \\ 7&\text{ }&16&\text{ }&\text{ } \\ 8&\text{ }&1&\text{ }&\text{ } \\ 9&\text{ }&1&\text{ }&\text{ } \\ 10&\text{ }&16&\text{ }&\text{ }     \end{bmatrix}

The primitive roots modulo 17 are:

    3, 5, 6, 7, 10, 11, 12, 14

Note that the non-one value 16 in the above table has order 2 modulo 17. See the exercise below.

___________________________________________________________________________________________________________________

Special Case

Based on Example 2, the following is a special case for Check # 3.

    ____________________________________________________________________________________________
    Check # 3 (A Special Case)

      Let p be a prime such that p-1=2^n for some positive integer n.

      Note that 2 is the only prime divisor of \phi(p)=p-1.

      Check a^j \ (\text{mod} \ p) where \displaystyle j=\frac{p-1}{2}.

      If a^j \not \equiv 1, then the number a is a primitive root modulo p.

    ____________________________________________________________________________________________

___________________________________________________________________________________________________________________

Exercise

This is the exercise mentioned at the end of Example 1.

Let p be a prime number. Let q be a prime divisor of p-1. Let a be an integer with 1 \le a \le p-1. Show that the number \displaystyle a^{\frac{p-1}{q}} is either \equiv 1 or has order q modulo p.

___________________________________________________________________________________________________________________

\copyright \ 2013 \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

Solving Quadratic Congruences

This post is an introductory discussion on the congruence equations of the form x^2 \equiv a \ (\text{mod} \ p) where the modulus p is an odd prime and the number a is relatively prime to p. A discussion on the related notion of quadratic residues is found here. Specific algorithms for solving quadratic congruence eqautions with odd prime moduli are discussed in this subsequent post.

____________________________________________________________________________

Simple Example

We start off with a simple example. Calculate x^2 modulo m=11 for x=0,1,2,\cdots,10.

    0^2 \equiv 0 \ (\text{mod} \ 11)

    1^2 \equiv 1 \ (\text{mod} \ 11)

    2^2 \equiv 4 \ (\text{mod} \ 11)

    3^2 \equiv 9 \ (\text{mod} \ 11)

    4^2 \equiv 5 \ (\text{mod} \ 11)

    5^2 \equiv 3 \ (\text{mod} \ 11)

    6^2 \equiv 3 \ (\text{mod} \ 11)

    7^2 \equiv 5 \ (\text{mod} \ 11)

    8^2 \equiv 9 \ (\text{mod} \ 11)

    9^2 \equiv 4 \ (\text{mod} \ 11)

    10^2 \equiv 1 \ (\text{mod} \ 11)

The above calculation shows that the values of x^2 modulo m=11 can only be 1,3,4,5,9. So equations such as x^2 \equiv a \ (\text{mod} \ 11) for a=1,3,4,5,9 have solutions. For example, the solutions for the equation x^2 \equiv 5 \ (\text{mod} \ 11) are x=4 and x=7.

On the other hand, the equations x^2 \equiv b \ (\text{mod} \ 11) for b=2,6,7,8,10 have no solutions.

Also note that whenever a \ne 0 and the equation x^2 \equiv a \ (\text{mod} \ 11) has a solution, the solutions come in pairs.

____________________________________________________________________________

Quadratic Congruences

Let m be an odd prime number. Let a be an integer that is not divisible by p (equivalently relatively prime to p). The object of interest here is the quadratic congruence equation x^2 \equiv a \ (\text{mod} \ p). It turns out that each such equation has exactly two solutions whenever the number a and the modulus p are relatively prime (as demonstrated in the above simple example). The following lemma and corollary confirm what we see in the above example.

    Lemma 1

      Let p be an odd prime number. Let a be an integer that is not divisible by p. Then the equation

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

      has no solutions or exactly two solutions.

Proof of Lemma 1
If equation (1) has no solutions, then we are done. Suppose it has at least one solution, say x=r. We have r^2 \equiv a \ (\text{mod} \ p). It follows that x=-r \equiv p-r \ (\text{mod} \ p) is a solution of equation (1) too.

We claim x=r and x=p-r are distinct modulo p. To see this, suppose p-r \equiv r \ (\text{mod} \ p). Then p \ \lvert \ (p-2r). Because p is an odd prime, p \not \lvert \ 2. So p \ \lvert \ r. This implies that p \ \lvert \ r^2. Because p \ \lvert \ (r^2-a), p \ \lvert \ a, contradicting the assumption that p \not \lvert \ a. Thus p-r \not \equiv r \ (\text{mod} \ p), demonstrating that equation (1) has at least two solutions.

It remains to be shown that any solution of equation (1) must be congruent to one of x=r and x=p-r. Suppose t^2 \equiv a \ (\text{mod} \ p). Then t^2 \equiv r^2 \ (\text{mod} \ p). It follows that p \ \lvert \ (t-r)(t+r). Thus p must divide one of the two factors (Euclid’s lemma). The case p \ \lvert \ (t-r) implies t \equiv r \ (\text{mod} \ p). The case p \ \lvert \ (t+r) implies t \equiv -r \ (\text{mod} \ p). \blacksquare

    Corollary 2

      Let p be an odd prime number. The equation x^2 \equiv a \ (\text{mod} \ p) has exactly two solutions for \displaystyle \frac{p-1}{2} many numbers a \in \left\{1,2,\cdots,p-1 \right\} and has no solutions for the other \displaystyle \frac{p-1}{2} numbers a \in \left\{1,2,\cdots,p-1 \right\}.

Remark
For the even prime p=2, the equation x^2 \equiv a \ (\text{mod} \ 2) is not an interesting one. For x^2 \equiv 0 \ (\text{mod} \ 2), x=0 is the only solution. For x^2 \equiv 1 \ (\text{mod} \ 2), x=1 is the only solution.

For composite moduli, the quadratic equation x^2 \equiv a \ (\text{mod} \ m) can have more than two solutions. For example, x^2 \equiv 1 \ (\text{mod} \ 8) has four solutions x=1,3,5,7.

For these reasons, we only work with odd prime moduli for quadratic congruences.

____________________________________________________________________________

General Case

What about the general case of the quadratic congruence equation of the following form?

    \alpha y^2+\beta y+\gamma \equiv 0 \ (\text{mod} \ p)  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

Of course, we only consider the equations where \alpha \not \equiv 0 \ (\text{mod} \ p) and p is an odd prime. It turns out that equation (2) can be replaced by an equivalent congruence equation of the same form as equation (1) above. So the general case of equation (2) presents no new problem. We just convert equation (2) to its equivalence and solve it accordingly. We now discuss how this is done.

The coefficient \alpha, the coefficient of the y^2 term, has a multiplicative inverse modulo p. So multiplying equation (2) by \alpha^{-1} gives the following equation.

    y^2+\alpha^{-1} \beta y+\alpha^{-1} \gamma \equiv 0 \ (\text{mod} \ p)  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

So we can now focus on solving equation (3), which has the same solutions as equation (2). Consider the coefficient of the y term. If the coefficient \alpha^{-1} \beta is even, we can complete the square and obtain an equivalent equation of the same form as equation (1). If the coefficient \alpha^{-1} \beta is odd, then we can add p to it and obtain an even coefficient. We can then proceed to complete the square as in the even case. We demonstrate with two examples.

Consider the equation 3 y^2+4y+1 \equiv 0 \ (\text{mod} \ 11). Since 4 \cdot 3 \equiv 1 \ (\text{mod} \ 11). The multiplicative inverse of 4 is 3. So we multiply 4 across and obtain y^2+16y+4 \equiv 0 \ (\text{mod} \ 11). The coefficient of the y term is even. We complete the square as follows.

    y^2+16y+4 \equiv 0 \ (\text{mod} \ 11)

    y^2+16y+64 \equiv 64-4 \ (\text{mod} \ 11)

    (y+8)^2 \equiv 60 \ (\text{mod} \ 11)

    (y+8)^2 \equiv 5 \ (\text{mod} \ 11)

The last equation in the above derivation is of the form x^2 \equiv 5 \ (\text{mod} \ 11) where the solutions are x=4 and x=7. Thus we have y+8 \equiv 4 \ (\text{mod} \ 11) and y+8 \equiv 7 \ (\text{mod} \ 11). These two congruences give y \equiv 7 \ (\text{mod} \ 11) and y \equiv 10 \ (\text{mod} \ 11).

For the odd case, consider the equation 5 y^2+y+8 \equiv 0 \ (\text{mod} \ 11). The multiplicative inverse of 5 is 9 as 5 \cdot 9 \equiv 1 \ (\text{mod} \ 11). After multiplying by the inverse, we obtain y^2+9y+72 \equiv 0 \ (\text{mod} \ 11). We further reduce 72 modulo 11 to get y^2+9y+6 \equiv 0 \ (\text{mod} \ 11). Note that the coefficient of the y term is odd. So we add modulus to that coefficient to obtain the equation y^2+20y+6 \equiv 0 \ (\text{mod} \ 11). We then proceed to complete the square as follows.

    y^2+20y+100 \equiv 100-6 \ (\text{mod} \ 11)

    (y+10)^2 \equiv 94 \ (\text{mod} \ 11)

    (y+10)^2 \equiv 6 \ (\text{mod} \ 11)

The last equation in the above derivation is of the form x^2 \equiv 6 \ (\text{mod} \ 11), which has no solutions (based on the simple example above). Thus the original equation 5 y^2+y+8 \equiv 0 \ (\text{mod} \ 11) has no solutions.

____________________________________________________________________________

Examples

To solve the quadratic congruence x^2 \equiv a \ (\text{mod} \ p), one way is to compute the entire table of values for x^2 modulo p. For very small prime such as the simple example above, this approach is workable. For large primes, this requires a lot of computational resources.

To further illustrate the quadratic congruences, we work three examples with help from Euler’s Criterion and from using Excel to do some of the calculations.

According to Euler’s Criterion, 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). Equivalently, 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). So the solvability of the quadratic congruence equation can be translated as a modular exponentiation calculation.

The computation for \displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p) can be done directly using an online modular arithmetic calculator or using the fast-powering algorithm (discussed in the post Congruence Arithmetic and Fast Powering Algorithm). For a discussion and a proof of Euler’s Criterion, see the post Euler’s Criterion.

When Euler’s Criterion indicates there are solutions, how do we find the solutions? We demonstrate using the following examples.

Example 1
Solve x^2 \equiv 5 \ (\text{mod} \ 61).

According to Euler’s Criterion, the equation x^2 \equiv 5 \ (\text{mod} \ 61) has solutions since 5^{30} \equiv 1 \ (\text{mod} \ 61). To find the solutions, we keep adding the modulus to a=5 until we get a perfect square.

    \displaystyle x^2 \equiv 5 \equiv 5+61 \equiv 5+2(61) \equiv \cdots \equiv 5+20(61)=1225=35^2 \ (\text{mod} \ 61)

So we have x^2 \equiv 35^2 \ (\text{mod} \ 61), which gives x=35 and x=-35. The solutions are x \equiv -35 \equiv 26 \ (\text{mod} \ 61) and x \equiv 35 \ (\text{mod} \ 61).

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

Since 899^{25130} \equiv 1 \ (\text{mod} \ 50261), the equation has solutions. We then add the modulus repeatedly to 899 until we get a perfect square (with the aid of an Excel spreadsheet).

    \displaystyle x^2 \equiv 899 \equiv 899+50261 \equiv 899+2(50261) \equiv \cdots \equiv 899+4297(50261)=215972416=14696^2 \ (\text{mod} \ 50261)

So we have x^2 \equiv 14696^2 \ (\text{mod} \ 50261), which gives x=14696 and x=-14696. The solutions are x \equiv 14696 \ (\text{mod} \ 50261) and x \equiv -14696 \equiv 35565 \ (\text{mod} \ 50261).

Example 3
Solve x^2 \equiv 13961 \ (\text{mod} \ 50261).

Since 13961^{25130} \equiv -1 \ (\text{mod} \ 50261), the equation has no solutions according to Euler’s Criterion.

____________________________________________________________________________

\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}