# Euler’s phi function is multiplicative

This post gives a proof that Euler’s phi function is multiplicative. The proof is a simpler and more elegant proof, as compared to the one presented here. The combinatorial argument is greatly simplified using the Chinese remainder theorem (abbreviated CRT).

The letter $m$ is used below to denote the modulus in modular arithmetic. The phi function $\phi(m)$ is defined to be the count of all the integers $0 \le a \le m-1$ such that $a$ and $m$ are relatively prime. If $m$ is prime, then $\phi(m)=m-1$ since all integers from $1$ to $m-1$ have no factors in common with $m$ (other than 1). If $m=10$, then $\phi(10)=4$ since 1, 3, 7, and 9 are the only numbers that are relatively prime to $m=10$.

To properly work with the phi function, conmsider the following setting. Given a modulus $m$, a set of interest is $\mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}$. This is the set of all least resdues modulo $m$, i.e., every integer is congruent modulo $m$ to exactly one element of $\mathbb{Z}_m$. Another set of interest is $\mathbb{Z}_m^*$, which is the set of all elements $a$ in $\mathbb{Z}_m$ such that $a$ and $m$ are relatively prime. In other words, $\phi(m)$ is defined to be the cardinality of the set $\mathbb{Z}_m^*$.

The set $\mathbb{Z}_m$ is called the ring of integers modulo $m$ since it satisfies the definition of a ring with regard to addition and multiplication modulo $m$. The set $\mathbb{Z}_m^*$ with the multiplication modulo $m$ is a group, i.e. every element of $\mathbb{Z}_m^*$ has a multiplicative inverse with respect to the binary operation of multiplication modulo $m$. The set $\mathbb{Z}_m^*$ is called the multiplicative group of integers modulo $m$. The fact that $\mathbb{Z}_m^*$ is a group is established by the following theorem, which is proved here.

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

1. The numbers $a$ and $m$ are relatively prime, i.e. $\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$.

Another interesting fact to point out is that when $m$ is a prime number, $\mathbb{Z}_m$ is a field, i.e. it is a commutative ring in which every non-zero element has a multiplicative inverse. Another terminology that is used by some authors is that the elements in $\mathbb{Z}_m$ that have multiplicative inverses are called units. Thus $\mathbb{Z}_m^*$ is also called the group of units of the ring of integers modulo $m$. Our notation here is not standard. The usual notation for the ring $\mathbb{Z}_m$ is $\mathbb{Z}/m\mathbb{Z}$. The usual notation for $\mathbb{Z}_m^*$ is $(\mathbb{Z}/m\mathbb{Z})^*$.

The phi function is multiplicative in the following sense.

Theorem 2
Let $m$ and $n$ be positive integers such that they are relatively prime. Then $\phi(m \times n)=\phi(m) \times \phi(n)$.

Theorem 2 is established by the following results.

Lemma 3
Let $m$ and $n$ be positive integers such that they are relatively prime. Then the set $\mathbb{Z}_{mn}$ and the set $\mathbb{Z}_m \times \mathbb{Z}_n$ have the same cardinality.

Proof
To prove that the two sets have the same cardinality, we define a bijection $f: \mathbb{Z}_{mn} \rightarrow \mathbb{Z}_m \times \mathbb{Z}_n$, i.e. $f$ is a one-to-one function that maps $\mathbb{Z}_{mn}$ onto the set $\mathbb{Z}_m \times \mathbb{Z}_n$. For each $a \in \mathbb{Z}_{mn}=\left\{0,1,2,\cdots,m \cdot n-1 \right\}$, define $f(a)=(c, d)$ where $c \in \mathbb{Z}_m$ with $c \equiv a \ (\text{mod} \ m)$ and $d \in \mathbb{Z}_n$ with $d \equiv a \ (\text{mod} \ n)$.

To see that $f$ is one-to-one, let $f(a)=f(b)$. Then we have $a \equiv b \ (\text{mod} \ m)$ and $a \equiv b \ (\text{mod} \ n)$. By the Chinese remainder theorem, $a \equiv b \ (\text{mod} \ mn)$. Since $a,b \in \mathbb{Z}_{mn}$, $a=b$.

To show that $f$ maps $\mathbb{Z}_{mn}$ onto the set $\mathbb{Z}_m \times \mathbb{Z}_n$, let $(c,d) \in \mathbb{Z}_m \times \mathbb{Z}_n$. Consider the equations $x \equiv c \ (\text{mod} \ m)$ and $x \equiv d \ (\text{mod} \ n)$. By CRT, these two equations have a simultaneous solution $a$ that is unique modulo $m \times n$. This means that $f(a)=(c, d)$. $\square$

Lemma 4
Let $m$ and $n$ be positive integers such that they are relatively prime. Then the set $\mathbb{Z}_{mn}^*$ and the set $\mathbb{Z}_m^* \times \mathbb{Z}_n^*$ have the same cardinality.

Proof
The same mapping $f$ defined in the proof of Lemma 3 is used. We show that when $f$ is restricted to the set $\mathbb{Z}_{mn}^*$, it is a bijection from $\mathbb{Z}_{mn}^*$ onto the set $\mathbb{Z}_m^* \times \mathbb{Z}_n^*$. First, we show that for any $a \in \mathbb{Z}_{mn}^*$, $f(a)$ is indeed in $\mathbb{Z}_m^* \times \mathbb{Z}_n^*$. To see this, note that $a$ and $m \times n$ are relatively prime. So it must be that $a$ and $m$ are relatively prime too and that $a$ and $n$ are relatively prime.

The function $f$ is one-to-one as shown above. The remaining piece is that for each $(c,d) \in \mathbb{Z}_m^* \times \mathbb{Z}_n^*$, there is some $a \in \mathbb{Z}_{mn}^*$ such that $f(a)=(c,d)$. As in the proof of Lemma 3, there is some $a \in \mathbb{Z}_{mn}$ such that $f(a)=(c,d)$. Note that $a$ and $m$ are relatively prime and $a$ and $n$ are relatively prime. This means that $a$ and $m \times n$ are relatively prime (see Lemma 4 here). Thus the function $f$ is a one-to-one from $\mathbb{Z}_{mn}^*$ onto $\mathbb{Z}_m^* \times \mathbb{Z}_n^*$. $\square$

Proof of Theorem 2
Lemma 4 shows that the set $\mathbb{Z}_{mn}^*$ and the set $\mathbb{Z}_m^* \times \mathbb{Z}_n^*$ have the same cardinality. First, $\phi(m \times n)$ is the cardinality of the set $\mathbb{Z}_{mn}^*$. Theorem 2 is established by noting that $\phi(m) \times \phi(n)$ is the cardinality of $\mathbb{Z}_m^* \times \mathbb{Z}_n^*$. $\square$

____________________________________________________________________________

Evaluating the phi function

The combinatorial argument for $\phi(m \times n)=\phi(m) \times \phi(n)$ is greatly simplified by using the Chinese remainder theorem. Compare the above proof with the lengthier proof in an earlier post (see Theorem 3 here). With the multiplicative property of the phi function, we can evaluate the phi function for any positive integer.

For any positive integer $m$, consider its unique prime factorization $m=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}$. Then we have:

\displaystyle \begin{aligned} \phi(m)&=\phi(p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}) \\&=\phi(p_1^{e_1}) \times \phi(p_2^{e_2}) \times \cdots \times \phi(p_t^{e_t}) \\&=p_1^{e_1-1} \cdot (p_1-1) \times p_2^{e_2-1} \cdot (p_2-1) \times \cdots \times p_t^{e_t-1} \cdot (p_t-1) \\&=p_1^{e_1} \cdot \biggl(1-\frac{1}{p_1}\biggr) \times p_2^{e_2} \cdot \biggl(1-\frac{1}{p_2}\biggr) \times \cdots \times p_t^{e_t} \cdot \biggl(1-\frac{1}{p_t}\biggr) \\&=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t} \cdot \biggl(1-\frac{1}{p_1}\biggr) \times \cdot \biggl(1-\frac{1}{p_2}\biggr) \times \cdots \times \cdot \biggl(1-\frac{1}{p_t}\biggr) \\&=m \cdot \biggl(1-\frac{1}{p_1}\biggr) \times \cdot \biggl(1-\frac{1}{p_2}\biggr) \times \cdots \times \cdot \biggl(1-\frac{1}{p_t}\biggr)\end{aligned}

In the above evaluation, this fact is used. For any prime $p$, $\phi(p^n)=p^{n-1} \times (p-1)$ (see see Theorem 2 here). We also use the extended version of Theorem 2: if $m_1,m_2,\cdots,m_t$ are pairwise relatively prime, then

$\phi(m_1 \times m_2 \times \cdots \times m_t)=\phi(m_1) \times \phi(m_2) \times \cdots \times \phi(m_t)$.

The extended result is to extend the product to more than two numbers. It is derived by a simple inductive argument.

____________________________________________________________________________

A formula for the phi function

The above evaluation leads us to the following way to express the phi function. For $m=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}$, we have the following:

$\displaystyle \phi(m)=m \ \prod \limits_{p \lvert m} \biggl( 1-\frac{1}{p} \biggr)$

In the above product, the $p$ ranges over all prime divisors of $m$. A quick example: for $33075=3^3 \cdot 5^2 \cdot 7^2$,

\displaystyle \begin{aligned}\phi(33075)&=33075 \times \biggl( 1-\frac{1}{3} \biggr) \times \biggl( 1-\frac{1}{5} \biggr) \times \biggl( 1-\frac{1}{7} \biggr) \\&=33075 \times \frac{2}{3} \times \frac{4}{5} \times \frac{6}{7} \\&=315 \times 2 \times 4 \times 6 \\&=15120 \end{aligned}

One comment. For the above formula to work, we only need to know the prime divisors of the number, not necessarily the powers of the primes. For example, for 33075, we only need to know that the prime divisors are 3, 5 and 7.

____________________________________________________________________________

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

# The primitive root theorem revisited

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

____________________________________________________________________________

The primitive root theorem

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

____________________________________________________________________________

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

____________________________________________________________________________

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

# The primitive root theorem

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

Main Theorem (The Primitive Root Theorem)

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

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

___________________________________________________________________________________________________________________

LCM

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

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

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

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

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

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

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

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

Lemma 1

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

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

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

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

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

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

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

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

___________________________________________________________________________________________________________________

Other Tools

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

Lemma 2

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

The number $a$ is a primitive root modulo $m$ if and only if $\displaystyle a^{\frac{\phi(m)}{q}} \not \equiv 1 \ (\text{mod} \ m)$ for all prime divisors $q$ of $\phi(m)$.

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

___________________________________________________________________________________________________________________

Breaking It Up Into Smaller Pieces

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

Lemma 4

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

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

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

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

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

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

Theorem 5

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

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

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

Theorem 6

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

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

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

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

Lemma 7

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

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

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

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

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

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

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

Theorem 8

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

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

___________________________________________________________________________________________________________________

Putting It All Together

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

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

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

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

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

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

___________________________________________________________________________________________________________________

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

# Primitive roots of twice the powers of odd primes

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

Theorem 1

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

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

Theorem 2 (CRT)

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

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

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

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

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

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

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

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

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

___________________________________________________________________________________________________________________

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

# Primitive roots of powers of odd primes

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

___________________________________________________________________________________________________________________

Example

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

___________________________________________________________________________________________________________________

Square of an Odd Prime

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

Lemma 1

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

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

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

Theorem 2

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

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

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

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

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

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

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

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

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

___________________________________________________________________________________________________________________

Higher Powers of an Odd Prime

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

Lemma 3

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

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

(*) A number $h$ is a primitive root modulo $m$ if and only if $\displaystyle h^{\frac{\phi(m)}{t}} \not \equiv 1 \ (\text{mod} \ m)$ for all prime divisor $t$ of $\phi(m)$.

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

Theorem 4

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

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

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

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

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

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

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

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

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

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

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

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

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

___________________________________________________________________________________________________________________

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

# More about checking for primitive roots

Finding primitive roots modulo a number is of great interest in number theory, both in a theoretical standpoint and in a computational standpoint. In this post we compare and contrast three different ways of checking for primitive roots, continuing a discussion in an earlier post An elementary algorithm for finding primitive roots.

___________________________________________________________________________________________________________________

Background

Let $m$ be a positive integer. Let $a$ be a positive integer that is relative prime to $m$. Let $\phi$ be Euler’s phi function, which counts the number of least residues that are relatively prime to the modulus. For example, $\phi(6)=2$ as $1$ and $5$ are the only numbers relatively prime to $6$ (out of the numbers $0,1,2,3,4,5$). Furthermore, $\phi(p)=p-1$ for any prime number $p$. Previous posts on the phi function: Euler’s phi function, part 1 and Euler’s phi function, part 2.

Euler’s theorem tells us that $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$. By the order of $a$ modulo $m$ we mean the least positive exponent $k$ such that $a^{k} \equiv 1 \ (\text{mod} \ m)$ (Euler’s theorem indicates that this notion of order is well defined). The number $a$ is said to be a primitive root modulo $m$ if the order of $a$ modulo $m$ is $\phi(m)$.

___________________________________________________________________________________________________________________

Three Checks

Let $m$ be a positive integer. Let $a$ be a positive integer that is relative prime to $m$. How can we determine whether the number $a$ is a primitive root modulo $m$? We discuss three ways of answering this question.

____________________________________________________________________________________________
Check # 1

Check $a^j \ (\text{mod} \ m)$ for all positive integers $j<\phi(m)$.

If each such congruence $\not \equiv 1$, then the number $a$ is a primitive root modulo $m$.

____________________________________________________________________________________________

Check # 1 is merely a restatement of the definition of primitive root. It is a dumb test as it requires too much calculation. For large moduli, it would be an inefficient method of checking for primitive roots. The following is a much better test.

____________________________________________________________________________________________
Check # 2

Check $a^j \ (\text{mod} \ m)$ for all positive divisors $j$ of $\phi(m)$ with $j<\phi(m)$.

If each such congruence $\not \equiv 1$, then the number $a$ is a primitive root modulo $m$.

____________________________________________________________________________________________

Check # 2 narrows down the checking by quite a bit – simply checking $a^j$ among the divisors of $\phi(m)$. This works because the only possible numbers for the order modulo $m$ of the number $a$ are the divisors of $\phi(m)$. So we can skip all $j$ that are not divisors of $\phi(m)$. The following lemma shows why this is so. Actually, the lemma proves something more general. It shows that if $a^n \equiv 1 \ (\text{mod} \ m)$, then the order of $a$ must be a divisor of $n$. Euler’s theorem says that $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$. So the order of $a$ must be a divisor of $\phi(m)$.

Lemma 1

Let $k$ be the order of $a$ modulo $m$. If $a^n \equiv 1 \ (\text{mod} \ m)$, then $k \ \lvert \ n$.

Proof of Lemma 1
We have $k \le n$ since $k$ is least with the property $a^k \equiv 1 \ (\text{mod} \ m)$. By the division algorithm, we have $n=q \cdot k+r$ where $q$ is some integer and $0 \le r . 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}$

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