# 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 . 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}$

# 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 . 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 . 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. 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}$

# 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}$

# Congruence Arithmetic and Fast Powering Algorithm

In some cryptography applications such as RSA algorithm, it is necessary to compute $\displaystyle a^w$ modulo $m$ where the power $w$ and the modulus $m$ are very large numbers. We discuss and demonstrate an efficient algorithm that can handle such calculations. This general algorithm has various names such as fast powering algorithm, square-and-multiply algorithm and exponentiation by squaring.

The problem at hand is to compute $a^w \ (\text{mod} \ m)$. The naïve approach is to compute by repeatedly multiplying by $a$ and reducing modulo $m$. When the power $w$ is large (e.g. an integer with hundreds of digits), this approach is difficult or even impossible (given the current technology). In this post we discuss an alternative that is known as the fast powering algorithm.

___________________________________________________________________________________________________________________

An Example

Compute $1286^{1171}$ modulo $1363$.

Using the naïve approach described earlier, we would do something like the following:

\displaystyle \begin{aligned} 1286^{1171} &=(1286 \cdot 1286) \cdot 1286^{1269} \equiv 477 \cdot 1286^{1269} \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&=(477 \cdot 1286) \cdot 1286^{1268} \equiv 72 \cdot 1286^{1268} \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&=(72 \cdot 1286) \cdot 1286^{1267} \equiv 1271 \cdot 1286^{1267} \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\text{ }\cdots \\&\text{ }\cdots \\&\text{ }\cdots \end{aligned}

In this naïve approach, we would multiply two numbers at a time and then reduce the result modulo $1363$ so that the numbers do not get too large. The above example would involve $1170$ multiplications and then $1170$ divisions for the reduction modulo $1363$. Great difficulty comes when the power is not $1171$ and instead is an integer with hundreds or even thousands of digits.

Note that in the above naïve approach, the power is reduced by one at each step. In the fast power alternative, the power comes down by an exponent of two in each step. The idea is to use the binary expansions of the exponent $1171$ to transform the computation of $1286^{1171}$ into a series of squarings and multiplications. To this end, we write $1171$ as a sum of powers of two as follows:

$(1) \ \ \ \ \ \ \ \ \ 1171=2^0+2^1+2^4+2^7+2^{10}$

Next we compute $1286^{2^0},1286^{2^1},1286^{2^2},1286^{2^3},\cdots,1286^{2^{10}}$ modulo $1363$. Note that each term is the square of the preceding term, hence the word square in the name “square-and-multiply”. To make it easier to see, we put the results in the following table.

$\displaystyle (2) \ \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ i }&\text{ }&1286^{2^i}&\text{ }&\text{squaring}&\text{ }&\text{modulo } 1363&\text{ }&\text{ } \\\text{ }&\text{ }&\text{ } \\ 0&\text{ }&1286^{2^0}&\text{ }&\text{ }&\text{ }&\equiv 1286&\text{ }&* \\ 1&\text{ }&1286^{2^1}&\text{ }&\equiv 1286^2&\text{ }&\equiv 477&\text{ }&* \\ 2&\text{ }&1286^{2^2}&\text{ }&\equiv 477^2&\text{ }&\equiv 1271&\text{ }&\text{ } \\ 3&\text{ }&1286^{2^3}&\text{ }&\equiv 1271^2&\text{ }&\equiv 286&\text{ }&\text{ } \\ 4&\text{ }&1286^{2^4}&\text{ }&\equiv 286^2&\text{ }&\equiv 16&\text{ }&* \\ 5&\text{ }&1286^{2^5}&\text{ }&\equiv 16^2&\text{ }&\equiv 256&\text{ }&\text{ } \\ 6&\text{ }&1286^{2^6}&\text{ }&\equiv 256^2&\text{ }&\equiv 112&\text{ }&\text{ } \\ 7&\text{ }&1286^{2^7}&\text{ }&\equiv 112^2&\text{ }&\equiv 277&\text{ }&* \\ 8&\text{ }&1286^{2^8}&\text{ }&\equiv 277^2&\text{ }&\equiv 401&\text{ }&\text{ } \\ 9&\text{ }&1286^{2^9}&\text{ }&\equiv 401^2&\text{ }&\equiv 1330&\text{ }&\text{ } \\ 10&\text{ }&1286^{2^{10}}&\text{ }&\equiv 1330^2&\text{ }&\equiv 1089&\text{ }&* \end{bmatrix}$

Note that the rows marked by * in the above table are the results that we need. In the above table, there are 10 multiplications for the squarings and 10 divisions for the reduction modulo $1363$.

Now $1286^{1171}$ is calculated as follows:

\displaystyle \begin{aligned} (3) \ \ \ \ \ \ \ \ \ 1286^{1171} &=1286^{2^0} \cdot 1286^{2^1} \cdot 1286^{2^4} \cdot1286^{2^7} \cdot 1286^{2^{10}} \\&\equiv 1286 \ \ \cdot 477 \ \ \ \ \cdot 16 \ \ \ \ \ \cdot 277 \ \ \ \ \cdot 1089 \ \ \text{mod} \ 1363 \\&\equiv 72 \ \ \ \ \cdot 16 \ \ \ \ \ \cdot 277 \ \ \ \ \cdot 1089 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\equiv 1152 \ \ \cdot 277 \ \ \cdot 1089 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\equiv 162 \ \ \cdot 1089 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\equiv 591 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \end{aligned}

We have the answer $1286^{1171} \equiv 591 \ (\text{mod} \ 1363)$. The calculation in (3) is the step that gives the word “multiply” in the name “square-and-multiply”. In this step, we multiply the results obtained from the previous step.

We now tally up the amount of work that is done. The calculation in table (2) requires 10 multiplications for the squaring and 10 divisions for the reduction modulo $1363$. The calculation in (3) requires 4 multiplications and 4 divisions for the reduction modulo $1363$. Together, there are 14 multiplications and 14 divisions. In contrast, the naïve approach would require 1170 multiplications and 1170 divisions!

___________________________________________________________________________________________________________________

Description of Fast Powering Algorithm

To compute $a^w \equiv (\text{mod} \ m)$, use the following steps. The following steps correspond with the steps in the above example.

Step (1)

Compute the binary expansions of the power $w$.

$\displaystyle w=C_0 +C_1 \cdot 2^{1}+C_2 \cdot 2^{2}+\cdots+C_{k-1} \cdot 2^{k-1}+C_k \cdot 2^{k}$

where each $j$, $C_j=0$ or $C_j=1$. In particular, we assume that $C_k=1$.

Step (2)

For each $j=0,1,2,\cdots,k$, compute $\displaystyle a^{2^j} \equiv A_j$ modulo $m$. Note that each $\displaystyle a^{2^j} \equiv A_j$ is the result of squaring the previous term $\displaystyle a^{2^{j-1}} \equiv A_{j-1}$. We arrange the calculation in the following table.

$\displaystyle (2) \ \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ i }&\text{ }&a^{2^i}&\text{ }&\text{squaring}&\text{ }&\text{modulo } m&\text{ }&\text{ } \\\text{ }&\text{ }&\text{ } \\ 0&\text{ }&a^{2^0}&\text{ }&\text{ }&\text{ }&A_0\equiv a&\text{ }&\text{ } \\ 1&\text{ }&a^{2^1}&\text{ }&\equiv A_0^2&\text{ }&\equiv A_1&\text{ }&\text{ } \\ 2&\text{ }&a^{2^2}&\text{ }&\equiv A_1^2&\text{ }&\equiv A_2&\text{ }&\text{ } \\ 3&\text{ }&a^{2^3}&\text{ }&\equiv A_2^2&\text{ }&\equiv A_3&\text{ }&\text{ } \\ \text{ }&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ } \\ \text{ }&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ } \\ \text{ }&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ } \\ k-1&\text{ }&a^{2^{k-1}}&\text{ }&\equiv A_{k-2}^2&\text{ }&\equiv A_{k-1}&\text{ }&\text{ } \\ k&\text{ }&a^{2^k}&\text{ }&\equiv A_{k-1}^2&\text{ }&\equiv A_k&\text{ }&\text{ } \end{bmatrix}$

Step (3)

Compute $a^w \equiv (\text{mod} \ m)$ using the following derivation.

\displaystyle \begin{aligned}(3) \ \ \ \ \ \ \ \ \ a^{w}&=a^{C_0 +C_1 \cdot 2^{1}+C_2 \cdot 2^{2}+\cdots+C_{k-1} \cdot 2^{k-1}+C_k \cdot 2^{k}} \\&=a^{C_0} \cdot a^{C_1 \cdot 2^{1}} \cdot a^{C_2 \cdot 2^{2}} \cdots a^{C_{k-1} \cdot 2^{k-1}} \cdot a^{C_k \cdot 2^{k}} \\&=a^{C_0} \cdot (a^{2^{1}})^{C_1} \cdot (a^{2^{2}})^{C_2} \cdots (a^{2^{k-1}})^{C_{k-1}} \cdot (a^{2^{k}})^{C_k} \\&\equiv A_0^{C_0} \cdot (A_1)^{C_1} \cdot (A_2)^{C_2} \cdots (A_{k-1})^{C_{k-1}} \cdot (A_k)^{C_k} \ \ \ \ \ (\text{mod} \ m) \end{aligned}

The last line in (3) is to be further reduced modulo $m$. In the actual calculation, only the terms with $C_j=1$ need to be used.

We now establish an upper bound for the number multiplications. Step (2) requires $k$ multiplications and $k$ divisions to reduce modulo $m$. Step (3) requires at most $k$ many multiplications since some of the $C_j$ many be zero. Step (3) also requires at most $k$ many divisions to reduce modulo $m$. So altogether, the algorithm requires at most $2k$ multiplications and $2k$ divisions.

From Step (1), we know that $\displaystyle 2^k \le w$. Take natural log of both sides, we have $\displaystyle k \le \frac{\text{ln}(w)}{\text{ln}(2)}$ and $\displaystyle 2 \cdot k \le \frac{2 \cdot \text{ln}(w)}{\text{ln}(2)}$. So the fast powering algorithm requires at most

$\displaystyle \frac{2 \cdot \text{ln}(w)}{\text{ln}(2)}$

many multiplications and at most that many divisions to compute the congruence calculation $a^w \equiv (\text{mod} \ m)$.

For example, when the power $w=2^{127}-1$, which is a Mersenne prime, which has 39 digits. Now $w \approx 2^{127}$. By the above calculation, the fast powering algorithm would take at most 254 multiplications and at most 254 divisions to do the power congruence computation.

The fast powering calculations demonstrated in this post can be done by hand (using a hand-held calculator). In real applications, such calculations should of course be done in a computer.

___________________________________________________________________________________________________________________

Another Example

Use the fast power algorithm to show that

$4030^{2657} \equiv 21144 \ (\text{mod} \ 55049)$

$21144^{79081} \equiv 4030 \ (\text{mod} \ 55049)$

Note that one congruence is encryption and the other one is decryption. We demonstrate the second calculation.

In doing the second calculation, we use a little bit of help from Fermat’s little theorem. The modulus $55049$ is a prime number. So $21144^{55048} \equiv 1 \ (\text{mod} \ 55049)$. Thus we have:

$21144^{79081}=21144^{24033} \cdot 21144^{55048} \equiv 21144^{24033} \ (\text{mod} \ 55049)$

Step (1)

The binary expansions of $24033$ are:

$24033=2^0+2^5+2^6+2^7+2^8+2^{10}+2^{11}+2^{12}+2^{14}$

Step (2)

Compute $21144^{2^j}$ modulo $55049$ for each $j$. The computation is displayed in the following table. The rows with * are the results that we need for Step (3).

$\displaystyle \begin{bmatrix} \text{ i }&\text{ }&21144^{2^i}&\text{ }&\text{squaring}&\text{ }&\text{modulo } 55049&\text{ }&\text{ } \\\text{ }&\text{ }&\text{ } \\ 0&\text{ }&21144^{2^0}&\text{ }&\text{ }&\text{ }&\equiv 21144&\text{ }&* \\ 1&\text{ }&21144^{2^1}&\text{ }&\equiv 21144^2&\text{ }&\equiv 15807&\text{ }&\text{ } \\ 2&\text{ }&21144^{2^2}&\text{ }&\equiv 15807^2&\text{ }&\equiv 48887&\text{ }&\text{ } \\ 3&\text{ }&21144^{2^3}&\text{ }&\equiv 48887^2&\text{ }&\equiv 41483&\text{ }&\text{ } \\ 4&\text{ }&21144^{2^4}&\text{ }&\equiv 41483^2&\text{ }&\equiv 7549&\text{ }&\text{ } \\ 5&\text{ }&21144^{2^5}&\text{ }&\equiv 7549^2&\text{ }&\equiv 11686&\text{ }&* \\ 6&\text{ }&21144^{2^6}&\text{ }&\equiv 11686^2&\text{ }&\equiv 41076&\text{ }&* \\ 7&\text{ }&21144^{2^7}&\text{ }&\equiv 41076^2&\text{ }&\equiv 40975&\text{ }&* \\ 8&\text{ }&21144^{2^8}&\text{ }&\equiv 40975^2&\text{ }&\equiv 11174&\text{ }&* \\ 9&\text{ }&21144^{2^9}&\text{ }&\equiv 11174^2&\text{ }&\equiv 7144&\text{ }&\text{ } \\ 10&\text{ }&21144^{2^{10}}&\text{ }&\equiv 7144^2&\text{ }&\equiv 6313&\text{ }&* \\ 11&\text{ }&21144^{2^{11}}&\text{ }&\equiv 6313^2&\text{ }&\equiv 53542&\text{ }&* \\ 12&\text{ }&21144^{2^{12}}&\text{ }&\equiv 53542^2&\text{ }&\equiv 14040&\text{ }&* \\ 13&\text{ }&21144^{2^{13}}&\text{ }&\equiv 14040^2&\text{ }&\equiv 46180&\text{ }&\text{ } \\ 14&\text{ }&21144^{2^{14}}&\text{ }&\equiv 46180^2&\text{ }&\equiv 49189&\text{ }&* \end{bmatrix}$

Step (3)

Compute $21144^{79081} \ (\text{mod} \ 55049)$.

\displaystyle \begin{aligned} 21144^{24033} &=21144^{2^0} \cdot 21144^{2^5} \cdot 21144^{2^6} \cdot 21144^{2^7} \cdot 21144^{2^{8}} \cdot 21144^{2^{10}} \cdot 21144^{2^{11}} \cdot 21144^{2^{12}} \cdot 21144^{2^{14}} \\&\equiv 21144 \cdot 11686 \cdot 41076 \cdot 40975 \cdot 11174 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \text{mod} \ 55049 \\&\equiv 25665 \cdot 40975 \cdot 11174 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 22328 \cdot 11174 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 11004 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 51463 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 9300 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 50821 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 4030 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \end{aligned}

___________________________________________________________________________________________________________________

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

# The Fundamental Theorem of Arithmetic

This post discusses and proves the fundamental theorem of arithmetic.

Finding the prime factors of a large integer is no easy feat. For example, the ninth Fermat number $F_9=2^{2^9}+1$ has 155 digits and has the following three prime factors:

$a=\text{2,424,833}$

$b=\text{7,455,602,825,647,884,208,337,395,736,200,454,918,783,366,342,657}$

\displaystyle \begin{aligned} c=&\text{ 741,640,062,627,530,801,524,787,141,901,937,474,059,940,781,097,519} \\&\text{ 023,905,821,316,144,415,759,504,705,008,092,818,711,693,940,737} \end{aligned}

These prime factors have 9 digits, 49 digits and 99 digits, respectively. They were published in 1993 after lengthy calculations involving approximately 700 workstations and a supercomputer using a number field sieve algorithm (see [1]). If the project were to be done today, it could certainly be done much faster and more efficiently with the current state of the art in supercomputing. However, the project will still be no trivial feat.

The following 617-digit integer is a product of two prime numbers and has yet to be factored by anyone (or any computer or any sets of computers). According RSA Laboratories, barring fundamental algorithmic or computing advances, the above number or other similarly sized number is expected to stay unfactored in the decades to come. For more background about this large number, see see RSA challenge number and RSA factoring challenge.

25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357

Though the implementation of prime factorization may be difficult or even impossible for large numbers, the fundamental theorem of arithmetic guarantees that any positive integer can be expressed uniquely as a product of prime numbers. The fundamental theorem of arithmetic is an essential theorem in number theory. In this post, we present of proof of this fundamental theorem.

___________________________________________________________________________________________________________________

The Fundamental Theorem of Arithmetic

The theorem has two parts – the existence and the uniqueness of the prime factorization. The existence part is relatively easy. We first prove the existence part. We use Euclid’s lemma to prove the uniqueness part.

Lemma 1

Any integer $n>1$ has a prime divisor.

Proof

Let $n$ be an integer with $n>1$. If $n$ is prime, then it has a prime divisor, namely $n$. So assume $n$ is not prime. Then $n=h \cdot k$ for some positive integers $h$ and $k$ smaller than $n$.

Now consider the set $D$ of all positive integer divisors of $n$. The set $D$ is nonempty since $h$ and $k$ belong to this set. The set $D$ is also a finite set since an integer can only have finitely many integer divisors. Every finite set of real numbers has a smallest element. Let $p$ be the least element of $D$.

The $p$ must be a prime number. If not, $p$ would have a positive divisor $q$ that is smaller than $p$. Then $q$ is also a positive divisor of $n$, contradicting that $p$ is the least element of $D$. $\blacksquare$

Lemma 2

Any integer $n>1$ is a product of prime numbers.

Proof

We prove by induction. The lemma is certainly true for $n=2$. Suppose the lemma is true for all positive integers $k$ where $k.

If $n$ is prime, then we are done. Assume $n$ is not prime. Then $n=h \cdot k$ for some positive integers $h$ and $k$ smaller than $n$. By induction hypothesis, both $h$ and $k$ are product of prime numbers. We can conclude that $n$ is also a product of prime numbers. $\blacksquare$

Euclid’s Lemma

If $p$ is a prime number and $p \ \lvert (a \cdot b)$, then $p \ \lvert \ a$ or $p \ \lvert \ b$.

Proof of Euclid’s Lemma is found in this post. As a corollary of Euclid’s Lemma, we have the following lemma.

Lemma 3

If $p$ is a prime number and $p \ \lvert (a_1 \cdot a_2 \cdots a_n)$, then $p \ \lvert \ a_i$ for some $i$.

Proof

We prove by induction. The case for $n=2$ is the Euclid’s Lemma. Assume that the lemma is true for $n$ where $n \ge 2$. Suppose that $p \ \lvert (a_1 \cdot a_2 \cdots a_n \cdot a_{n+1})$. By Euclid’s lemma, we have $p \ \lvert (a_1 \cdot a_2 \cdots a_n)$ or $p \ \lvert \ a_{n+1}$. In the first case, the induction hypothesis tells us that $p \ \lvert \ a_i$ for some $i$ with $1 \le i \le n$. In the second case $p \ \lvert \ a_{n+1}$. The two cases together tell us that $p \ \lvert \ a_i$ for some $i$ with $1 \le i \le n+1$.

Since the validity of the lemma for $n$ implies the validity of the lemma for $n+1$ and since the lemma is true for $n=2$, we now know that the lemma is true for all integers $n>1$. This establishes the lemma. $\blacksquare$

Fundamental Theorem of Arithmetic

Any interger $n>1$ can be expressed uniquely as a product of prime numbers.

Proof

Let $n$ be an integer with $n>1$. The existence of the prime factors of $n$ is established by Lemma 2. We now show there is only one prime factorization for $n$. We would like to point out that order of the prime factors is not important. For example, we consider $2 \times 2 \times 3 \times 11$ and $11 \times 3 \times 2 \times 2$ as the same factorization for the integer $132$.

Suppose that $n=p_1 \cdot p_2 \cdots p_h$ and $n=q_1 \cdot q_2 \cdots q_k$ are prime factorizations of the integer $n$. We show that each $p_i$ is identical to some $q_j$ and each $q_s$ is identical to some $p_t$. This implies that the prime numbers $p_1,p_2,\cdots,p_h$ are simply a rearrangement of $q_1,q_2,\cdots,q_k$ such that the only difference for the two factorizations is in the order of the factors.

Note that $p_1 \cdot (p_2 \cdots p_h)=q_1 \cdot q_2 \cdots q_k$. Thus $p_1$ divides $q_1 \cdot q_2 \cdots q_k$, or we write $p_1 \ \lvert \ q_1 \cdot q_2 \cdots q_k$. By Lemma 3, $p_1 \ \lvert \ q_j$ for some $j$. Since they are prime, $p_1=q_j$. Then cancel out $p_1$ on both side of the equation, we have

$p_2 \cdot (p_3 \cdots p_h)=q_1 \cdot q_2 \cdots q_{j-1} \cdot q_{j+1} \cdots q_k$

Note that $p_2$ divides the right-hand side of the above equation. By Lemma 3, $p_2 \ \lvert \ q_w$ for some $w$. Continue in this same manner, we see that each $p$ is identical to some $q$. Furthermore, $h \le k$. Otherwise, there would be some $p_i$ left after we cancel out all the $q_j$, leading to the situation that the product of several prime numbers is equal to one.

By interchanging $p$ with $q$, the same argument will also show that each $q$ is identical to some $p$. Furthermore, $k \le h$. Thus we have $h=k$ and that the two factorizations are really just rearrangement of each other. $\blacksquare$

Comment

From the fundamental theorem of arithmetic, it follows that any positive integer greater than one can be expressed uniquely in the following way:

$p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdots p_m^{e_m}$

where $m$ is a positive integer and each $e_i \ge 1$. Such representation of an integer is called a prime-power decomposition. For example, $7056=2^4 \cdot 3^2 \cdot 7^2$.

___________________________________________________________________________________________________________________

Reference

1. Lenstra, A. K., Lenstra, H. W., Manasse, M. S., Pollard, J. M. The Factorization of the Ninth Fermat Number, Mathematiics of Computation, Volume 61, Number 203, July 1993, Pages 319-349.

___________________________________________________________________________________________________________________

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

# Euclid’s Lemma

This post presents a proof of a lemma that is called Euclid’s lemma, which is one of the fundamental properties of prime numbers. Euclid’s lemma is the statement that if a prime number divides a product of two integers, it must divide one of the factors.

This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

We first state all the tools that we need. The notation $a \ \lvert \ b$ refers to the condition that $a$ divides $b$. The notation $\text{GCD}(a,b)$ refers to the greatest common divisor (GCD) of $a$ and $b$.

___________________________________________________________________________________________________________________

Extended Euclidean Algorithm

Let $a$ and $b$ be integers. Let $d$ be the greatest common divisor of $a$ and $b$. Then there exist integers $x$ and $y$ such that $ax+by=d$.

The extended Euclidean algorithm is discussed in this post.

___________________________________________________________________________________________________________________

Lemma 1

If $d \ \lvert \ a \cdot b$ and $\text{GCD}(d,a)=1$, then $d \ \lvert \ b$.

Proof of Lemma 1

Suppose that $d \ \lvert \ a \cdot b$ and $\text{GCD}(d,a)=1$. According to the extended Euclidean algorithm, for some integers $x$ and $y$, we have $ax+dy=1$. Multiplying both sides by $b$, we have:

$abx+dby=b$

Since $d$ divides each term in the left-hand side of this equation, $d \ \lvert \ b$. $\blacksquare$

___________________________________________________________________________________________________________________

Euclid’s Lemma

If $p$ is a prime number and $p \ \lvert (a \cdot b)$, then $p \ \lvert \ a$ or $p \ \lvert \ b$.

Proof

If $p \ \lvert \ a$, then we are done. So assume $p \not \lvert \ a$, which implies that $\text{GCD}(p,a)=1$. If $\text{GCD}(p,a)>1$, $\text{GCD}(p,a)=p$, which implies that $p \ \lvert \ a$. Note that the only positive divisors of $p$ are $1$ and $p$. By Lemma 1, $p \ \lvert \ b$. $\blacksquare$

Comment

We would like to point out that the assumption that $p$ is prime is essential in Euclid’s lemma. Note that $8 \ \lvert \ (4 \cdot 4)$ and $8 \not \lvert \ 4$.

___________________________________________________________________________________________________________________

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

# The Division Algorithm

The division algorithm is the conceptual underpinning of many concepts in number theory (congruence arithmetic is one example). In this post, we present a proof of the division algorithm and connect it to one important property of congruence.

This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

___________________________________________________________________________________________________________________

The Division Algorithm

The following is the statement of the division algorithm.

Let $a$ and $b$ be positive integers. Then there exist unique integers $q$ and $r$ such that

$a = q \cdot b + r$

where $0 \le r .

Let $A$ be the set $A=\left\{a-jb: j=0,1,2,3,\cdots \right\}$. Let $A_+$ be the following subset of $A$.

$A_+=\left\{x \in A: x \ge 0 \right\}$

The set $A_+$ is a set of non-negative integers. Hence it must have a least element, say $r$. Then we have $r=a-qb$ for some positive integer $q$. Furthermore, we have $0 \le r. If $r>b$, $r$ would not be the least element of $A_+$ since we can subtract $b$ into $r$ to obtain $a-(q+1)b$, which is less than $r$ and is an element of $A_+$.

We now have found integers $q$ and $r$ such that $a = q \cdot b + r$. It remains to show that the integers $q$ and $r$ are unique. Suppose there are also integers $q_0$ and $r_0$ such that

$a=q \cdot b + r=q_0 \cdot b + r_0$

After subtracting, $(q-q_0) \cdot b + (r-r_0)=0$. Since $b$ divides both $0$ and $(q-q_0) \cdot b$, $b$ must divides $r-r_0$. This means that $r-r_0=0$, since both $r$ and $r_0$ are non-negative integers that are less than $b$. Thus $r=r_0$ and in turns $q-q_0$. $\blacksquare$

Conceptually the division algorithm tells us that there is a unique remainder $r$ upon division of $a$ by $b$. In terms of actual computation, it does not tell us how to find the remainder or the quotient. However it is the conceptual underpinning of many concepts and ideas in number theory.

___________________________________________________________________________________________________________________

Congruence

We now use the division algorithm to prove one important property of congruence. The symbol $a \equiv b \ (\text{mod} \ m)$ means that $m$ divides $a-b$ (in words, we say $a$ is congruent to $b$ modulo $m$). For a basic discussion of congruence arithmetic, see “A basic discussion of congruences”. We prove the following property of congruence.

For every integer $a$, $a \equiv r \ (\text{mod} \ m)$ for a unique integer $r$ with $0 \le r.

In other words, any integer is congruence modulo $m$ to one and only one element $r$ in the set $\left\{0,1,2,\cdots,m-1 \right\}$. The integer $r$ is called the least residue of $a$ modulo $m$.

The above property about least residue follows from the division algorithm. Let $a$ be any integer. If $a=0$, clearly $a \equiv 0 \ (\text{mod} \ m)$. We can assume that $a \ne 0$.

Now consider the case that $a>0$. By the division algorithm, there are integers $q$ and $r$ such that $a=q \cdot m+r$ where $0 \le r . Thus $a \equiv r \ (\text{mod} \ m)$.

Consider the case that $a<0$. By the division algorithm, there are integers $q$ and $r$ such that $-a=q \cdot m+r$ where $0 \le r . Immediately we have $a=(-q) \cdot m+(-r)$. Thus $a \equiv -r \ (\text{mod} \ m)$. Note that $-r \equiv m-r \ (\text{mod} \ m)$. Thus $a \equiv m-r \ (\text{mod} \ m)$/

One concluding remark is that any least residue that is found in the above argument is unique. This is because no two distinct elements of the set $\left\{0,1,2,\cdots,m-1 \right\}$ can be congruent to each other. $\blacksquare$

___________________________________________________________________________________________________________________

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