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

Advertisements

Two Proofs of Wilson’s Theorem

In this post, we give two proofs of Wilson’s theorem. The second proof uses the notion of primitive roots. The following is the statement of the theorem.

    Theorem 1 (Wilson’s Theorem)

      Let p be a positive integer. Then p is a prime number if and only if (p-1)! \equiv -1 \ (\text{mod} \ p).

An alternative way of stating Wilson’s theorem is that p is a prime number if and only if (p-1)! +1 is divisible by p.

___________________________________________________________________________________________________________________

One Proof

We use \text{GCD}(a,b) to denote the greatest common divisor of the positive integers a and b. We use the following lemma.

    Lemma 2

      Let m be a prime number. Then the congruence equation x^2 \equiv 1 \ (\text{mod} \ m) has exactly two solutions. They are x=1,m-1.

Proof of Lemma 2

It is straightforward to see that 1^2 \equiv 1 \ (\text{mod} \ m) and (m-1)^2 \equiv 1 \ (\text{mod} \ m). It remains to show that x=1,m-1 are the only two solutions. To that end, we show that any solution of x^2 \equiv 1 \ (\text{mod} \ m) must be one of these.

Let t be a solution of the above congruence equation. This means that t^2 \equiv 1 \ (\text{mod} \ m) and 0 \le t \le m-1. So m \ \lvert \ (t^2-1)=(t+1)(t-1). By Euclid’s lemma, either m \ \lvert (t+1) or m \ \lvert (t-1). The first case gives t \equiv -1 \ (\text{mod} \ m) and the second case gives t \equiv 1 \ (\text{mod} \ m). Since 0 \le t \le m-1, the first congruence means that t=p-1 and the second congruence means that t=1. \blacksquare

    Lemma 3

      Let a be a positive integer with 0 \le a \le m-1. Then the following conditions are equivalent.

      1. The number a and the modulus m are relatively prime, i.e., \text{GCD}(a,m)=1.
      2. There exists a unique integer b with 0 \le b \le m-1 such that ab \equiv 1 \ (\text{mod} \ m). In other words, the number a has a multiplicative inverse modulo m.

Lemma 3 is proved in a previous post (see Theorem 1 in the post Euler’s phi function, part 1).

Proof of Theorem 1 (first proof)

\Longleftarrow
Suppose p is a positive integer that is not prime. Then p has a factor among the integers 2,3,\cdots,p-1. Thus d=\text{GCD}((p-1)!,p)>1 (i.e. (p-1)! and p are not relatively prime).

We claim that (p-1)! \not \equiv -1 \ (\text{mod} \ p). Suppose that (p-1)! \equiv -1 \ (\text{mod} \ p). Then we have (p-1)! \cdot x+ p \cdot y=-1 for some integers x and y. Since d divides the left-hand side of the equation, d \ \lvert \ -1. But d=\text{GCD}((p-1)!,p)>1. So (p-1)! \not \equiv -1 \ (\text{mod} \ p).

We have proved that if p is not prime, then (p-1)! \not \equiv -1 \ (\text{mod} \ p). Equivalently if (p-1)! \equiv -1 \ (\text{mod} \ p), then p is prime.

\Longrightarrow
Suppose p is prime. For each a \in \left\{1,2,3,\cdots,p-1 \right\}, a and p are relatively prime. By Lemma 3, for each such a, there exists a unique b in \left\{1,2,3,\cdots,p-1 \right\} such that ab \equiv 1 \ (\text{mod} \ p).

By Lemma 2, the congruence equation x^2 \equiv 1 \ (\text{mod} \ p) has exactly two solutions, namely x=1,p-1. Thus a=1,p-1 are the only numbers in \left\{1,2,3,\cdots,p-1 \right\} for which a and its inverse b are the same. For each a \in \left\{2,3,\cdots,p-2 \right\}, a \ne b.

The number p-3 is an even integer. There are p-3 many numbers in the set \left\{2,3,\cdots,p-2 \right\}. Based on the discussion in the preceding paragraph, the set \left\{2,3,\cdots,p-2 \right\} consists of \displaystyle \frac{p-3}{2} many pairs of numbers such that the product of each pair is \equiv 1 \ (\text{mod} \ p). Thus we have

    2 \cdot 3 \cdots (p-2) \equiv 1 \ (\text{mod} \ p)

We can also write (p-2)! \equiv 1 \ (\text{mod} \ p). Multiply p-1 on both sides of the equation, we have (p-1)! \equiv p-1 \ (\text{mod} \ p). Since p-1 \equiv -1 \ (\text{mod} \ p), we have (p-1)! \equiv -1 \ (\text{mod} \ p). \blacksquare

___________________________________________________________________________________________________________________

Another Proof

To carry out the following proof, we use the theorem that every prime modulus has a primitive root. A primitive root for a given prime modulus m is a positive integer g with 1 \le g \le m-1 such that the least positive exponent satisfying the equation g^x \equiv 1 \ (\text{mod} \ m) is m-1.

Another property of primitive roots that is used in the following proof is that for a given primitive root g for a given prime modulus m, the powers of g would generate the elements of the set \left\{1,2,3,\cdots,p-1 \right\} (these are the least residues that are relatively prime to the prime modulus m).

Basic properties of primitive roots are discussed in the post called Defining Primitive Root.

Proof of Theorem 1 (second proof)

We prove the direction that if p is prime, then (p-1)! \equiv -1 \ (\text{mod} \ p).

\Longrightarrow
If p=2, it is clear that (p-1)! \equiv -1 \ (\text{mod} \ p). Suppose p is an odd prime. Then there exists a primitive root modulo p. Let g be one such. Because p is prime, every integer x in the interval 1 \le x \le p-1 is relative prime to p. One property of a primitive root for the prime modulus p is that the powers of g would generate the integers in the interval 1 \le x \le p-1. Specifically we have the following set equality

    \left\{r_1,r_2,r_3,\cdots,r_{p-1} \right\}=\left\{1,2,3,\cdots,p-1 \right\}

where each r_j is a least residue modulo p, i.e., 0 \le r_j \le p-1 and r_j \equiv g^j \ (\text{mod} \ p). As a result of the above set equality, we have the following congruence equality.

    g^1 g^2 g^3 \cdots g^{p-1} \equiv r_1 \cdot r_2 \cdot r_3 \cdots r_{p-1} \equiv (p-1)! \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

The exponents in the left-hand side of the above congruence equality can be summed as follows:

    \displaystyle 1+2+3+\cdots+p-1=\frac{(p-1)p}{2}

The congruence equality (1) can be further simplified as follows:

    \displaystyle g^{\frac{(p-1)p}{2}} \equiv (p-1)! \ (\text{mod} \ p)

It follows from Fermat’s theorem that g^{p-1} \equiv 1 \ (\text{mod} \ p). Thus the number \displaystyle g^{\frac{p-1}{2}} satisfies the congruence equation x^2 \equiv 1 \ (\text{mod} \ p). By Lemma 2, x^2 \equiv 1 \ (\text{mod} \ p) has exactly 2 solutions, namely x=1 or x=p-1. So we have the following are two possibilities for \displaystyle g^{\frac{p-1}{2}}.

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

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

But the first one is not possible since g is a primitive root modulo p. So the second congruence is true. It follows that

    \displaystyle (p-1)! \equiv g^{\frac{(p-1)p}{2}}=(-1)^p \equiv -1 \equiv  \ (\text{mod} \ p)

The above derivation concludes the proof of the theorem. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Primitive roots of prime moduli

In this post we show that if m is prime, then there exists a primitive root modulo m. It follows that there exist \phi(m-1) primitive roots modulo m where \phi is Euler’s phi function.

For a basic discussion of the notion of primitive roots, see Defining Primitive Root. A basic discussion of the phi function is found in the post Euler’s phi function, part 1 and in the post Euler’s phi function, part 2.

In modular arithmetic, not all moduli have primitive roots. For example, for the modulus m=8, the least residues that are relatively prime are a=1,3,5,7. Thus \phi(8)=4. For each one of these values of a, a^2 \equiv 1 \ (\text{mod} \ 8). Thus every one of them has order 2 < \phi(8). Thus there are no primitive roots modulo m=8. We prove the following results.

    Theorem 1

      Let p be a prime number. Then there exists a primitive root modulo p.

    \text{ }

    Theorem 2

      Let p be a prime number. Then there are exactly \phi(m-1) many primitive roots modulo m.

\text{ }

Theorem 1 is the main theorem in this post. Theorem 2 follows from Theorem 1 and from a result proved in a previous post. The previous result is that if there exists a primitive root modulo m (not necessarily prime), then there exist exactly \phi(\phi(m)) many primitive roots modulo m (see Theorem 6 and Corollary 7 in Defining Primitive Root). Since Theorem 1 provides the existence of a primitive root, Theorem 2 follows from Theorem 1 and from the previous result and from the fact that \phi(p)=p-1 for any prime number.

___________________________________________________________________________________________________________________

Proving the Main Theorem

Our proof of the existence of a primitive root of any prime modulus uses only elementary techniques. Most of the results we need are developed here in this post. The first result is proved in a previous post (see Theorem 4 in Defining Primitive Root).

    Lemma 3

      Let a be an integer with 0 \le a \le m-1 such that a is relaively prime to the modulus m. Let k be the order of a modulo m. Then the following two conditions are equivalent for any positive integer n.

      1. The congruence condition a^n \equiv 1 \ (\text{mod} \ m) holds.
      2. The number k is a divisor of n.

The second result is that of polynomial congruence. Let f(x) be a polynomial with integer coefficients. In the next lemma, we are interested in solving the polynomial congruence equation f(x) \equiv 0 \ (\text{mod} \ m).

    Lemma 4

      Let m be a prime number. Let f(x) be a polynomial of degree n. Then the equation

        f(x) \equiv 0 \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

      \text{ }

      has at most n solutions.

Proof of Lemma 4

Suppose f(x)=a_n x^n +a_{n-1} x^{n-1} + \cdots+a_2 x^2+a_1 x + a_0 where a_n \not \equiv 0 \ (\text{mod} \ m). We prove the lemma by induction on the degree n.

Suppose n=1. We have f(x)=a_1 x +a_0 \equiv 0 \ (\text{mod} \ m). Since m is prime and a_1 \not \equiv 0 \ (\text{mod} \ m), the coefficient a_1 must be relatively prime to m. Then the congruence equation a_1 x +a_0 \equiv 0 \ (\text{mod} \ m) has exactly one solution. The number of solutions of a linear congruence is the same as the greatest common divisor of the coefficient of x and the modulus m (see Theorem 2 in the post Solving Linear Congruences).

Suppose the lemma is true for polynomials of degree n-1. Consider two cases – either equation (1) has no solution or equation (1) has a solution. If the first case is true, then the conclusion of the lemma is true.

Suppose the second case is true. Suppose b is a solution to equation (1). It follows that f(b) \equiv 0 \ (\text{mod} \ m) and that b is a least residue modulo m.

Our next goal is to factor the polynomial f(x) into a product of a first degree polynomial and a polynomial of degree n-1. To this end, note that x-b is a factor of x^w-b^w for w=1,2,3,\cdots,n. We have the following derivation

    \displaystyle \begin{aligned} f(x)&\equiv f(x)-f(b) \\&\equiv a_n (x^n-b^n) +a_{n-1} (x^{n-1}-b^{n-1}) + \cdots+a_2 (x^2-b^2)+a_1 (x-b) \\&\equiv (x-b) \cdot h(x) \ (\text{mod} \ m) \end{aligned}

where h(x) is a polynomial of degree n-1.

Whenever f(x) \equiv 0 \ (\text{mod} \ m), we have m \ \lvert \ (x-b) \cdot h(x). Using the fact that m is prime and Euclid’s lemma, either m \ \lvert \ (x-b) or m \ \lvert \ h(x). In terms of congruence, either x-b \equiv 0 \ (\text{mod} \ m) or h(x) \equiv 0 \ (\text{mod} \ m). The first congruence has exactly one solution. By induction hypothesis, the second congruence has at most n-1 solutions. Together, equation (1) has at most n solutions. \blacksquare

    Lemma 5

      Let m be a prime number. If d \ \lvert \ (p-1), then the congruence equation x^d \equiv 1 \ (\text{mod} \ m) has exactly d many solutions.

Proof of Lemma 5

Suppose d \ \lvert \ (p-1). Fermat’s little theorem tells us that x^{m-1}-1 \equiv 0 \ (\text{mod} \ m) has exactly m-1 solutions, namely 1,2,3,\cdots,m-1. We can factor the polynomial x^{m-1}-1 as follows:

    g(x)=x^{m-1}-1=(x^d-1) \cdot (x^{m-1-d}+x^{m-1-2d}+x^{m-1-3d}+\cdots+x^{d}+1)

Let t(x)=(x^{m-1-d}+x^{m-1-2d}+x^{m-1-3d}+\cdots+x^{d}+1). Whenever g(x) \equiv 0 \ (\text{mod} \ m), m \ \lvert \ g(x)=x^{m-1}-1=(x^d-1) \cdot t(x). By Euclid’s lemma, m \ \lvert \ (x^d-1) or m \ \lvert \ t(x). In terms of congruence, x^d \equiv 1 \ (\text{mod} \ m) or t(x) \equiv 0 \ (\text{mod} \ m).

By Lemma 4, the congruence t(x) \equiv 0 \ (\text{mod} \ m) has at most m-1-d solutions. Since x^{m-1}-1 \equiv 0 \ (\text{mod} \ m) has exactly m-1 solutions, the congruence equation x^d \equiv 1 \ (\text{mod} \ m) has at least d many solutions.

By Lemma 4, the congruence equation x^d \equiv 1 \ (\text{mod} \ m) has at most d solutions. Thus x^d \equiv 1 \ (\text{mod} \ m) has exactly d many solutions. \blacksquare

We need one more lemma before proving Theorem 1.

    Lemma 6

      Let a and b be integers with 0 \le a,b \le m-1. Let \alpha be the order of a modulo m. Let \beta be the order of b modulo m.

      Suppose that \alpha and \beta are relatively prime. Then \alpha \cdot \beta is the order of a \cdot b modulo m.

Proof of Lemma 6

Let \gamma be the order of a \cdot b modulo m. We show that \gamma=\alpha \beta. The following derivation shows that \alpha \ \lvert \ \gamma.

    1 \equiv 1^\beta \equiv ((ab)^\gamma)^\beta =(ab)^{\gamma \beta}=(a)^{\gamma \beta} (b)^{\gamma \beta}=(a)^{\gamma \beta} (b^{\gamma})^{\beta} \equiv a^{\gamma \beta} \ (\text{mod} \ m)

Since a^{\gamma \beta} \equiv 1 \ (\text{mod} \ m), we have \alpha \ \lvert \ \gamma \beta (by Lemma 3). Since \alpha and \beta are relatively prime, \alpha \ \lvert \ \gamma. By a symmetrical argument, it can also be shown that \beta \ \lvert \ \gamma.

Since \alpha \ \lvert \ \gamma, we have \gamma=\alpha \cdot t for some integer t. Since \beta \ \lvert \alpha \cdot t, it follows that \beta \ \lvert t (Euclid’s lemma). So t=\beta \cdot z for some integer z. Now \gamma=\alpha \cdot \beta \cdot z. This means that \alpha \beta \ \lvert \ \gamma.

On the other hand, we have \gamma \ \lvert \alpha \beta. This follows from the following derivation and from Lemma 3.

    (ab)^{\alpha \beta}=(a^\alpha)^\beta \cdot (b^\beta)^\alpha \equiv 1 \ (\text{mod} \ m)

It follows that \gamma= \alpha \beta. \blacksquare

Remark
Lemma 6 indicates that the orders of two numbers are multiplicative as long as the two orders are relatively prime. As a corollary of Lemma 6, it follows that the order of a product of finitely many numbers (for the same modulus) is the product of the individual orders provided that the orders are pairwise relatively prime. This fact will be used in the proof of Theorem 1 below.

Proof of Theorem 1

We start off with a prime factorization of the number p-1.

    \displaystyle p-1=w_1^{e_1} \cdot w_2^{e_2} \cdot w_3^{e_3} \cdots w_n^{e_n}

In the above factorization, the numbers w_i are distinct prime numbers and the exponents e_i \ge 1.

For each i, it is clear that w_i^{e_i} \ \lvert \ (p-1). By Lemma 5, the congruence equation

    \displaystyle x^{w_i^{e_i}} \equiv 1 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

has exactly w_i^{e_i} many solutions. Note that the w_i^{e_i} many solutions are integers in the interval 0 \le x \le p-1. Furthermore, the order modulo p of each of these solutions to (2) is a divisor of w_i^{e_i} (by Lemma 3).

In fact, from Lemma 3, we can say that for any integer x in the interval 0 \le x \le p-1, the number x is a solution of equation (2) if and only if the order modulo p of x is a divisor of w_i^{e_i}. We have the following claim.

Claim
For each i, we claim that there exists at least one integer a_i in the interval 0 \le x \le p-1 such that the order of a_i modulo p is w_i^{e_i}.

To see the above claim, the congruence equation

    \displaystyle x^{w_i^{e_i-1}} \equiv 1 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

has exactly w_i^{e_i-1} many solutions in the interval 0 \le x \le p-1 (using Lemma 5). Furthermore, the order of each of the solutions of (3) is a divisor of w_i^{e_i-1}.

In fact, from Lemma 3, we can also say that for any integer x in the interval 0 \le x \le p-1, the number x is a solution of equation (3) if and only if the order modulo p of x is a divisor of w_i^{e_i-1}.

Note that the solutions of (3) are also solutions of (2). This is clear since we know that divisors of w_i^{e_i-1} are also divisors of w_i^{e_i}.

Thus there are w_i^{e_i}-w_i^{e_i-1} many of the solutions to (2) that are not solutions to equation (3). Pick one such solution and call it a_i. Let k be the order of a_i modulo p. There are three possibilities for k:

    k \le w_i^{e_i-1} \ \ \ \ \ w_i^{e_i-1}<k<w_i^{e_i} \ \ \ \ \  k=w_i^{e_i}

Since a_i is a solution to (2), the number k is a divisor of w_i^{e_i}. Note that there are no divisors of w_i^{e_i} within the interval w_i^{e_i-1}<y<w_i^{e_i} since w_i is a prime number. So w_i^{e_i-1}<k<w_i^{e_i} is not possible.

Since a_i is not a solution to (3), the number k is not a divisor of w_i^{e_i-1}. This means that k \le w_i^{e_i-1} is not possible. Since w_i is prime, k must be a power of w_i. Since k must be a power of w_i, if k \le w_i^{e_i-1}, k is then a divisor of w_i^{e_i-1}.

So the only possibility is that k=w_i^{e_i}. This establishes the above claim.

Let g=a_1 \cdot a_2 \cdots a_n. The primitive root modulo p we are looking for is either g if g<p or the least residue of g if g \ge p.

According to the above claim, the order modulo p of a_i is w_i^{e_i}. Clearly w_i^{e_i} and w_j^{e_j} are relatively prime for i \ne j. As a corollary of Lemma 6, the order of the product g=a_1 \cdot a_2 \cdots a_n is the products of w_i^{e_i}, namely p-1. Thus g=a_1 \cdot a_2 \cdots a_n or its least residue modulo p is a primitive root. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

An elementary algorithm for finding primitive roots

In the previous post Finding Primitive Roots, we demonstrate one approach for finding all primitive roots of a prime modulus. In this post, we summarize the ideas behind that example.

Throughout this discussion m is a positive integer that is used as the modulus for modular arithmetic, and a is assumed to be a positive integer that is relatively prime to m such that 0 \le a \le m-1.

According to Fermat’s little theorem, if the modulus m is prime, then a^{m-1} \equiv 1 \ (\text{mod} \ m). If the modulus is relaxed to include non-prime integers as well, then we have Euler’s theorem which states that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m) where \phi(m) is Euler’s phi function. For any modulus m, \phi(m) is simply the numbers of possible values of a that are relatively prime to m. For example, \phi(m)=10 if m=11 and \phi(m)=4 if m=10.

So it is always the case that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m). Another way to say this is that the number \phi(m) is always a solution to the following congruence equation.

    \displaystyle a^x \equiv 1 \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

With this above discussion in mind, we define the notion of order. The order of a modulo m is the least positive integer solution to the congruence equation (1).

Furthermore, the number a is said to be a primitive root modulo m if the least positive integer solution to (1) is \phi(m).

Note that even though the notions of order and primitive root are defined here for integers a that are relatively prime to m with 0 \le a \le m-1, the definitions are also valid for positive a outside the range 0 \le a \le m-1. Relaxing the definitions can make some proofs go easier (e.g. Theorem 2 below).

___________________________________________________________________________________________________________________

An Approach in Finding Primitive Roots

We now summarize the ideas discussed in the previous post Finding Primitive Roots.

Recall that a is a positive integer less than m that is relatively prime to m. How do we check if a is a primitive root? On the face of it, we need to check that no positive integer less than \phi(m) is a solution to equation (1). It turns out that we only need to check positive integers less than \phi(m) that are divisors of \phi(m). We have the following theorem.

    Theorem 1

      The following conditions are equivalent.

      1. The number a is a primitive root modulo m.
      2. Every positive divisor k of \phi(m) with k < \phi(m) is not a solution of the congruence equation (1).

\text{ }
If we know that there exists a primitive root for a modulus, the followng theorem tells us how to find the other primitive roots.

    Theorem 2

      Suppose the number a is a primitive root modulo m. Then there are exactly \phi(\phi(m)) many primitive roots modulo m. They are obtained by finding the least residues of the numbers a^j where the exponents j are taken from the following set.

        \left\{j: 1 \le j \le \phi(m) \text{ and } j \text{ is relatively prime to } \phi(m) \right\} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

Thus the above two theorems taken together form an algorithm for finding primitve roots of a modulus (if one is known to exist to begin with). We can use Theorem 1 to find a primitive root. Once we have found one, we can raise it to exponents that are relatively prime to the number \phi(m) to find the remaining primitive roots. Since there are \phi(\phi(m)) many positive integers that are less than \phi(m) and relatively prime to \phi(m), there are \phi(\phi(m)) many primitive roots modulo m (if one exists).

Before proving the theorems, let’s look at a quick example.

For m=11, \phi(11)=10. The candidates for primitive roots modulo m=11 are in the set \left\{2,3,4,\cdots,10 \right\}. The divisors of \phi(11)=10 are 1,2,5. According to Theorem 1, we only need to raise these numbers to exponents that are divisors of \phi(11)=10.

Note that 2^1 \equiv 2 \ (\text{mod} \ 11), 2^2 \equiv 4 \ (\text{mod} \ 11) and 2^5 \equiv 10 \ (\text{mod} \ 11). Thus a=2 is a primitive root modulo m=11.

The positive integers that are less than \phi(11)=10 and that are relatively prime to \phi(11)=10 are 1, 3, 7, 9. So there are four primitive roots modulo m=11. They are:

    \displaystyle \begin{aligned} \text{ }&2^1 \equiv 2 \ (\text{mod} \ 11) \\&2^3 \equiv 8 \ (\text{mod} \ 11) \\&2^7 \equiv 7 \ (\text{mod} \ 11) \\&2^9 \equiv 6 \ (\text{mod} \ 11) \end{aligned}

___________________________________________________________________________________________________________________

Proof of Theorems

Proof of Theorem 1

The direction 1 \Longrightarrow 2 is clear. If a is a primitive root modulo m, then by definition, no positive integer less than \phi(m) can be a solution to the congruence equation (1).

2 \Longrightarrow 1
Let h be the order of a modulo m. The key to the proof is that h must be a divisor of \phi(m) (see Theorem 4 and Corollary 5 in the post Defining Primitive Root). For the sake of completeness, we provide the proof here.

Since h is the least positive solution of the congruence equation (1), h \le \phi(m). Using the division algorithm, we have \phi(m)=q \cdot h+r for some integers q and r where 0 \le r <h. We have the following calculation.

    1 \equiv a^{\phi(m)}=(a^h)^q \cdot a^r \equiv (1)^q \cdot a^r \equiv a^r \ (\text{mod} \ m)

So we have a^r \equiv 1 \ (\text{mod} \ m) and 0 \le r <h. Since h is the least positive solution of (1), the only possibility is that r=0. Hence \phi(m)=q \cdot h and h is a divisor of \phi(m).

Now back to the proof for 2 \Longrightarrow 1. We claim that h=\phi(m), implying that a is a primitive root modulo m. If h<\phi(m), then h is a positive divisor of \phi(m) with h<\phi(m) such that h is a solution of the congruence equation (1) (i.e. the condition 2 does not hold). Thus if condition 2 holds, condition 1 must hold. \blacksquare

Proof of Theorem 2
Theorem 2 is the combined result of Theorem 6 and Corollary 7 in the post Defining Primitive Root. To make this post as self contained as possible, we repeat the proof, showing just the essential parts.

We do need one theorem from the previous post Defining Primitive Root. Let w be a positive integer that is relatively prime to the modulus m. Let k be the order of w modulo m. Theorem 4 in this post states that for any , w^n \equiv 1 \ (\text{mod} \ m) if and only if k \ \lvert \ n.

There are exactly \phi(\phi(m)) many elements in the above set indicated by (2). So there are these many powers of a. The first thing to show is that the powers a^j are all distinct congruent modulo m. Hence their least residues are also distinct.

To see this, suppose a^j \equiv a^i \ (\text{mod} \ m) where i, j \le \phi(m) with i \le j. We want to show i=j. Suppose that i<j. Since a^i is relatively prime to m, we can cancel out a^i on both sides and obtain a^{j-i} \equiv 1 \ (\text{mod} \ m). Since j-i<\phi(m) and a is a primitive root modulo m, a^{j-i} \not \equiv 1 \ (\text{mod} \ m). So i=j. Thus if i \ne j, then a^j \not \equiv a^i \ (\text{mod} \ m).

The next thing to show is that a^j is a primitive root modulo m for any j in the above set (2). Suppose j is one such element of the set (2). Then j and \phi(m) are relatively prime.

Let h be the order of a^j modulo m. We have a^{j \cdot h}=(a^h)^j \equiv 1 \ (\text{mod} \ m). Since a is a primitive root modulo m, it follows that \phi(m) \ \lvert \ j \cdot h (according Theorem 4 in Defining Primitive Root). Since \phi(m) and j are relatively prime, \phi(m) \ \lvert \ h.

On the other hand, (a^j)^{\phi(m)}=(a^{\phi(m)})^j \equiv 1 \ (\text{mod} \ m). Since h is the order of a^j, it follows that h \ \lvert \ \phi(m) (also using Theorem 4 in Defining Primitive Root).

With \phi(m) \ \lvert \ h and h \ \lvert \ \phi(m), we have h=\phi(m). Thus a^j is a primitive root modulo m and so is its least residue. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}