Solving quadratic congruences with odd prime moduli

The goal of this post is to show how to solve the quadratic congruence equation

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

where p is an odd prime and a is an integer that is relatively prime to p. When equation (1) has a solution, the number a is said to be a quadratic residue modulo p. Any solution of equation (1) is called a square root of a modulo p. When the equation has no solutions, the number a is said to be a quadratic nonresidue modulo p. For both theoretical and practical reasons, it is important to solve quadratic congruence equation (1) (or to find square roots modulo an odd prime). This post expands on the previous post called Solving Quadratic Congruences.

____________________________________________________________________________

Background

If the modulus p is small (prime or composite), then it is easy to solve equation (1). Simply square each element in the set \left\{1,2,\cdots,p-1 \right\} modulo p and look for the value a. We need a systematic method only when the modulus is large to the point that checking for solutions by squaring one number at a time cannot be done in a reasonable amount of time using modern supercomputers.

The moduli discussed here are prime numbers p. The case p=2 is easy to deal with. Thus in solving equations described in (1), the focus is on odd primes p and on integers a that are relatively prime to p.

In solving the quadratic congruence equation (1), for that matter any other type of equations, three natural questions arise: given an equation of the form in (1), how do I know if it has a solution? If it has a solution, how many solution does it have? How do I compute a solution of one exists? It turns out that for quadratic congruence equations with odd prime moduli as described in (1), there are clear and definite answers for all three questions.

There is an effective algorithm for checking whether a is a quadratic residue modulo p. The algorithm is to evaluate the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr) (see these two previous posts: Legendre symbol and Jacobi symbol). As for the second question (the number of solutions), the equation (1) either has no solutions or has exactly two solutions (see the post called Solving Quadratic Congruences). Thus for an odd prime p, exactly half of the elements in the set \mathbb{Z}_p^*=\left\{1,2,\cdots,p-1 \right\} are quadratic residues modulo p. In other words, modulo an odd prime p, there are (p-1)/2 many quadratic residues and (p-1)/2 many quadratic nonresidues. To answer the third question, we discuss algorithms that can be used to solve quadratic congruences with odd prime moduli.

Any odd prime is congruent to either 1 or 3 modulo 4. For odd prime p \equiv 3 \ (\text{mod} \ 4), there is an explicit formula that gives the solutions to equation (1). For odd prime p \equiv 1 \ (\text{mod} \ 4), no explicit formula exists. For the case of p \equiv 1 \ (\text{mod} \ 4), we demonstrate how to use the Tonelli-Shanks algorithm to iteratively find the solutions. We describe the algorithm and show how it works with some examples. We also present a proof of why the algorithm works.

The Tonelli-Shanks algorithm was invented in 1972 by Dan Shanks. He called it RESSOL (RESidues SOLver). The algorithm is very similar to one described much earlier by Tonelli, hence the name Tonelli-Shanks algorithm.

____________________________________________________________________________

Odd primes congruent to 3 modulo 4

Let’s take care of the easy case first, i.e. p \equiv 3 \ (\text{mod} \ 4). In this case, the solutions to equation (1) are given by \pm R where

    \displaystyle R \equiv a^{\frac{p+1}{4}} \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

To see that the R gives a solution to the equation (1), consider the following derivation:

    \displaystyle \begin{aligned} R^2&\equiv (a^{\frac{p+1}{4}})^2 \\&\equiv a^{\frac{p+1}{2}} \\&\equiv a \cdot a^{\frac{p-1}{2}} \\&\equiv a \cdot \biggl(\frac{a}{p}\biggr) \\&\equiv a \cdot 1  \\&\equiv a \ (\text{mod} \ p) \end{aligned}

On the surface, it appears that the above derivation works for all primes. Note that the exponent (p+1)/4 must be an integer. The assumption p \equiv 3 \ (\text{mod} \ 4) makes it an integer. Using Euler’s Criterion, the quantity \displaystyle a^{\frac{p-1}{2}} is replaced by the Lengendre symbol, which is a 1 since a is a quadratic residue modulo p.

As a quick example, let’s solve the equation x^2 \equiv 19 \ (\text{mod} \ 431). The prime 431 is congruent to 3 modulo 4. The number 19 is a quadratic residue modulo 431. One solution is given by 19^{432/4} \equiv 19^{108} \equiv 197 \ (\text{mod} \ 431). The other solution is given by 234 (= 431-197).

____________________________________________________________________________

Odd primes congruent to 1 modulo 4

The focus of the remainder of the post is on using the Tonelli-Shanks algorithm to solve the quadratic equation (1). We describe the algorithm in the next section and demonstrate with examples. To follow along the algorithm and the examples, it would be helpful to have a calculator (or a software package) that can handle modular exponentiation and the evaluation of Legendre symbol and Jacobi symbol. The algorithm also requires the finding of a quadratic nonresidue modulo the odd prime p. Obviously, we need to check that the number a is a quadratic residue modulo p. This can be done by evaluating the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr).

____________________________________________________________________________

Tonelli-Shanks Algorithm

Objective: to solve the equation x^2 \equiv a \ (\text{mod} \ p) where p is an odd prime satisfying p \equiv 1 \ (\text{mod} \ 4) and a is a quadratic residue modulo p, i.e. the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr)=1.

Steps:

  1. Factor out the largest power of 2 from the even integer p-1, i.e. obtain p-1=2^{S} \cdot Q where Q is odd.
  2. Find a positive integer y that is a quadratic nonresidue modulo p, i.e. find y such that \displaystyle  \biggl(\frac{y}{p}\biggr)=-1.
  3. Calculate the following four quantities:
    • \displaystyle R \equiv a^{\frac{Q+1}{2}} \ (\text{mod} \ p)
    • \displaystyle c \equiv y^Q \ (\text{mod} \ p)
    • \displaystyle t \equiv a^{Q} \ (\text{mod} \ p)
    • \displaystyle E=S
  4. Loop
    1. If \displaystyle t \equiv 1 \ (\text{mod} \ p), then the algorithm stops and output R and p-R, the two solutions of the equation. If \displaystyle t \not \equiv 1 \ (\text{mod} \ p), then perform the following two steps.
    2. Find the least i such that 0<i<E and such that \displaystyle t^{2^i} \equiv 1 \ (\text{mod} \ p).
    3. Calculate \displaystyle b \equiv c^{2^{E-i-1}} \ (\text{mod} \ p) and replace the quantities R, c, t and E as follows:
      • \displaystyle R \equiv Rb \ (\text{mod} \ p)
      • \displaystyle c \equiv b^2 \ (\text{mod} \ p)
      • \displaystyle t \equiv b^2 \cdot t \ (\text{mod} \ p)
      • \displaystyle E=i

      Go back to Step A.

The initial value of \displaystyle R \equiv a^{\frac{Q+1}{2}} is an initial estimate of the solution to the equation. The rest of the algorithm is to repeatedly refine this estimate to reach a solution. Note that Step 4-B is to determine the order of the number t. Each time a new value of t is calculated, the order of the new t is smaller than the order of the previous t. The goal is to reach a t of order 1, which means that the number t itself would be \equiv 1, at which point the estimate R becomes a solution. Let’s consider some examples.

____________________________________________________________________________

Examples

Example 1
Solve the equation x^2 \equiv 381 \ (\text{mod} \ 593).

The following shows the steps in carrying out the Tonelli-Shanks algorithm.

Step 1. S=4 and Q=37 since 592 = 16 x 37.

Step 2. y=3 is a quadratic nonresidue modulo 593.

Step 3. Calculate the following four quantities:

  • \displaystyle R \equiv 381^{\frac{37+1}{2}} \equiv 381^{19} \equiv 218 \ (\text{mod} \ 593)
  • \displaystyle c \equiv 3^{37} \equiv 384 \ (\text{mod} \ 593)
  • \displaystyle t \equiv 381^{37} \equiv 201 \ (\text{mod} \ 593)
  • \displaystyle E=4

_______________________________________
The above t is obviously t \not \equiv 1. We now find the least i, 0<i<E, such that t^{2^i} \equiv 1. In other words, repeatedly square t until reaching the value of 1. The result is i=3. Let b \equiv c^{2^{E-i-1}} \equiv 384^{2^{4-3-1}} \equiv 384 \ (\text{mod} \ 593). Replace the quantities R, c, t and E as follows:

  • \displaystyle R \equiv 218 \cdot 384 \equiv 99 \ (\text{mod} \ 593)
  • \displaystyle c \equiv 384^{2} \equiv 392 \ (\text{mod} \ 593)
  • \displaystyle t \equiv 201 \cdot 392 \equiv 516 \ (\text{mod} \ 593)
  • \displaystyle E=3

_______________________________________
The last t is obviously t \not \equiv 1. We now find the least i, 0<i<E, such that t^{2^i} \equiv 1. The result is i=2. Note that the order of t goes from 2^3 previously to 2^2.

Let b \equiv c^{2^{E-i-1}} \equiv 392^{2^{3-2-1}} \equiv 392 \ (\text{mod} \ 593). Replace the quantities R, c, t and E as follows:

  • \displaystyle R \equiv 99 \cdot 392 \equiv 263 \ (\text{mod} \ 593)
  • \displaystyle c \equiv 392^{2} \equiv 77 \ (\text{mod} \ 593)
  • \displaystyle t \equiv 516 \cdot 77 \equiv 1 \ (\text{mod} \ 593)
  • \displaystyle E=2

Now we reach t \equiv 1. The solutions to the equations are: 263 and 330 (=593 – 263). \square

Example 2
Solve the equation x^2 \equiv a \ (\text{mod} \ p) where p= 2795830049 and a= 2262876953.

The number p is a prime and the value of the Legendre symbol is \displaystyle  \biggl(\frac{a}{p}\biggr)=1. The following shows the steps.

Step 1. S=5 and Q= 87369689.

Step 2. y=3 is a quadratic nonresidue modulo p. This is the result of a search starting with 2.

Step 3. Calculate the following four quantities. All calculations are modulo p.

  • \displaystyle R \equiv a^{\frac{Q+1}{2}} \equiv 2075434035
  • \displaystyle c \equiv 3^{Q} \equiv 268289123
  • \displaystyle t \equiv a^{Q} \equiv 2666735226
  • \displaystyle E=5

The above t is obviously not 1. So we need to perform the loop several times.

_______________________________________
Iteration 1

  • i=4, the least i such that t^{2^i} \equiv 1.
  • b \equiv c^{2^{E-i-1}} \equiv c^{2^{5-4-1}} \equiv c \equiv 268289123
  • \displaystyle R_1 \equiv R \cdot b \equiv 2438491248
  • \displaystyle c_1 \equiv b^2 \equiv 717416975
  • \displaystyle t_1 \equiv c_1 \cdot t \equiv 2569006270
  • \displaystyle E_1=4

_______________________________________
Iteration 2

  • i=2, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_1^{2^{E_1-i-1}} \equiv c_1^{2^{4-2-1}} \equiv c_1^2 \equiv 17652213
  • \displaystyle R_2 \equiv R_1 \cdot b \equiv 2519954933
  • \displaystyle c_2 \equiv b^2 \equiv 2569006270
  • \displaystyle t_2 \equiv c_2 \cdot t_1 \equiv 2795830048
  • \displaystyle E_2=2

_______________________________________
Iteration 3

  • i=1, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_2^{2^{E_2-i-1}} \equiv c_2^{2^{2-1-1}} \equiv c_2 \equiv 2569006270
  • \displaystyle R_3 \equiv R_2 \cdot b \equiv  1147516973
  • \displaystyle c_3 \equiv b^2 \equiv 2795830048
  • \displaystyle t_3 \equiv c_3 \cdot t_2 \equiv 1
  • \displaystyle E_3=1

_______________________________________
Solutions

  • \displaystyle R \equiv 1147516973
  • \displaystyle p-R \equiv 1648313076

____________________________________________________________________________

Why the algorithm works

To prove that the algorithm produces the solutions to the given equation, we need the following lemma.

Lemma
Suppose that both g and h are relatively prime to an odd prime number p. Suppose that the order of g modulo p is 2^j with j being a positive integer. Suppose that the order of h modulo p is also 2^j. Then the order of g \cdot h modulo p is 2^k where k<j.

Proof
Since the order of g is 2^j, \displaystyle y=g^{2^{j-1}} \not \equiv 1 \ (\text{mod} \ p). Note that \displaystyle y^2 \equiv g^{2^{j}} \equiv 1 \ (\text{mod} \ p). Then it must be that y \equiv -1 \ (\text{mod} \ p) since the equation x^2 \equiv 1 \ (\text{mod} \ p) has only two solutions. By a similar argument, h^{2^{j-1}} \equiv -1 \ (\text{mod} \ p). Consider the following:

    \displaystyle (gh)^{2^{j-1}} \equiv g^{2^{j-1}} \cdot h^{2^{j-1}} \equiv (-1) (-1) \equiv 1 \ (\text{mod} \ p)

This means that the order of g \cdot h divides 2^{j-1}. Thus the order of g \cdot h modulo p must be 2^{k} for some k \le j-1 < j. \square

Proof of Tonelli-Shanks algorithm
Since p is an odd prime, we set p-1=Q \cdot 2^{S} where Q is odd. We also select a positive integer y that is a quadratic nonresidue modulo p. To start the calculation, obtain the following four quantities:

  • \displaystyle R \equiv a^{\frac{Q+1}{2}} \ (\text{mod} \ p)
  • \displaystyle c \equiv y^Q \ (\text{mod} \ p)
  • \displaystyle t \equiv a^{Q} \ (\text{mod} \ p)
  • \displaystyle E=S

The quantity R is an initial estimate of the desired solution since

    \displaystyle R^2 \equiv a^{Q+1} \equiv a \cdot a^Q \equiv a \cdot t \ (\text{mod} \ p)

If t \equiv 1 \ (\text{mod} \ p), then R would be a solution and the algorithm stops. So assume that t \not \equiv 1 \ (\text{mod} \ p). Then we begin a loop to fine tune R until reaching a step with t \equiv 1 \ (\text{mod} \ p).

To make sense of the loop in the algorithm, consider the quantity c and the quantity t. First of all, the integer c has order 2^S modulo p, as shown below.

    \displaystyle c^{2^S} \equiv (y^{Q})^{2^S} \equiv y^{p-1} \equiv (y^{\frac{p-1}{2}})^2 \equiv (-1)^2 \equiv 1 \ (\text{mod} \ p)

    \displaystyle c^{2^{S-1}} \equiv (y^{Q})^{2^{S-1}} \equiv y^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)

Furthermore, the order of t modulo p is less or equal to 2^S since \displaystyle t^{2^S} \equiv 1 \ (\text{mod} \ p) as shown below.

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

Let 2^{S_1} be the order of t where S_1 \le S. Now begin the calculation for the first iteration of the loop. First, calculate \displaystyle b_1 \equiv c^{2^{E-S_1-1}} \ (\text{mod} \ p).

  • \displaystyle R_1 \equiv R \cdot b_1 \ (\text{mod} \ p)
  • \displaystyle c_1 \equiv b_1^2 \ (\text{mod} \ p)
  • \displaystyle t_1 \equiv c_1 \cdot t \ (\text{mod} \ p)
  • \displaystyle E_1=S_1

One important point to make is that the order of c_1 modulo p is the same as the order of t, which is 2^{S_1}. The following shows why.

    \displaystyle c_1^{2^{S_1}} \equiv (b_1^2)^{2^{S_1}} \equiv b_1^{2^{S_1+1}} \equiv (c^{2^{E-S_1-1}})^{2^{S_1+1}} \equiv c^{2^S} \equiv 1 \ (\text{mod} \ p)

    \displaystyle c_1^{2^{S_1-1}} \equiv (b_1^2)^{2^{S_1-1}} \equiv b_1^{2^{S_1}} \equiv (c^{2^{E-S_1-1}})^{2^{S_1}} \equiv c^{2^{S-1}} \equiv -1 \ (\text{mod} \ p)

By the lemma, the order of \displaystyle t_1 \equiv c_1 \cdot t \ (\text{mod} \ p) is 2^{S_2} for some S_2<S_1. Note that

    \displaystyle R_1^2 \equiv R^2 \cdot b_1^2 \equiv a \cdot t \cdot c_1 \equiv a \cdot t_1 \ (\text{mod} \ p)

In light of the above, if \displaystyle t_1 \equiv 1 \ (\text{mod} \ p), then R_1 is a solution and the algorithm stops. Even if \displaystyle t_1 \not \equiv 1 \ (\text{mod} \ p), there is progress since the order of t_1 is less than the previous t with 2^{S_2}<2^{S_1}. Repeat the loop to obtain t_2, \cdots, t_k with the order of t_k being 2^{S_{k+1}}=1 where S_{k+1}=0. When the order of t_k is 1, t_k=1. When the modulus is a prime, there is only one element with order 1, namely the element 1. Then the quantity R_j is a solution to the given equation.

To further illustrate, we perform one more iteration of the loop. Let \displaystyle b_2 \equiv c_1^{2^{E_1-S_2-1}} \ (\text{mod} \ p). Calculate the following four quantities:

  • \displaystyle R_2 \equiv R_1 \cdot b_2 \ (\text{mod} \ p)
  • \displaystyle c_2 \equiv b_2^2 \ (\text{mod} \ p)
  • \displaystyle t_2 \equiv c_2 \cdot t_1 \ (\text{mod} \ p)
  • \displaystyle E_2=S_2

Similar to the previous step, the order of c_2 is the same as the order of t_1 as shown below:

    \displaystyle C_2^{2^{S_2}} \equiv (b_2^2)^{2^{S_2}} \equiv b_2^{2^{S_2+1}} \equiv (c_1^{2^{E_1-S_2-1}})^{2^{S_2+1}} \equiv c_1^{2^{E_1}} \equiv c_1^{2^{S_1}} \equiv 1 \ (\text{mod} \ p)

    \displaystyle C_2^{2^{S_2-1}} \equiv (b_2^2)^{2^{S_2-1}} \equiv b_2^{2^{S_2}} \equiv (c_1^{2^{E_1-S_2-1}})^{2^{S_2}} \equiv c_1^{2^{E_1-1}} \equiv c_1^{2^{S_1-1}} \equiv -1 \ (\text{mod} \ p)

By the lemma, the order of \displaystyle t_2 \equiv c_2 \cdot t_1 \ (\text{mod} \ p) is 2^{S_3} for some S_3<S_2. Note the following:

    \displaystyle R_2^2 \equiv R_1^2 \cdot b_2^2 \equiv a \cdot t_1 \cdot c_2 \equiv a \cdot t_2 \ (\text{mod} \ p)

Now we reach the same decision point. If t_2 \equiv 1, then R_2 is a solution and the algorithm stops. Even if t_2 \not \equiv 1, the order of t_2 is smaller than previously. Continue to execute the loop until the step where the order of t_k is 1. \square

____________________________________________________________________________

Comments

The Tonelli-Shanks algorithm works correctly (as the proof indicated) and works efficiently (as the examples show). The speed of the algorithm is a function of the inputs. The inputs to the Tonelli-Shanks algorithm are the odd prime p and the quadratic residue a modulo p. The two inputs are translated to the three quantities m, k and S where m is the number of digits in the binary representation of the odd prime p, k is the number of ones in the binary representation of p and S is the largest power of 2 in the factor of p-1. These three numbers determine the amount of calculations. According to this source, the average number of modular multiplications required by the Tonelli-Shanks algorithm is:

    \displaystyle 2m+2k+\frac{S(S-1)}{4}+\frac{1}{2^{S-1}}-9

Another consideration is the selection of y, a quadratic nonresidue modulo p, which can be found by checking random selections from the set \mathbb{Z}_p^*=\left\{1,2,\cdots,p-1 \right\}. Since half the elements in the set are quadratic residues, it takes on average two random selections from this set (hence two computations of the Legendre symbol). One way to see this is that the number of Bernoulli trials until the first success has a geometric distribution. The probability of success in each trial is 0.5. Then the mean of the geometric distribution is 1/0.5 = 2.

Overall, the Tonelli-Shanks algorithm works efficiently in solving the quadratic congruence equation (1). Along with the explicit formula (2) that handles the case of odd prime congruent to 3 modulo 4, the quadratic congruence equations are completely and efficiently solved. As a result, it is not possible to hide secrets using quadratic congruence equations with odd prime moduli. If a message is embedded as a solution of such equation, then it can be easily recovered using the Tonelli-Shanks algorithm or the explicit formula (2). On the other hand, the equation

    x^2 \equiv a \ (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

is difficult to solve where the modulus n is the product of two large primes p and q. In fact the Rabin cryptosystem is based on the difficulty of solving equation (3). However, if the factoring of n is known, equation (3) is solvable and the Tonelli-Shanks algorithm along with the Chinese remainder theorem play a crucial role.

____________________________________________________________________________

Another example

Example 3
This is a slightly larger example than the ones given earlier. Solve the equation x^2 \equiv a \ (\text{mod} \ p) where p= 3825123056546413057 and a= 1347234680313589343.

The number p is a prime and the value of the Legendre symbol is \displaystyle  \biggl(\frac{a}{p}\biggr)=1. The following shows the steps.

Step 1. S=9 and Q= 7470943469817213.

Step 2. y=5 is a quadratic nonresidue modulo p. This is the result of a search starting with 2.

Step 3. Calculate the following four quantities. All calculations are modulo p.

  • \displaystyle R \equiv a^{\frac{Q+1}{2}} \equiv 2098778229504385555
  • \displaystyle c \equiv 5^{Q} \equiv 945046778698092498
  • \displaystyle t \equiv a^{Q} \equiv 3356211917617579979
  • \displaystyle E=9

The above t is obviously not 1. So we need to perform the loops several times.

_______________________________________
Iteration 1

  • i=8, the least i such that t^{2^i} \equiv 1.
  • b \equiv c^{2^{E-i-1}} \equiv c^{2^{9-8-1}} \equiv c \equiv 945046778698092498
  • \displaystyle R_1 \equiv R \cdot b \equiv 852974818860733646
  • \displaystyle c_1 \equiv b^2 \equiv 777225398785777536
  • \displaystyle t_1 \equiv c_1 \cdot t \equiv 3130593564544117824
  • \displaystyle E_1=8

_______________________________________
Iteration 2

  • i=7, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_1^{2^{E_1-i-1}} \equiv c_1^{2^{8-7-1}} \equiv c_1 \equiv 777225398785777536
  • \displaystyle R_2 \equiv R_1 \cdot b \equiv 1437578878907258220
  • \displaystyle c_2 \equiv b^2 \equiv 872612747799733789
  • \displaystyle t_2 \equiv c_2 \cdot t_1 \equiv 3053369905528253481
  • \displaystyle E_2=7

_______________________________________
Iteration 3

  • i=2, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_2^{2^{E_2-i-1}} \equiv c_2^{2^{7-2-1}} \equiv c_2^{2^5} \equiv 2409792470045159888
  • \displaystyle R_3 \equiv R_2 \cdot b \equiv 1136125891705727966
  • \displaystyle c_3 \equiv b^2 \equiv 3053369905528253481
  • \displaystyle t_3 \equiv c_3 \cdot t_2 \equiv 3825123056546413056
  • \displaystyle E_3=2

_______________________________________
Iteration 4

  • i=1, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_3^{2^{E_3-i-1}} \equiv c_3^{2^{2-1-1}} \equiv c_3^{2^0} \equiv c_3 \equiv 3053369905528253481
  • \displaystyle R_4 \equiv R_3 \cdot b \equiv  3727993796269536942
  • \displaystyle c_4 \equiv b^2 \equiv 3825123056546413056
  • \displaystyle t_4 \equiv c_4 \cdot t_3 \equiv 1
  • \displaystyle E_4=1

_______________________________________
Solutions

  • \displaystyle R \equiv 3727993796269536942
  • \displaystyle p-R \equiv 97129260276876115

____________________________________________________________________________

Exercises

We close with some exercises. Use Tonelli-Shanks algorithm to solve the equation x^2 \equiv a \ (\text{mod} \ p) for each of the following choices of a and p.

  1. p=193 and a = 67
  2. p=569 and a = 367
  3. p=34369 and a = 19170
  4. p=50753 and a = 12957
  5. p=97241 and a = 47861
  6. p=2773676993 and a = 1342865413

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

Solutions are:

  1. 35 and 158
  2. 103 and 466
  3. 19136 and 15233
  4. 30781 and 19972
  5. 45733 and 51508
  6. 1056882643 and 1716794350

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

Advertisements

The primitive root theorem revisited

The primitive root theorem lists out all possible values of m for which primitive roots exist in the modulo m arithmetic. The theorem is proved in this previous post and several blog posts leading to it. In this post, we reorganize the proof and add some additional information. The proof of the primitive root theorem detailed below shows that the list of values of the moduli m is very restrictive and, in addition, that such moduli m are such that there are no extra square root beside 1 and -1. The crux of the argument is a lemma that indicates that most moduli have a third square root of 1 in addition to 1 and -1. The proof is also an opportunity for applying the Chinese remainder theorem (usually abbreviated CRT).

____________________________________________________________________________

The primitive root theorem

In this post, m is a positive integer that serves as the modulus. Given m, it is of interest to know all the integers a where 1 \le a <m and that a and the modulus m are relatively prime. The number of such values of a is denoted by \phi(m) (this is called the phi function). For example, for m=11, \phi(11)=10. For m=10, \phi(10)=4 since there are only 4 numbers that are relatively prime to 10, namely 1, 3, 7, and 9.

A positive integer g is said to be a primitive root modulo m if \phi(m) is the least positive integer x such that g^x \equiv 1 \ (\text{mod} \ m). If g is said to be a primitive root modulo m, it is necessary that g and the modulus m are relatively prime. This is because of this basic fact: a and the modulus m are relatively prime if and only a \cdot b \equiv 1 \ (\text{mod} \ m) if and only of a^t \equiv 1 \ (\text{mod} \ m) for some integer t. The middle condition is saying that a has a multiplicative modulo m.

The following lemma is alluded to at the beginning. The idea will used through the proof of the primitive root theorem. So it is extracted as a lemma to make the argument easier to follow.

Lemma 1
Let c and d be integers such that c>2 and d>2 and such that c and d are relatively prime. Let m=c \cdot d. Then there exist x_0 such that x_0 \not \equiv \pm 1 \ (\text{mod} \ m) and such that x_0^2 \equiv 1 \ (\text{mod} \ m), i.e. x_0 is a third square root of 1 modulo m that is neither 1 nor -1.

Proof
Consider the two equations x \equiv 1 \ (\text{mod} \ c) and x \equiv -1 \ (\text{mod} \ d). By the Chinese remainder theorem, there is a solution x_0 to this system of equations. We have x_0^2 \equiv 1 \ (\text{mod} \ c) and x_0^2 \equiv 1 \ (\text{mod} \ d). By the Chinese remainder theorem again, x_0^2 \equiv 1 \ (\text{mod} \ m). There are three possibilities for x_0, 1, -1 or another value. If x_0 \equiv 1 \ (\text{mod} \ m), then 1 \equiv -1 \ (\text{mod} \ d), which means d \lvert 2, contradicting that d>2. Similarly, x_0 \equiv -1 \ (\text{mod} \ m) would lead to c \lvert 2, which contradicts c>2. The only possibility is that x_0 \not \equiv \pm 1 \ (\text{mod} \ m). \square

The proof of Lemma 1 makes use of CRT twice. Lemma 1 will be used several times in the proof of 2 \longrightarrow 3 in the primitive root theorem.

The Primitive Root Theorem
Let m be a positive integer. Then the following conditions are equivalent:

  1. There exists a primitive root modulo m.
  2. The equation x^2 \equiv 1 \ (\text{mod} \ m) has no solution outside of \pm 1 modulo m. In other words, the only square roots of 1 modulo m are \pm 1.
  3. The only possibilities for m are:
    • m=2,
    • m=4,
    • m is the power of an odd prime,
    • m is twice the power of an odd prime.

Proof
1 \longrightarrow 2
Suppose that g is a primitive root modulo m. Suppose that condition 2 does not hold. As a result, there exists some positive integer a \not \equiv \pm 1 \ (\text{mod} \ m) such that a^2 \equiv 1 \ (\text{mod} \ m). Since g is a primitive root modulo m, a \equiv g^h \ (\text{mod} \ m) for some integer integer h with 1 \le h < \phi(m) (see Theorem 5 here). If h = \phi(m), then a \equiv 1 \ (\text{mod} \ m). Thus 1 \le h < \phi(m).

Furthermore, a^2 \equiv g^{2h} \equiv 1 \ (\text{mod} \ m). We have \phi(m) \le 2h, since \phi(m) is the least power x such that g^x is congruent to 1 modulo m. Since g^{2h}=g^{\phi(m)} g^{2h-\phi(m)}, g^{2h} \equiv g^{2h-\phi(m)} \equiv 1 \ (\text{mod} \ m). We have \phi(m) \le 2h-\phi(m) since \phi(m) is the least power x such that g^x is congruent to 1 modulo m. The last inequality leads to \phi(m) \le h, contradicting the earlier observation of h < \phi(m). Thus condition 2 must holds if condition 1 is true.

2 \longrightarrow 3
We show that for any m outside of the four possibilities listed in condition 3, condition 2 does not hold. This means that if condition 2 holds for m, m must be one of the four possibilities. We consider the cases of m even and m odd separately.

Case 1. The modulus m is odd. Since m is not the power of one single odd prime, it must be the product of two or more powers of odd primes. Let m=c \cdot d where c a power of an odd prime and d is the product of one ore more powers of odd primes. It is clear that c and d are relatively prime. It is also the case that c>2 and d>2 since each of them has at least one odd prime factor. By Lemma 1, there exists a square root x_0 of 1 such that x_0 \not \equiv \pm 1 \ (\text{mod} \ m).

For the second case, m is even. We break this up into two cases. One is that m is a power of 2. The other is that m is not a power of 2. In these two cases, the goal is still to show that if m is outside of the four possibilities in condition 3, then condition 2 does not hold.

Case 2a. The modulus m is a power of 2.
Then m=2^h where h \ge 3. In this case, we can actually exhibit a square root that is neither 1 nor -1. Define x_0=2^{h-1}-1. Since h \ge 3, x_0>1. Consider the following derivation:

    \displaystyle x_0^2=(2^{h-1}-1)^2=2^{2(h-1)}-2^h+1=2^h (2^{h-2}-1)+1

The above derivation shows that x_0^2 \equiv 1 \ (\text{mod} \ m=2^h). It is clear that x_0 \not \equiv \pm 1 \ (\text{mod} \ 2^h).

Case 2b. The modulus m is not a power of 2.
Since m is even and m is not a power of 2, it must be that m=2^k \times q where q is odd. Either q is the power of an odd prime or it is not. If q is the power of an odd prime, then k \ge 2. If q is not the power of an odd prime (i.e. q is of case 1 above), then k \ge 1. To make the argument clear, we consider the two sub cases separately.

Case 2b-1. The modulus m=2^k \times p^j where k \ge 2, j \ge 1 and p is an odd prime.
Let c=2^k and d=p^j. Note that m=c \cdot d. By Lemma 1, there exists a square root x_0 of 1 modulo m such that x_0 \not \equiv \pm 1 \ (\text{mod} \ m).

Case 2b-2. The modulus m=2^k \times b where k \ge 1 and b is an odd integer that is not the power of an odd prime.
Consider the prime factorization of b, say b=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t} where t \ge 2. Let c=2^k \cdot p_1^{e_1} and d=p_2^{e_2} \cdots p_t^{e_t}. We can also apply Lemma 1 to obtain a square root of 1 modulo m=c \cdot d that is neither 1 nor -1.

3 \longrightarrow 1
It is clear that there are primitive roots modulo both m=2 and m=4. For the case of power of an odd prime, see this previous post. For the case of twice the power of an odd prime, see this previous post. \square

____________________________________________________________________________

Comments

Lemma 1 plays a prominent role in the proof of the direction 2 \longrightarrow 3. Lemma 1 shows that it is easy to find moduli that have a third square root of 1 (other than 1 and -1). As the primitive root theorem shows, having a third square root of 1 is the condition that kills the possibility of having a primitive root. Lemma 1 and the primitive root theorem speak to different sides of the same coin. One tells us that moduli with no primitive roots are easy to find. The other says that only in rare cases do you find moduli that admit primitive roots, namely the moduli that are not product of two factors, each of which is greater than 2, that are relatively prime. The proof of 2 \longrightarrow 3 may seem tedious (by listing out all cases that satisfy Lemma 1). The key to understanding the proof is through Lemma 1.

____________________________________________________________________________

\copyright \ 2015 \text{ by Dan Ma}

Introducing Carmichael numbers

This is an introduction to Carmichael numbers. We first discuss Carmichael numbers in the context of Fermat primality test and then discuss several basic properties. We also prove Korselt’s criterion, which gives a useful characterization of Carmichael numbers.

___________________________________________________________________________________________________________________

Fermat Primality Test

Fermat’s little theorem states that if p is a prime number, then a^p \equiv a \ (\text{mod} \ p) for any integer a. Fermat primality test refers to the process of using Fermat little theorem to check the “prime vs. composite” status of an integer.

Suppose that we have a positive integer n such that the “prime vs. composite” status is not known. If we can find an integer a such that a^n \not \equiv a \ (\text{mod} \ n), then we know for certain that the modulus n is composite (or not prime). For example, let n = \text{8,134,619}. Note that 2^{8134619} \equiv 3024172 \ (\text{mod} \ 8134619). So we know right away that n = \text{8,134,619} is not prime, even though we do not know what its prime factors are just from applying this test.

Given a positive integer n, whenever a^n \not \equiv a \ (\text{mod} \ n), we say that a is a Fermat witness for (the compositeness of) the integer n. Thus 2 is a Fermat witness for n = \text{8,134,619}.

What if we try one value of a and find that a is not a witness for (the compositeness of) n? Then the test is inconclusive. The best we can say is that n is probably prime. It makes sense to try more values of a. If all the values of a we try are not witnesses for n (i.e. a^n \equiv a \ (\text{mod} \ n) for all the values of a we try), then it “seems likely” that n is prime. But if we actually declare that n is prime, the decision could be wrong!

Take n=\text{10,024,561}. For several randomly chosen values of a, we have the following calculations:

    \displaystyle 5055996^{10024561} \equiv 5055996 \ (\text{mod} \ 10024561)

    \displaystyle 4388786^{10024561} \equiv 4388786 \ (\text{mod} \ 10024561)

    \displaystyle 4589768^{10024561} \equiv 4589768 \ (\text{mod} \ 10024561)

    \displaystyle  146255^{10024561} \equiv 146255 \ (\text{mod} \ 10024561)

    \displaystyle 6047524^{10024561} \equiv 6047524 \ (\text{mod} \ 10024561)

The above calculations could certainly be taken as encouraging signs that n=\text{10,024,561} is prime. With more values of a, we also find that a^{10024561} \equiv a \ (\text{mod} \ 10024561). However, if we declare that n=\text{10,024,561} is prime, it turns out to be a wrong conclusion.

In reality, n=\text{10,024,561} is composite with \text{10,024,561}=71 \cdot 271 \cdot 521. Furthermore a^{10024561} \equiv a \ (\text{mod} \ 10024561) for any integer a. So there are no witnesses for n=\text{10,024,561}. Any composite positive integer that has no Fermat witnesses is called a Carmichael number, in honor of Robert Carmichael who in 1910 found the smallest such number, which is 561.

Fermat primality test is always correct if the conclusion is that the integer being tested is a composite number (assuming there is no computational error). If the test says the number is composite, then it must be a composite number. In other words, there are no false negatives in using Fermat primality test as described above.

On the other hand, there can be false positives as a result of using Fermat primality test. If the conclusion is that the integer being tested is a prime number, it is possible that the conclusion is wrong. For a wrong conclusion, it could be that there exists a witness for the number being tested and that we have missed it. Or it could be that the number being tested is a Carmichael number. Though Carmichael numbers are rare but there are infinitely many of them. So we cannot ignore them entirely. For these reasons, Fermat primality test as described above is often not used. Instead, other extensions of the Fermat primality test are used.

___________________________________________________________________________________________________________________

Carmichael Numbers

As indicated above, a Carmichael number is a positive composite integer that has no Fermat witnesses. Specifically, it is a positive composite integer that satisfies the conclusion of Fermat’s little theorem. In other words, a Carmichael number is a positive composite integer n such that a^n \equiv a \ (\text{mod} \ n) for any integer a.

Carmichael numbers are rare. A recent search found that there are \text{20,138,200} Carmichael numbers between 1 and 10^{21}, about one in 50 trillion numbers (documented in this Wikipedia entry on Carmichael numbers). However it was proven by Alford, Granville and Pomerance in 1994 that there are infinitely many Carmichael numbers (paper).

The smallest Carmichael number is 561=3 \cdot 11 \cdot 17. A small listing of Carmichael numbers can be found in this link, where the example of n=\text{10,024,561} is found.

Carmichael numbers must be odd integers. To see this, suppose n is a Carmichael number and is even. Let a=-1. By condition (1) of Theorem 1, we have (-1)^n=1 \equiv -1 \ (\text{mod} \ n). On the other hand, -1 \equiv n-1 \ (\text{mod} \ n). Thus n-1 \equiv 1 \ (\text{mod} \ n). Thus we have n \equiv 2 \ (\text{mod} \ n). It must be the case that n=2, contradicting the fact that n is a composite number. So any Carmichael must be odd.

The following theorem provides more insight about Carmichael numbers. A positive integer n is squarefree if its prime decomposition contains no repeated prime factors. In other words, the integer n is squarefree means that if \displaystyle n=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} is the prime factorization of n, then all exponents e_j=1.

    Theorem 1 (Korselt’s Criterion)

      Let n be a positive composite integer. Then the following conditions are equivalent.

      1. The condition a^n \equiv a \ (\text{mod} \ n) holds for any integer a.
      2. The condition a^{n-1} \equiv 1 \ (\text{mod} \ n) holds for any integer a that is relatively prime to n.
      3. The integer n is squarefree and p-1 \ \lvert \ (n-1) for any prime divisor p of n.

Proof of Theorem 1

1 \Longrightarrow 2
Suppose that a is relatively prime to the modulus n. Then let b be the multiplicative inverse of a modulo n, i.e., ab \equiv 1 \ (\text{mod} \ n). By (1), we have a^n \equiv a \ (\text{mod} \ n). Multiply both sides by the multiplicative inverse b, we have a^{n-1} \equiv 1 \ (\text{mod} \ n).

2 \Longrightarrow 3
Let \displaystyle n=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} be the prime factorization of n where p_i \ne p_j for i \ne j and each exponent e_j \ge 1. Since n must be odd, each p_j must be an odd prime.

We first show that each e_j=1, thus showing that n is squarefree. To this end, for each j, let a_j be a primitive root modulo p_j^{e_j} (see Theorem 4 in the post Primitive roots of powers of odd primes). Consider the following system of linear congruence equations:

    x \equiv a_1 \ (\text{mod} \ p_1^{e_1})

    x \equiv a_2 \ (\text{mod} \ p_2^{e_2})

      \cdots
      \cdots
      \cdots

    x \equiv a_t \ (\text{mod} \ p_t^{e_t})

Since the moduli p_j^{e_j} are pairwise relatively prime, this system must have a solution according to the Chinese Remainder Theorem (a proof is found here). Let a one such solution. For each j, since a_j is a primitive root modulo p_j^{e_j}, a_j is relatively prime to p_j^{e_j}. Since a \equiv a_j \ (\text{mod} \ p_j^{e_j}), a is relatively prime to p_j^{e_j} for each j. Consequently, a is relatively prime to n. By assumption (2), we have a^{n-1} \equiv 1 \ (\text{mod} \ n).

Now fix a j with 1 \le j \le t. We show that e_j=1. Since a^{n-1} \equiv 1 \ (\text{mod} \ n), a^{n-1} \equiv 1 \ (\text{mod} \ p_j^{e_j}). Since a \equiv a_j \ (\text{mod} \ p_j^{e_j}), we have a_j^{n-1} \equiv 1 \ (\text{mod} \ p_j^{e_j}). Note that the order of a_j modulo p_j^{e_j} is \phi(p_j^{e_j})=p_j^{e_j-1}(p_j-1). Thus we have p_j^{e_j-1}(p_j-1) \ \lvert \ (n-1). If e_j>1, then p_j \ \lvert \ (n-1), which would mean that p_j \ \lvert \ 1. So it must be the case that e_j=1. It then follows that (p_j-1) \ \lvert \ (n-1).

3 \Longrightarrow 1
Suppose that n=p_1 p_2 \cdots p_t is a product of distinct prime numbers such that for each j, (p_j-1) \ \lvert \ (n-1).

Let a be any integer. First we show that a^n \equiv a \ (\text{mod} \ p_j) for all j. It then follows that a^n \equiv a \ (\text{mod} \ n).

Now fix a j with 1 \le j \le t. First consider the case that a and p_j are relatively prime. According to Fermat’s little theorem, a^{p_j-1} \equiv 1 \ (\text{mod} \ p_j). Since (p_j-1) \ \lvert \ (n-1), a^{n-1} \equiv 1 \ (\text{mod} \ p_j). By the Chinese Remainder Theorem, it follows that a^{n-1} \equiv 1 \ (\text{mod} \ n) and a^n \equiv a \ (\text{mod} \ n). \blacksquare

Examples
With Korselt’s criterion, it is easy to verify Carmichael numbers as long as the numbers are factored. For example, the smallest Carmichael number is 561=3 \cdot 11 \cdot 17. The number is obviously squarefree. furthermore 560 is divisible by 2, 10 and 16.

The number \text{10,024,561}= 71 \cdot 271 \cdot 521 is discussed above. We can also verify that this is a Carmichael number: 70 \ \lvert \ \text{10,024,560}, 270 \ \lvert \ \text{10,024,560} and 520 \ \lvert \ \text{10,024,560}.

Here’s three more Carmichael numbers (found here):

    \text{23,382,529} = 97 \cdot 193 \cdot 1249

    \text{403,043,257} = 19 \cdot 37 \cdot 43 \cdot 67 \cdot 199

    \text{154,037,320,009} = 23 \cdot 173 \cdot 1327 \cdot 29173

We end the post by pointing out one more property of Carmichael numbers, that Carmichael numbers must have at least three distinct prime factors. To see this, suppose that n=p \cdot q is a Carmichael number with two distinct prime factors p and q. We can express n-1 as follows:

    n-1=pq-1=(p-1)q+q-1

Since n is Carmichael, p-1 \ \lvert \ (n-1). So n-1=(p-1)w for some integer w. Plugging this into the above equation, we see that p-1 \ \lvert \ (q-1). By symmetry, we can also show that q-1 \ \lvert \ (p-1). Thus p=q, a contradiction. So any Carmichael must have at least three prime factors.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

The primitive root theorem

The primitive root theorem identifies all the positive integers for which primitive roots exist. The list of such integers is a restrictive list. This post along with two previous posts give a complete proof of this theorem using only elementary number theory. We prove the following theorem.

    Main Theorem (The Primitive Root Theorem)

      There exists a primitive root modulo m if and only if m=2, m=4, m=p^t or m=2p^t where p is an odd prime number and t is a positive integer.

The theorem essentially gives a list of the moduli that have primitive roots. Any modulus outside this restrictive list does not have primitive roots. For example, any integer that is a product of two odd prime factors is not on this list and hence has no primitive roots. In the post Primitive roots of powers of odd primes, we show that the powers of an odd prime have primitive roots. In the post Primitive roots of twice the powers of odd primes, we show that the moduli that are twice the power of an odd prime have primitive roots. It is easy to verify that the moduli 2 and 4 have primitive roots. Thus the direction \Longleftarrow of the primitive root theorem has been established. In this post we prove the direction \Longrightarrow, showing that if there exists a primitive root modulo p, then p must be one of the moduli in the list stated in the theorem.

___________________________________________________________________________________________________________________

LCM

The proof below makes use of the notion of the least common multiple. Let a and b be positive integers. The least common multiple of a and b is denoted by \text{LCM}(a,b) and is defined as the least positive integer that is divisible by both a and b. For example, \text{LCM}(16,18)=144. We can also express \text{LCM}(a,b) as follows:

    \displaystyle \text{LCM}(a,b)=\frac{a \cdot b}{\text{GCD}(a,b)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

where \text{GCD}(a,b) is the greatest common divisor of a and b. The above formula reduces the calculation of LCM to that of calculating the GCD. To compute the LCM of two numbers, we can simply remove the common prime factors between the two numbers. When the number a and b are relatively prime, i.e., \text{GCD}(a,b)=1, we have \displaystyle \text{LCM}(a,b)=a \cdot b.

Another way to look at LCM is that it is the product of multiplying together the highest power of each prime number. For example, 48=2^4 \cdot 3 and 18=2 \cdot 3^2. Then \text{LCM}(16,18)=2^4 \cdot 3^2=144.

The least common divisor of the numbers a_1,a_2,\cdots,a_n is denoted by \text{LCM}(a_1,a_2,\cdots,a_n) and is defined similarly. It is the least positive integer that is divisible by all a_j. Since the product of all the numbers a_j is one integer that is divisible by each a_k, we have:

    \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n) \le a_1 \cdot a_2 \cdots a_n  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

As in the case of two numbers, the LCM of more than two numbers can be thought as the product of multiplying together the highest power of each prime number. For example, the LCM of 48=2^4 \cdot 3, 18=2 \cdot 3^2 and 45=3^2 \cdot 5 is 2^4 \cdot 3^2 \cdot 5=720.

For a special case, there is a simple expression of LCM.

    Lemma 1

      Let a_1,a_2,\cdots,a_n be positive integers.

      Then \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n)=a_1 \cdot a_2 \cdots a_n if and only if the numbers a_1,a_2,\cdots,a_n are pairwise relatively prime, i.e., a_i and a_j are relatively prime whenever i \ne j.

Proof of Lemma 1
\Longleftarrow
Suppose the numbers are pairwise relatively prime. Then there are no common prime factors in common between any two numbers on the list. Then multiplying together the highest power of each prime factor is the same as multiplying the individual numbers a_1,a_2 \cdots,a_n.

\Longrightarrow
Suppose a_i and a_j are not relatively prime for some i \ne j. As a result, d=\text{GCD}(a_i,a_j)>1. It follows that

    \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n) \le \frac{a_1 \cdot a_2 \cdots a_n}{d} < a_1 \cdot a_2,\cdots a_n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

To give a sense of why the above is true, let’s look at a simple case of d=\text{GCD}(a_i,a_j)=p^u where p is a prime number and u \ge 1. Assume that a_i=a_1, a_j=a_2 and p^u is part of the prime factorization of a_1. Furthermore, note that \displaystyle \text{LCM}(\frac{a_1}{p^u},a_2,\cdots,a_n) is identical to \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n). The following derivation confirms (3):

    \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n)=\text{LCM}(\frac{a_1}{p^u},a_2,\cdots,a_n) \le \frac{a_1}{p^u} \cdot a_2 \cdots a_n < a_1 \cdot a_2,\cdots a_n

With the above clarification, the lemma is established. \blacksquare

___________________________________________________________________________________________________________________

Other Tools

We need to two more lemmas to help us prove the main theorem.

    Lemma 2

      Let m and n be positive integers that are relatively prime. Then a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n) if and only if a \equiv b \ (\text{mod} \ mn).
    Lemma 3

      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).

Lemma 2 a version of the Chinese Remainder Theorem and is proved a previous post (see Theorem 2 in Primitive roots of twice the powers of odd primes or see Theorem 2 in Proving Chinese Remainder Theorem). Lemma 3 is also proved in a previous post (see Lemma 2 in More about checking for primitive roots).

___________________________________________________________________________________________________________________

Breaking It Up Into Smaller Pieces

The proof of the direction \Longrightarrow of the primitive root theorem is done in the following lemmas and theorems.

    Lemma 4

      Let \displaystyle m=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} be the prime factorization of the positive integer m. Let a be a primitive root modulo m. Then the numbers \phi(p_1^{e_1}), \phi(p_2^{e_2}),\cdots,\phi(p_t^{e_t}) are pairwise relatively prime.

Proof of Lemma 4
Note that a is relatively prime to m. So a is relatively prime to each p_j^{e_j}. By Euler’s theorem, we have \displaystyle a^{\phi(p_j^{e_j})} \equiv 1 \ (\text{mod} \ p_j^{e_j}) for each j. Let \displaystyle W=\text{LCM}(\phi(p_1^{e_1}),\phi(p_2^{e_2}),\cdots,\phi(p_t^{e_t})).

By definition of LCM, \phi(p_j^{e_j}) \ \lvert \ W for each j. So \displaystyle a^{W} \equiv 1 \ (\text{mod} \ p_j^{e_j}) for each j. By the Chinese remainder theorem (Lemma 2 above), \displaystyle a^{W} \equiv 1 \ (\text{mod} \ m). Since a is a primitive root modulo m, it must be that \phi(m) \le W. Interestingly, we have:

    \displaystyle \phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_t^{e_t})=\phi(m) \le W \le \phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_t^{e_t})

Thus \displaystyle \text{LCM}(\phi(p_1^{e_1}),\phi(p_2^{e_2}),\cdots,\phi(p_t^{e_t}))=\phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_t^{e_t}). By Lemma 1, the numbers \phi(p_j^{e_j}) are relatively prime. \blacksquare

The following theorems follow from Lemma 4. The main theorem is a corollary of these theorems.

    Theorem 5

      If there exists a primitive root modulo m, then m cannot have two distinct prime divisors.

Proof of Theorem 5
Let \displaystyle m=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} be the prime factorization of m where t \ge 2.

If p_i and p_j are odd prime with i \ne j, then \phi(p_i^{e_i})=p_i^{e_i-1}(p_i-1) and \phi(p_j^{e_j})=p_j^{e_j-1}(p_j-1) are both even and thus not relatively prime. If there exists a primitive root modulo m, \phi(p_i^{e_i}) and \phi(p_j^{e_j}) must be relatively prime (see Lemma 4). Since we assume that there exists a primitive root modulo m, m cannot have two distinct odd prime divisors. \blacksquare

    Theorem 6

      Suppose that there exists a primitive root modulo m and that m has exactly one odd prime factor p. Then m must be of the form p^e or 2p^e where e \ge 1.

Proof of Theorem 6
By Theorem 5, the prime factorization of m must be m=2^{e_1} p^{e_2} where e_1 \ge 0 and e_2 \ge 1.

We claim that e_1=0 or e_1=1. Suppose e_1 \ge 2. Then \phi(2^{e_1})=2^{e_1-1} and \phi(p^{e_2})=p^{e_2-1}(p-1) are both even and thus not relatively prime. Lemma 4 tells us that there does not exist a primitive root modulo m. So if there exists a primitive root modulo m, then it must be the case that e_1=0 or e_2=1.

If e_1=0, then m=p^{e_2}. If e_1=1, then m=2p^{e_2}. \blacksquare

    Lemma 7

      Let n=2^k where k \ge 3. Then \displaystyle a^{\frac{\phi(n)}{2}} \equiv 1 \ (\text{mod} \ n) for any a that is relatively prime to n.

Proof of Lemma 7
We prove this by induction on k. Let k=3. Then n=8 and \displaystyle \frac{\phi(8)}{2}=2. For any odd a with 1 \le a <8, it can be shown that a^2 \equiv 1 \ (\text{mod} \ 8).

Suppose that the lemma holds for k where k \ge 3. We show that it holds for k+1. Note that \phi(2^k)=2^{k-1} and \displaystyle \frac{\phi(2^k)}{2}=2^{k-2}. Since the lemma holds for k, we have \displaystyle v^{2^{k-2}} \equiv 1 \ (\text{mod} \ 2^k) for any v that is relatively prime to 2^k. We can translate this congruence into the equation v^{2^{k-2}}=1+2^k y for some integer y.

Note that \phi(2^{k+1})=2^{k} and \displaystyle \frac{\phi(2^{k+1})}{2}=2^{k-1}. It is also the case that (v^{2^{k-2}})^2=v^{2^{k-1}}. Thus we have:

    \displaystyle v^{2^{k-1}}=(1+2^k y)^2=1+2^{k+1} y+2^{2k} y^2=1+2^{k+1}(y+2^{k-1} y^2)

The above derivation shows that \displaystyle v^{\frac{\phi(2^{k+1})}{2}} \equiv 1 \ (\text{mod} \ 2^{k+1}) for any v that is relatively prime to 2^k.

On the other hand, a is relatively prime to 2^{k+1} if and only if a is relatively prime to 2^k. So \displaystyle a^{\frac{\phi(2^{k+1})}{2}} \equiv 1 \ (\text{mod} \ 2^{k+1}) for any a that is relatively prime to 2^{k+1}. Thus the lemma is established. \blacksquare

    Theorem 8

      Suppose that there exists a primitive root modulo m and that m=2^e where e \ge 1. Then m=2^e where e=1 or e=2.

Proof of Theorem 8
Suppose m=2^e where e \ge 3. By Lemma 7, \displaystyle a^{\frac{\phi(m)}{2}} \equiv 1 \ (\text{mod} \ n) for any a relatively prime to m. Since 2 is the only prime divisor of m, by Lemma 3, there cannot be primitive root modulo m. Thus if there exists a primitive root modulo m and that m=2^e where e \ge 1, then the exponent e can be at most 2. \blacksquare

___________________________________________________________________________________________________________________

Putting It All Together

We now put all the pieces together to prove the \Longrightarrow of the Main Theorem. It is a matter of invoking the above theorems.

Proof of Main Theorem
Suppose that there exists a primitive root modulo m. Consider the following three cases about the modulus m.

  1. m has no odd prime divisor.
  2. m has exactly one odd prime divisor.
  3. m has at least two odd prime divisors.

\text{ }
Suppose Case 1 is true. Then m=2^e where e \ge 1. By Theorem 8, m=2 or m=4.

Suppose Case 2 is true. Then Theorem 6 indicates that m must be the power of an odd prime or twice the power of an odd prime.

Theorem 5 indicates that Case 3 is never true. Thus the direction \Longrightarrow of the Main Theorem is proved. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Primitive roots of twice the powers of odd primes

In a previous post, we show that there exist primitive roots modulo the power of an odd prime number (see Primitive roots of powers of odd primes). In this post we show that there exist primitive roots modulo two times the power of an odd prime number. Specifically we prove the following theorem.

    Theorem 1

      Let p be an odd prime number. Let j be any positive integer. Then there exist primitive roots modulo p^j.

We make use of the Chinese Remainder Theorem (CRT) in proving Theorem 1. We use the following version of CRT (also found in this post)

    Theorem 2 (CRT)

      Let m and n be positive integers that are relatively prime. Then a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n) if and only if a \equiv b \ (\text{mod} \ mn).

Proof of Theorem 2
\Longrightarrow
Suppose a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n). Converting these into equations, we have a=b+mx and a=b+ny for some integers x and y. It follows that mx=ny. This implies that m \ \lvert \ ny. Since m and n and relatively prime, m \ \lvert \ y and y=mt for some integer t. Now the equation a=b+ny can be written as a=b+mnt, which implies that a \equiv b \ (\text{mod} \ mn).

\Longleftarrow
Suppose a \equiv b \ (\text{mod} \ mn). Then a=b+mns for some integer s, which implies both congruences a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n). \blacksquare

Proof of Theorem 1
Let a be a primitive root modulo p^j (shown to exist in the post Primitive roots of powers of odd primes). When a is odd, we show that a is a primitive root modulo 2p^j. When a is even, we show that a+p^j is a primitive root modulo 2p^j.

First the odd case. Since a is a primitive root modulo p^j, a^k \not \equiv 1 \ (\text{mod} \ p^j) for all positive k<\phi(p^j). Since a is odd, a^k is odd for all integers k \ge 1. So a^k \equiv 1 \ (\text{mod} \ 2) for all integers k \ge 1. By CRT (Theorem 2), a^k \not \equiv 1 \ (\text{mod} \ 2p^j) for all positive k<\phi(p^j)=\phi(2 p^j). This implies that a is a primitive root modulo 2p^j.

Now the even case. Note that a+p^j is odd (even + odd is odd). It is also the case that (a+p^j)^k is odd for all k \ge 1. Thus (a+p^j)^k \equiv 1 \ (\text{mod} \ 2) for all k \ge 1.

In expanding (a+p^j)^k using the binomial theorem, all terms except the first term a^k is divisible by p^j. So (a+p^j)^k \equiv a^k \ (\text{mod} \ p^j). Furthermore, a^k \not \equiv 1 \ (\text{mod} \ p^j) for all positive k<\phi(p^j) since a is a primitive root modulo p^j. So (a+p^j)^k \not \equiv 1 \ (\text{mod} \ p^j) for all positive k<\phi(p^j).

By CRT (Theorem 2), we have (a+p^j)^k \not \equiv 1 \ (\text{mod} \ 2p^j) for all positive k<\phi(p^j)=\phi(2p^j). This implies that a+p^j is a primitive root modulo 2p^j. \blacksquare

The remainder of the proof of the primitive root theorem is found in The primitive root theorem.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Primitive roots of powers of odd primes

Let p be an odd prime number. There exist primitive roots modulo p (in fact there are \phi(p-1) many). There are various strategies for finding primitive roots of a prime modulus, other than simply trying all candidates (discussed here and here). In this post we discuss how to obtain primitive roots of moduli that are power of odd primes. Starting from a given primitive root modulo p, we show how to get a primitive root modulo p^2. Next, starting with a primitive root modulo p^2, we show how to get a primitive root modulo p^n for any integer n \ge 3. It follows from these results that there exist primitive roots modulo any power of any odd prime number. The results discussed in this post build up to the primitive root theorem. See the following posts for the rest of the proof of the primitive root theorem.

___________________________________________________________________________________________________________________

Example

We start the discussion with an example. There are two primitive roots for the odd prime modulus p=7. They are 3 and 5. Are 3 and 5 also primitive roots modulo 7^2=49?

Note that \phi(49)=\phi(7^2)=7(7-1)=42. One way to find out is to check

    3^x \ (\text{mod} \ 49) and 5^x \ (\text{mod} \ 49)

by letting x be the proper divisors of 42. The proper divisors of 42 are 1, 2, 3, 6, 7, 14, and 21. However, it is not necessary to check all 7 proper divisors of 42.

There is a better check that requires only checking 3 divisors of 42. According to a previous post, we only need to check the following:

    \displaystyle 3^{\frac{\phi(49)}{2}} \ (\text{mod} \ 49) and \displaystyle 3^{\frac{\phi(49)}{3}} \ (\text{mod} \ 49) and \displaystyle 3^{\frac{\phi(49)}{7}} \ (\text{mod} \ 49)

    \displaystyle 5^{\frac{\phi(49)}{2}} \ (\text{mod} \ 49) and \displaystyle 5^{\frac{\phi(49)}{3}} \ (\text{mod} \ 49) and \displaystyle 5^{\frac{\phi(49)}{7}} \ (\text{mod} \ 49)

To see why this works, see Check #3 in the post More about checking for primitive roots. Even this better check can be improved.

According to Lemma 1 discussed below, all we need to do is to check the following:

    3^6 \ (\text{mod} \ 49) and 5^6 \ (\text{mod} \ 49)

If the congruence \not \equiv 1 \ (\text{mod} \ 49), then the number in question is a primitive root modulo 49. Otherwise, it is not a primitive root. Note that the exponent is \phi(7)=6.

We have 3^6 \equiv 43 \ (\text{mod} \ 49) and 5^6 \equiv 43 \ (\text{mod} \ 49). So the two numbers 3 and 5 are primitive roots modulo 49.

Remarks
In general, given that a is a primitive root modulo p, to check whether a is a primitive root modulo p^2, all we need to do is to check a^{p-1} \ (\text{mod} \ p^2). If it is \not \equiv 1 \ (\text{mod} \ p^2), then a is a primitive root modulo p^2. Otherwise, it is not a primitive root modulo p^2.

What makes this works is that if a is a primitive root modulo p, the order of a modulo p^2 can only be p-1 or p(p-1)=\phi(p^2) (see Lemma 1 below). When a^{p-1} \not \equiv 1 \ (\text{mod} \ p^2), the order of a modulo p^2 is not p-1 and is p(p-1)=\phi(p^2), which means that a is a primitive root modulo p^2. When a^{p-1} \equiv 1 \ (\text{mod} \ p^2), the order of a modulo p^2 is p-1, which means that a is not a primitive root modulo p^2.

Furthermore, in the case that the order of a modulo p^2 is p-1, even though the number a is not a primitive root modulo p^2, the number a+p is a primitive root modulo p^2 (see Theorem 2 below).

As an example, 31 \equiv 3 \ (\text{mod} \ 7). So 31 is also a primitive root modulo 7. But 31^6 \equiv 1 \ (\text{mod} \ 49). So 31 is not a primitive root modulo 49. However 38 is a primitive root modulo 49. Note that 38^6 \equiv 15 \ (\text{mod} \ 49). For more details, see Theorem 2 below.

Theorem 4 below states that any primitive root modulo p^2 is also a primitive root modulo any higher power of p. For example, 38 is a primitive root modulo 7^n for any n \ge 3.

___________________________________________________________________________________________________________________

Square of an Odd Prime

We now show that there exist primitive roots modulo the square of an odd prime (Theorem 2 below). The starting point is that there is a given primitive root modulo a prime number (the existence is proved in Primitive roots of prime moduli).

    Lemma 1

      Let p be a prime number. Let g be a primitive root modulo p. Let t be the order of g modulo p^2. Then either t=p or t=p(p-1).

Proof of Lemma 1
Immediately we know that t \ \lvert \ \phi(p^2)=p(p-1). Furthermore, it follows that g^t \equiv 1 \ (\text{mod} \ p^2), which implies g^t=1+p^2 y for some integer y. In turn this equation implies that g^t \equiv 1 \ (\text{mod} \ p). We also have we have p-1 \ \lvert \ t since the order of g modulo p is p-1.

So we have p-1 \ \lvert \ t and t \ \lvert \ p(p-1). In words, the integer t is at least p-1 and at the same time t is a divisor of p(p-1). The only possibilities of t are t=p-1 or t=p(p-1). \blacksquare

    Theorem 2

      Let p be an odd prime number. Let a be a primitive root modulo p. Then either a or a+p is a primitive root modulo p^2. Thus there exist primitive roots modulo p^2.

Proof of Theorem 2
Let k be the order of a modulo p^2. By Lemma 1, we have k=p-1 or k=\ p(p-1). Note that \phi(p^2)=p(p-1). Thus if it is the case that k=\ p(p-1), then a is a primitive root modulo p^2. So in the remainder of the proof, we assume that k=p-1.

Since a+p \equiv a \ (\text{mod} \ p), the number a+p is a primitive root modulo p. Let h be the order of a+p modulo p^2. Using Lemma 1 again, there are only two possibilities for h, namely h=p-1 or h=\ p(p-1)=\phi(p^2). If we can show that the case h=p-1 is not possible, then a+p must be a primitive root modulo p^2. To this end, we show (a+p)^{p-1} \not \equiv 1 \ (\text{mod} \ p).

Using the binomial theorem, we expand (a+p)^{p-1} as follows:

    \displaystyle (a+p)^{p-1}=a^{p-1}+\binom{p-1}{1}a^{p-2}p+\binom{p-1}{2}a^{p-3}p^2+\binom{p-1}{3}a^{p-4}p^3 +\cdots+p^{p-1}

All terms except the first two terms are divisible by p^2. Recall that we assume above that k=p-1 (the order of a modulo p^2). So in the following derivation, we use a^{p-1} \equiv 1 \ (\text{mod} \ p^2).

    \displaystyle \begin{aligned} (a+p)^{p-1}&\equiv a^{p-1}+\binom{p-1}{1}a^{p-2}p \ (\text{mod} \ p^2) \\&\equiv a^{p-1}+(p-1)a^{p-2}p \ (\text{mod} \ p^2) \\&\equiv a^{p-1}+p^2 a^{p-2}-p a^{p-2} \ (\text{mod} \ p^2)  \\&\equiv 1+0-p a^{p-2} \ (\text{mod} \ p^2) \\&\equiv 1-p a^{p-2} \ (\text{mod} \ p^2) \end{aligned}

We now need to show that 1-p a^{p-2} \not \equiv 1 \ (\text{mod} \ p^2). Suppose that 1-p a^{p-2} \equiv 1 \ (\text{mod} \ p^2). Then we have -p a^{p-2} \equiv 0 \ (\text{mod} \ p^2).

Because a^{p-1} \equiv 1 \ (\text{mod} \ p^2), a^{p-2} is the multiplicative inverse of a modulo p^2. Now multiply both sides of -p a^{p-2} \equiv 0 \ (\text{mod} \ p^2) by a, we get -p \equiv 0 \ (\text{mod} \ p^2), which implies p is divisible by p^2, a contradiction. So (a+p)^{p-1} \equiv 1-p a^{p-2} \not \equiv 1 \ (\text{mod} \ p^2). Thus h=p-1 is not possible. Then h=p(p-1), which means that a+p is a primitive root modulo p^2. \blacksquare

___________________________________________________________________________________________________________________

Higher Powers of an Odd Prime

In this section, we show that there exist primitive roots modulo any higher power of an odd prime.

    Lemma 3

      Let p be an odd prime number. If g be a primitive root modulo p^2, then g is also a primitive root modulo p.

Proof of Lemma 3
Let g be a primitive root modulo p^2 where p is an odd prime number. To show that g be a primitive root modulo p, we use the following result:

Let t be a prime divisor of \phi(p)=p-1. Then t is a prime divisor of \phi(p^2)=p(p-1). By the result indicated by (*), we have \displaystyle g^{\frac{p(p-1)}{t}} \not \equiv 1 \ (\text{mod} \ p^2). It follows that \displaystyle g^{\frac{p-1}{t}} \not \equiv 1 \ (\text{mod} \ p). Thus by the result indicated by (*), g is a primitive root modulo p. Note that if \displaystyle g^{\frac{p-1}{t}} \equiv 1 \ (\text{mod} \ p), then \displaystyle (g^{\frac{p-1}{t}})^p \equiv 1 \ (\text{mod} \ p). \blacksquare

    Theorem 4

      Let p is an odd prime number. Let a be a primitive root modulo p^2. Then a is a primitive root modulo p^{j} for all integers j \ge 3.

Proof of Theorem 4
Note that \phi(p^2)=p(p-1). Thus a^{p-1} \not \equiv 1 \ (\text{mod} \ p^2). By Lemma 3, the number a is also a primitive root modulo p. Thus a^{p-1} \equiv 1 \ (\text{mod} \ p). Thus a^{p-1}=1+wp for some integer w. It is the case that w cannot be a multiple of p. Otherwise, we would have a^{p-1} \equiv 1 \ (\text{mod} \ p^2). We will use that fact that w cannot be a multiple of p at a later step in the proof.

Let j be any integer with j \ge 3. Note that \phi(p^j)=p^{j-1}(p-1). We establish the following three claims.

Claim 1
Let k be the order of a modulo p^j. The possibilities for k are p^n(p-1) where n=1,2,3,\cdots,j-1.

Claim 2
It is the case that k \ne p^{j-2}(p-1). To establish this, we show \displaystyle a^{p^{j-2}(p-1)} \not \equiv 1 \ (\text{mod} \ p^j).

Claim 3
It is the case that k \ne p^{n}(p-1) for n=1,2,3,\cdots,j-3.

Once the three claims are established, the order of a modulo p^j must be \phi(p^j)=p^{j-1}(p-1). Hence a is a primitive root modulo p^j.

Claim 3 follows from Claim 2. Note that if \displaystyle a^{p^{n}(p-1)} \equiv 1 \ (\text{mod} \ p^j) where n=0,1,2,3,\cdots,j-3, then we can raise both sides of the equation by an appropriate power of p to get \displaystyle a^{p^{j-2}(p-1)} \equiv 1 \ (\text{mod} \ p^j).

Proof of Claim 1. Since k is the order, we have \displaystyle a^{k} \equiv 1 \ (\text{mod} \ p^j), which leads to \displaystyle a^{k} \equiv 1 \ (\text{mod} \ p^2). These two congruences imply k \ \lvert \ \phi(p^j)=p^{j-1}(p-1) and p(p-1) \ \lvert \ k.

Thus k is at least p(p-1) and divides p^{j-1}(p-1). With p being a prime, k can only be p(p-1), p^{2}(p-1), \cdots, p^{j-1}(p-1).

Proof of Claim 2.
We show that \displaystyle a^{p^{j-2}(p-1)} \not \equiv 1 \ (\text{mod} \ p^j). With a^{p-1}=1+wp derived at the beginning of the proof, we have \displaystyle a^{p^{j-2}(p-1)}=(1+wp)^{p^{j-2}}. Upon using the binomial theorem to expand \displaystyle (1+wp)^{p^{j-2}}, we see that all terms except the first two are divisible by p^j. We can discard them since we take congruence modulo p^j. The following shows the first two terms:

    \displaystyle \begin{aligned} a^{p^{j-2}(p-1)}&= (1+wp)^{p^{j-2}}  \\&\equiv 1+p^{j-2} wp \ (\text{mod} \ p^j) \\&\equiv 1+wp^{j-1} \ (\text{mod} \ p^j) \end{aligned}

We claim that 1+wp^{j-1} \not \equiv 1 \ (\text{mod} \ p^j). Suppose 1+wp^{j-1} \equiv 1 \ (\text{mod} \ p^j). Then wp^{j-1} \equiv 0 \ (\text{mod} \ p^j), which implies wp^{j-1}=p^j c for some integer c. Cancelling out p^{j-1}, we have w=p c, which contradicts the fact that w cannot be a multiple of p. So 1+wp^{j-1} \not \equiv 1 \ (\text{mod} \ p^j). This establish Claim 3 and the theorem is also established. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

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}