# Defining Primitive Root

In this post, we define the notion of primitive root and prove some elementary results. Instead of jumping right into the definition, we take a leisurely approach by first looking at some of the related basic notions.

___________________________________________________________________________________________________________________

Setting Up the Scene

Two positive integers $a$ and $b$ are relatively prime if they do not share any prime factors, i.e., their greatest common divisor is one (the only positive integer that can divide both numbers is one). For example, $a=9$ and $b=14$ are relatively prime, as are $a=9$ and $b=35$. If $a$ and $b$ are relatively prime, we also say that $a$ is relatively prime to $b$ or $b$ is relatively prime to $a$. Our notation for greatest common divisor is $\text{GCD}(a,b)$.

In working with modular arithmetic where the modulus is the positive integer $m$, every integer is congruent modulo $m$ to exactly one number in the set $\left\{0,1,2,\cdots,m-1 \right\}$. The numbers in this set are called the least residues modulo $m$. In doing modulus $m$ calculation, for some purposes we only need to reduce the result to one number in this set. For convenience, we use the notation $\mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}$.

An even more interesting set is the set of all integers $a$ in $\mathbb{Z}_m$ such that $a$ and the modulus $m$ are relatively prime. To facilitate the discussion, we describe this set as follows:

\displaystyle \begin{aligned} (\mathbb{Z}_m)^*&=\left\{a \in \mathbb{Z}_m: a \text{ is relatively prime to } m \right\} \\&=\left\{a \in \mathbb{Z}_m:\text{GCD}(a,m) =1 \right\} \end{aligned}

When the modulus $m$ is a prime number, $(\mathbb{Z}_m)^*=\left\{1,2,\cdots,m-1 \right\}$, the non-zero elements of $\mathbb{Z}_m$. The following theorem gives some indication why $(\mathbb{Z}_m)^*$ is an interesting set, which provides alternative characterizations of $(\mathbb{Z}_m)^*$.

Theorem 1

Let $a$ be an integer in $\mathbb{Z}_m$. The following conditions are equivalent.

1. $\text{GCD}(a,m)=1$.
2. There is a $b \in \mathbb{Z}_m$ such that $a \cdot b \equiv 1 \ (\text{mod} \ m)$.
3. Some positive power of $a$ modulo $m$ is $1$, i.e., $a^n \equiv 1 \ (\text{mod} \ m)$ for some positive integer $n$.

$\text{ }$

The proof of Theorem 1 can be found in the post Euler’s phi function, part 1.

The Euler’s phi function, denoted by $\phi(m)$, is the number of integers $a$ where $0 \le a \le m-1$ such that $a$ and the modulus $m$ are relatively prime. In light of the above discussion, $\phi(m)$ is the number of elements in the set $(\mathbb{Z}_m)^*$. It is also the case that $\phi(m)$ is the number of elements in $\mathbb{Z}_m$ that satisfies any one of the three conditions in Theorem 1.

___________________________________________________________________________________________________________________

Defining Primitive Root

When we are interested in the power of a number being one congruence modulo $m$, according to Theorem 1, the base has to be a number that is relatively prime to the modulus. We have already come across two such situations – Fermat’s little theorem and its generalization, Euler’s theorem.

Theorem 2 (Fermat’s little theorem)

Let the modulus $m$ be a prime number. Then $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any integer $a$ that is relatively prime to $m$.

$\text{ }$

Theorem 3 (Euler’s theorem)

It is the case that $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ for any integer $a$ that is relatively prime to $m$.

$\text{ }$

Theorem 2 follows from Theorem 3, which is proved in the post Euler’s phi function, part 1.

Definitions
We now define the notion of primitive root. Let $a$ be an integer in $\mathbb{Z}_m$ that is relatively prime to the modulus $m$. Based on the above theorems, $a^k \equiv 1 \ (\text{mod} \ m)$ for some positive integer $k$. By the order of $a$ modulo $m$, we mean the least positive integer $k$ such that $a^k \equiv 1 \ (\text{mod} \ m)$. The number $a$ is a primitive root modulo $m$ if the order of $a$ modulo $m$ is the number $\phi(m)$.

By Theorem 3, the order of $a$ modulo $m$ is always $\le \phi(m)$. We will see below that the order always divides $\phi(m)$ (see Theorem 4).

One comment. The notions of order and primitive roots are defined above for integers in $\mathbb{Z}_m$. In actuality, the two notations can be defined for all positive integers. It is just that we are interested in finding primitive roots among the residues, i.e., the elements of the set $\mathbb{Z}_m$. In some cases, it will be helpful to think of orders of numbers outside of $\mathbb{Z}_m$ and think of numbers outside of $\mathbb{Z}_m$ as primitive roots (e.g. in the proof of Theorem 6 below).

Suppose that the modulus $m$ is a prime number. Fermat’s little theorem tells us that $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any $a$ that is relatively prime to $m$. Is $m-1$ the only exponent for which the power of $a$ is one? Take $m=11$. The following table gives the powers of $a$ modulus $m=11$ where $1 \le a \le 10$.

$\displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9&a^{10} \\\text{ }&\text{ }&\text{ } \\ 1&1&1&1&1&1&1&1&1&1 \\ 2&4&8&5&10&9&7&3&6&1 \\ 3&9&5&4&1&3&9&5&4&1 \\ 4&5&9&3&1&4&5&9&3&1 \\ 5&3&4&9&1&5&3&4&9&1 \\ 6&3&7&9&10&5&8&4&2&1 \\ 7&5&2&3&10&4&6&9&8&1 \\ 8&9&6&4&10&3&2&5&7&1 \\ 9&4&3&5&1&9&4&3&5&1 \\ 10&1&10&1&10&1&10&1&10&1 \end{bmatrix}$

The above table shows that for $a=2,6,7,8$, the number $10$ is the least exponent for which the power of $a$ is one. In other words, the order for these $a$ is $\phi(11)=10$. The numbers $a=2,6,7,8$ are primitive roots modulo $m=11$. The other values of $a$ are not primitive roots. The order for $a=1$ is $1$. The order for $a=10$ is $2$. The order for $a=3,4,5,9$ is $5$.

Note that in the above table, for the numbers $a$ that are primitive roots, the set $\left\{a^1,a^2,a^3,\cdots,a^{\phi(11)} \right\}$ equals the set $\left\{1,2,3,\cdots,10 \right\}$. So a primitive root generates by powering all the least residues that are relatively prime to the modulus.

Let’s look at a modulus that is not prime. Take $m=10$. The following table gives the powers of $a$ modulus $m=10$ where $1 \le a \le 9$.

$\displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9 \\\text{ }&\text{ }&\text{ } \\ 1&1&1&1&1&1&1&1&1 \\ 2&4&8&6&2&4&8&6&2 \\ 3&9&7&1&3&9&7&1&3 \\ 4&6&4&6&4&6&4&6&4 \\ 5&5&5&5&5&5&5&5&5 \\ 6&6&6&6&6&6&6&6&6 \\ 7&9&3&1&7&9&3&1&7 \\ 8&4&2&6&8&4&2&6&8 \\ 9&1&9&1&9&1&9&1&9 \end{bmatrix}$

Note that $\phi(10)=4$ since $(\mathbb{Z}_{10})^*=\left\{1,3,7,9 \right\}$ is the set of all the least residues that are relatively prime to $m=10$. In terms of powers of $a$, we should only focus on $\left\{1,3,7,9 \right\}$. The following is the reduced table.

$\displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9 \\\text{ }&\text{ }&\text{ } \\ 1&1&1&1&1&1&1&1&1 \\ 3&9&7&1&3&9&7&1&3 \\ 7&9&3&1&7&9&3&1&7 \\ 9&1&9&1&9&1&9&1&9 \end{bmatrix}$

Note that $a^4 \equiv 1 \ (\text{mod} \ 10)$ for all four $a$. But only $a=3,7$ are primitive roots modulo $m=10$.

Also note that in the above table, for the numbers $a$ that are primitive roots, the set $\left\{a^1,a^2,a^3,a^4 \right\}$ equals the set $\left\{1,3,7,9 \right\}$. So a primitive root generates by powering all the least residues that are relatively prime to the modulus.

Not all moduli have primitive roots. Take $m=8$. The least residues that are relatively prime to $m=8$ are the set $\left\{1,3,5,7 \right\}$. Note that $a^2 \equiv 1 \ (\text{mod} \ 8)$ for every $a$ in this set. Thus no number $a$ in this set can have order = $\phi(8)=4$.

___________________________________________________________________________________________________________________

Elementary Results

One observation can be made about the above small tables for $m=11$ and $m=10$ is that all exponents for which the power of $a$ is one are the multiples of the order. We have the following theorem.

Theorem 4

Let $a$ be an integer where $0 \le a \le m-1$ such that $a$ is relatively prime to the modulus $m$. Suppose $k$ is the order of the number $a$ modulo $m$. Then $a^n \equiv 1 \ (\text{mod} \ m)$ if and only if $n$ is a multiple of $k$.

Proof of Theorem 4

$\Longleftarrow$
This direction is clear. If $n=q \cdot k$ for some integer $q$, then $a^n=(a^k)^q \equiv 1 \ (\text{mod} \ m)$.

$\Longrightarrow$
Suppose that $a^n \equiv 1 \ (\text{mod} \ m)$. By the division algorithm, we have $n=q \cdot k+r$ for some integers $q$ and $r$ where $0 \le r . We have the following:

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

Since $r and $a^r \equiv 1 \ (\text{mod} \ m)$, it must be the case that $r=0$, implying that $n=q \cdot k$. $\blacksquare$

We have the following corollary.

Corollary 5

Let $a$ be an integer where $0 \le a \le m-1$ such that $a$ is relatively prime to the modulus $m$. Suppose $k$ is the order of the number $a$ modulo $m$. Then $\phi(m)$ is a multiple of $k$.

Another observation from the above small tables is that a primitive root, through powering, is a generator of the least residues that are relatively prime to the modulus.

Theorem 5

Let $a$ be an integer where $0 \le a \le m-1$ such that $a$ is relatively prime to the modulus $m$. The following conditions are equivalent.

1. The number $a$ is a primitive root modulo $m$.
2. The set $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$, where each $a^j$ is considered as the least residues modulo $m$, is precisely the set $(\mathbb{Z}_m)^*$.

$\text{ }$

Recall that $(\mathbb{Z}_m)^*$ is the set of all $a \in \mathbb{Z}_m=\left\{0,1,2,3,\cdots,m-1 \right\}$ such that $a$ is relatively prime to $m$.

Proof of Theorem 5

$1 \Longrightarrow 2$
Suppose that the number $a$ is a primitive root modulo $m$. The first step in showing condition 2 is to show that the $\phi(m)$ numbers in the set $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ are distinct congruent modulo $m$. Then it follows that their least residues modulo $m$ are distinct too.

Suppose $a^j \equiv a^i \ (\text{mod} \ m)$ where $i,j \le \phi(m)$. We want to show that $i=j$. Suppose $i. Then cancel out $a^i$ on both sides of the equation since $a^i$ is relatively prime to $m$. We have $a^{j-i} \equiv 1 \ (\text{mod} \ m)$. But $j-i<\phi(m)$. Since $a$ is a primitive root modulo $m$, we cannot have $a^{j-i} \equiv 1 \ (\text{mod} \ m)$. So it must be the case that $j=i$. So if $a^j \equiv a^i \ (\text{mod} \ m)$, then $i=j$. Equivalently, if $i \ne j$, $a^j \not \equiv a^i \ (\text{mod} \ m)$. Thus the least residues modulo $m$ of the values in $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ are distinct too.

Since $a^i$ is relatively prime to $m$, its least residue is also relatively prime to $m$. Now the least residues modulo $m$ of the values in $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ consist of $\phi(m)$ numbers inside $(\mathbb{Z}_m)^*$, which is also a set of $\phi(m)$ many numbers. So the two sets must equal.

$2 \Longrightarrow 1$
We show the contrapositive of $2 \Longrightarrow 1$. Suppose that the order of $a$ modulo $m$ is $j$ where $1 \le j<\phi(m)$. So $a^j \equiv 1 \ (\text{mod} \ m)$ and $a^{j+1} \equiv a \ (\text{mod} \ m)$. So $a$ and $a^{j+1}$ are two elements in the set $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ that are congruent to each other. This means that the least residues of $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ have less than $\phi(m)$ many values. In other words, the number $a$, through powering, cannot generate all the least residues that are relatively prime to the modulus $m$. $\blacksquare$

The following theorem and corollary give the number of primitive root modulo $m$ as long as it is known that there is a primitive root modulo $m$.

Theorem 6

Let $a$ be a primitive root modulo $m$. Then for any positive integer $k$, the least residue of $a^k$ is a primitive root modulo $m$ if and only if $k$ is relatively prime to $\phi(m)$.

Proof of Theorem 6

$\Longrightarrow$
Suppose that $k$ is not relatively prime to $\phi(m)$. So $d=\text{GCD}(k,\phi(m))>1$. Then we have:

$\displaystyle (a^k)^{\frac{\phi(m)}{d}}=(a^{\phi(m)})^{\frac{k}{d}} \equiv 1 \ (\text{mod} \ m)$

With $\displaystyle b=\frac{\phi(m)}{d}<\phi(m)$ and $(a^k)^b \equiv 1 \ (\text{mod} \ m)$, it follows that $a^k$ is not a primitive root modulo $m$. Hence the least residue of $a^k$ modulo $m$ is also not a primitive root. Thus if the least residue of $a^k$ is a primitive root modulo $m$, it must be that $\text{GCD}(k,\phi(m))=1$.

$\Longleftarrow$
Suppose $\text{GCD}(k,\phi(m))=1$. Let $\alpha$ be the order of $a^k$ modulo $m$. By the definition of order, $a^{k \cdot \alpha}=(a^k)^\alpha \equiv 1 \ (\text{mod} \ m)$. Based on the fact that the order of $a$ modulo $m$ is $\phi(m)$, we have $\phi(m) \ \lvert \ k \cdot \alpha$ (also using Theorem 4). Since $\text{GCD}(k,\phi(m))=1$, it must be the case that $\phi(m) \ \lvert \ \alpha$.

On the other hand, $(a^k)^{\phi(m)}=(a^{\phi(m)})^k \equiv 1 \ (\text{mod} \ m)$. Using the fact that the order of $a^k$ is $\alpha$ (and using Theorem 4), $\alpha \ \lvert \ \phi(m)$.

With $\phi(m) \ \lvert \ \alpha$ and $\alpha \ \lvert \ \phi(m)$, it follows that $\alpha = \phi(m)$. This implies that $a^k$ is a primitive root modulo $m$, and so is its least residue modulo $m$. $\blacksquare$

Corollary 7

Suppose that there exists a primitive root modulo $m$. Then there are exactly $\phi(\phi(m))$ many primitive roots modulo $m$.

Proof of Corollary 7

Let $a$ be a primitive root modulo $m$. By Theorem 6, the least residue of $a^k$ is a primitive roots modulo $m$ if and only if $k$ is relatively prime to the number $\phi(m)$. There are precisely $\phi(\phi(m))$ many such numbers $k$.

Furthermore, according to Theorem 5, the least residues of the values in $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ are all distinct. Thus the least residues of the powers $a^k$ for the $\phi(\phi(m))$ many $k$ are primitive roots modulo $m$. $\blacksquare$

___________________________________________________________________________________________________________________

An Algorithm

The theorems and corollaries in this post form an elementary algorithm for finding primitive roots of a modulus (if one is known to exist). The algorithm is described in the post An elementary algorithm for finding primitive roots. An example is given in the post Finding Primitive Roots.

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$