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

# Introducing Carmichael numbers

This is an introduction to Carmichael numbers. We first discuss Carmichael numbers in the context of Fermat primality test and then discuss several basic properties. We also prove Korselt’s criterion, which gives a useful characterization of Carmichael numbers.

___________________________________________________________________________________________________________________

Fermat Primality Test

Fermat’s little theorem states that if $p$ is a prime number, then $a^p \equiv a \ (\text{mod} \ p)$ for any integer $a$. Fermat primality test refers to the process of using Fermat little theorem to check the “prime vs. composite” status of an integer.

Suppose that we have a positive integer $n$ such that the “prime vs. composite” status is not known. If we can find an integer $a$ such that $a^n \not \equiv a \ (\text{mod} \ n)$, then we know for certain that the modulus $n$ is composite (or not prime). For example, let $n = \text{8,134,619}$. Note that $2^{8134619} \equiv 3024172 \ (\text{mod} \ 8134619)$. So we know right away that $n = \text{8,134,619}$ is not prime, even though we do not know what its prime factors are just from applying this test.

Given a positive integer $n$, whenever $a^n \not \equiv a \ (\text{mod} \ n)$, we say that $a$ is a Fermat witness for (the compositeness of) the integer $n$. Thus $2$ is a Fermat witness for $n = \text{8,134,619}$.

What if we try one value of $a$ and find that $a$ is not a witness for (the compositeness of) $n$? Then the test is inconclusive. The best we can say is that $n$ is probably prime. It makes sense to try more values of $a$. If all the values of $a$ we try are not witnesses for $n$ (i.e. $a^n \equiv a \ (\text{mod} \ n)$ for all the values of $a$ we try), then it “seems likely” that $n$ is prime. But if we actually declare that $n$ is prime, the decision could be wrong!

Take $n=\text{10,024,561}$. For several randomly chosen values of $a$, we have the following calculations:

$\displaystyle 5055996^{10024561} \equiv 5055996 \ (\text{mod} \ 10024561)$

$\displaystyle 4388786^{10024561} \equiv 4388786 \ (\text{mod} \ 10024561)$

$\displaystyle 4589768^{10024561} \equiv 4589768 \ (\text{mod} \ 10024561)$

$\displaystyle 146255^{10024561} \equiv 146255 \ (\text{mod} \ 10024561)$

$\displaystyle 6047524^{10024561} \equiv 6047524 \ (\text{mod} \ 10024561)$

The above calculations could certainly be taken as encouraging signs that $n=\text{10,024,561}$ is prime. With more values of $a$, we also find that $a^{10024561} \equiv a \ (\text{mod} \ 10024561)$. However, if we declare that $n=\text{10,024,561}$ is prime, it turns out to be a wrong conclusion.

In reality, $n=\text{10,024,561}$ is composite with $\text{10,024,561}=71 \cdot 271 \cdot 521$. Furthermore $a^{10024561} \equiv a \ (\text{mod} \ 10024561)$ for any integer $a$. So there are no witnesses for $n=\text{10,024,561}$. Any composite positive integer that has no Fermat witnesses is called a Carmichael number, in honor of Robert Carmichael who in 1910 found the smallest such number, which is 561.

Fermat primality test is always correct if the conclusion is that the integer being tested is a composite number (assuming there is no computational error). If the test says the number is composite, then it must be a composite number. In other words, there are no false negatives in using Fermat primality test as described above.

On the other hand, there can be false positives as a result of using Fermat primality test. If the conclusion is that the integer being tested is a prime number, it is possible that the conclusion is wrong. For a wrong conclusion, it could be that there exists a witness for the number being tested and that we have missed it. Or it could be that the number being tested is a Carmichael number. Though Carmichael numbers are rare but there are infinitely many of them. So we cannot ignore them entirely. For these reasons, Fermat primality test as described above is often not used. Instead, other extensions of the Fermat primality test are used.

___________________________________________________________________________________________________________________

Carmichael Numbers

As indicated above, a Carmichael number is a positive composite integer that has no Fermat witnesses. Specifically, it is a positive composite integer that satisfies the conclusion of Fermat’s little theorem. In other words, a Carmichael number is a positive composite integer $n$ such that $a^n \equiv a \ (\text{mod} \ n)$ for any integer $a$.

Carmichael numbers are rare. A recent search found that there are $\text{20,138,200}$ Carmichael numbers between $1$ and $10^{21}$, about one in 50 trillion numbers (documented in this Wikipedia entry on Carmichael numbers). However it was proven by Alford, Granville and Pomerance in 1994 that there are infinitely many Carmichael numbers (paper).

The smallest Carmichael number is $561=3 \cdot 11 \cdot 17$. A small listing of Carmichael numbers can be found in this link, where the example of $n=\text{10,024,561}$ is found.

Carmichael numbers must be odd integers. To see this, suppose $n$ is a Carmichael number and is even. Let $a=-1$. By condition (1) of Theorem 1, we have $(-1)^n=1 \equiv -1 \ (\text{mod} \ n)$. On the other hand, $-1 \equiv n-1 \ (\text{mod} \ n)$. Thus $n-1 \equiv 1 \ (\text{mod} \ n)$. Thus we have $n \equiv 2 \ (\text{mod} \ n)$. It must be the case that $n=2$, contradicting the fact that $n$ is a composite number. So any Carmichael must be odd.

The following theorem provides more insight about Carmichael numbers. A positive integer $n$ is squarefree if its prime decomposition contains no repeated prime factors. In other words, the integer $n$ is squarefree means that if $\displaystyle n=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ is the prime factorization of $n$, then all exponents $e_j=1$.

Theorem 1 (Korselt’s Criterion)

Let $n$ be a positive composite integer. Then the following conditions are equivalent.

1. The condition $a^n \equiv a \ (\text{mod} \ n)$ holds for any integer $a$.
2. The condition $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ holds for any integer $a$ that is relatively prime to $n$.
3. The integer $n$ is squarefree and $p-1 \ \lvert \ (n-1)$ for any prime divisor $p$ of $n$.

Proof of Theorem 1

$1 \Longrightarrow 2$
Suppose that $a$ is relatively prime to the modulus $n$. Then let $b$ be the multiplicative inverse of $a$ modulo $n$, i.e., $ab \equiv 1 \ (\text{mod} \ n)$. By (1), we have $a^n \equiv a \ (\text{mod} \ n)$. Multiply both sides by the multiplicative inverse $b$, we have $a^{n-1} \equiv 1 \ (\text{mod} \ n)$.

$2 \Longrightarrow 3$
Let $\displaystyle n=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ be the prime factorization of $n$ where $p_i \ne p_j$ for $i \ne j$ and each exponent $e_j \ge 1$. Since $n$ must be odd, each $p_j$ must be an odd prime.

We first show that each $e_j=1$, thus showing that $n$ is squarefree. To this end, for each $j$, let $a_j$ be a primitive root modulo $p_j^{e_j}$ (see Theorem 4 in the post Primitive roots of powers of odd primes). Consider the following system of linear congruence equations:

$x \equiv a_1 \ (\text{mod} \ p_1^{e_1})$

$x \equiv a_2 \ (\text{mod} \ p_2^{e_2})$

$\cdots$
$\cdots$
$\cdots$

$x \equiv a_t \ (\text{mod} \ p_t^{e_t})$

Since the moduli $p_j^{e_j}$ are pairwise relatively prime, this system must have a solution according to the Chinese Remainder Theorem (a proof is found here). Let $a$ one such solution. For each $j$, since $a_j$ is a primitive root modulo $p_j^{e_j}$, $a_j$ is relatively prime to $p_j^{e_j}$. Since $a \equiv a_j \ (\text{mod} \ p_j^{e_j})$, $a$ is relatively prime to $p_j^{e_j}$ for each $j$. Consequently, $a$ is relatively prime to $n$. By assumption (2), we have $a^{n-1} \equiv 1 \ (\text{mod} \ n)$.

Now fix a $j$ with $1 \le j \le t$. We show that $e_j=1$. Since $a^{n-1} \equiv 1 \ (\text{mod} \ n)$, $a^{n-1} \equiv 1 \ (\text{mod} \ p_j^{e_j})$. Since $a \equiv a_j \ (\text{mod} \ p_j^{e_j})$, we have $a_j^{n-1} \equiv 1 \ (\text{mod} \ p_j^{e_j})$. Note that the order of $a_j$ modulo $p_j^{e_j}$ is $\phi(p_j^{e_j})=p_j^{e_j-1}(p_j-1)$. Thus we have $p_j^{e_j-1}(p_j-1) \ \lvert \ (n-1)$. If $e_j>1$, then $p_j \ \lvert \ (n-1)$, which would mean that $p_j \ \lvert \ 1$. So it must be the case that $e_j=1$. It then follows that $(p_j-1) \ \lvert \ (n-1)$.

$3 \Longrightarrow 1$
Suppose that $n=p_1 p_2 \cdots p_t$ is a product of distinct prime numbers such that for each $j$, $(p_j-1) \ \lvert \ (n-1)$.

Let $a$ be any integer. First we show that $a^n \equiv a \ (\text{mod} \ p_j)$ for all $j$. It then follows that $a^n \equiv a \ (\text{mod} \ n)$.

Now fix a $j$ with $1 \le j \le t$. First consider the case that $a$ and $p_j$ are relatively prime. According to Fermat’s little theorem, $a^{p_j-1} \equiv 1 \ (\text{mod} \ p_j)$. Since $(p_j-1) \ \lvert \ (n-1)$, $a^{n-1} \equiv 1 \ (\text{mod} \ p_j)$. By the Chinese Remainder Theorem, it follows that $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ and $a^n \equiv a \ (\text{mod} \ n)$. $\blacksquare$

Examples
With Korselt’s criterion, it is easy to verify Carmichael numbers as long as the numbers are factored. For example, the smallest Carmichael number is $561=3 \cdot 11 \cdot 17$. The number is obviously squarefree. furthermore $560$ is divisible by $2$, $10$ and $16$.

The number $\text{10,024,561}= 71 \cdot 271 \cdot 521$ is discussed above. We can also verify that this is a Carmichael number: $70 \ \lvert \ \text{10,024,560}$, $270 \ \lvert \ \text{10,024,560}$ and $520 \ \lvert \ \text{10,024,560}$.

Here’s three more Carmichael numbers (found here):

$\text{23,382,529} = 97 \cdot 193 \cdot 1249$

$\text{403,043,257} = 19 \cdot 37 \cdot 43 \cdot 67 \cdot 199$

$\text{154,037,320,009} = 23 \cdot 173 \cdot 1327 \cdot 29173$

We end the post by pointing out one more property of Carmichael numbers, that Carmichael numbers must have at least three distinct prime factors. To see this, suppose that $n=p \cdot q$ is a Carmichael number with two distinct prime factors $p$ and $q$. We can express $n-1$ as follows:

$n-1=pq-1=(p-1)q+q-1$

Since $n$ is Carmichael, $p-1 \ \lvert \ (n-1)$. So $n-1=(p-1)w$ for some integer $w$. Plugging this into the above equation, we see that $p-1 \ \lvert \ (q-1)$. By symmetry, we can also show that $q-1 \ \lvert \ (p-1)$. Thus $p=q$, a contradiction. So any Carmichael must have at least three prime factors.

___________________________________________________________________________________________________________________

$\copyright \ 2013 \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}$