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}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s