# An upper bound for Carmichael numbers

It is well known that Fermat’s little theorem can be used to establish the compositeness of some integers without actually obtaining the prime factorization. Fermat’s little theorem is an excellent test for compositeness as well as primality. However, there are composite numbers that evade the Fermat test, i.e. the Fermat test will fail to indicate that these composite integers are composite. These integers are called Carmichael numbers. However, Carmichael numbers are rare. We illustrate this point by doing some calculation using an upper bound for Carmichael numbers.

Let $p$ be a prime number. According to Fermat’s little theorem, $a^{p-1} \equiv 1 \ (\text{mod} \ p)$ for all integer $a$ that is relatively prime to $p$ (i.e., the GCD of $a$ and $p$ is 1). The Fermat primality test goes like this. Suppose that the “composite or prime” status of the positive integer $n$ is not known. We randomly pick a number $a \in \left\{2,3,\cdots,n-1 \right\}$. If $a$ is relatively prime to $n$ and if $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$, then we are certain that $n$ is composite even though we may not know its prime factorization. Such a value of $a$ is said to be a Fermat witness for (the compositeness of) $a$. If $a^{n-1} \equiv 1 \ (\text{mod} \ n)$, then $n$ is probably prime. But to be sure, repeat the calculation with more values of $a$. If the calculation is done for a large number of randomly selected values of $a$ and if the calculation for every one of the values of $a$ indicates that $n$ is probably prime, we will have high confidence that $n$ is prime. In other words, the probability of making a mistake is very small.

However here is a wrinkle in the Fermat test. There are composite numbers which have no Fermat witnesses. These numbers are called Carmichael numbers. Specifically a positive composite integer $n$ is a Carmichael number if $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ for all $a$ relatively prime to $n$. In other words, if $n$ is a Carmichael number, the Fermat test always indicates $n$ is probably prime no matter how many values of $a$ you use in the test. Fortunately Carmichael numbers are rare. The upper bound discussed below gives an indication of why this is the case.

____________________________________________________________________________

An upper bound

For each positive integer $n$, let $C(n)$ be the number of Carmichael numbers that are less than $n$. The following is an upper bound for $C(n)$.

$\displaystyle C(n)

The formula is found here (credited to Richard G. E. Pinch). We use this upper bound to find out the chance of encountering a Carmichael numbers. As shown below, the upper bound can overestimate $C(n)$. The main point we like to make is that even with the overestimation of Carmichael numbers represented by the above upper bound, the number of Carmichael number is extremely small in relation to $n$. This is even more so when $n$ is large (e.g. a 1024-bit integer). Thus for a randomly selected 1024-bit odd number, the probability that it is a Carmichael number is practically zero (see Examples 4 and 5 below).

____________________________________________________________________________

Examples

Example 1
The first 10 Carmichael numbers are 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341. Furthermore, there are only 16 Carmichael numbers less than 100,000. Let $n=10^5$. According to the above formula, the following is the upper bound for $C(10^5)$:

$\displaystyle C(10^5)<10^5 \cdot \text{exp}\biggl(-\frac{(\text{ln} \ 10^5) \ (\text{ln} \ \text{ln} \ \text{ln} \ 10^5)}{\text{ln} \ \text{ln} \ 10^5} \biggr)=1485$

The bound of 1485 is a lot more than the actual count of 16. Even with this inflated estimate, when you randomly select an odd positive integer less than 10,000, the probability of getting a Carmichael number is $0.0297$. With the actual count of 16, the probability is 0.00032.

Example 2
Here’s another small example. There are only 2,163 Carmichael numbers that are less than 25,000,000,000. Let $n=2.5 \cdot 10^{10}$.

$\displaystyle C(2.5 \cdot 10^{10})<2.5 \cdot 10^{10} \cdot \text{exp}\biggl(-\frac{(\text{ln} \ 2.5 \cdot 10^{10}) \ (\text{ln} \ \text{ln} \ \text{ln} \ 2.5 \cdot 10^{10})}{\text{ln} \ \text{ln} \ 2.5 \cdot 10^{10}} \biggr)=4116019$

This inflated bound is a more than 1900 times over the actual count of 2163. But even with this inflated bound, the probability of a random odd integer being Carmichael is under 0.00033 (about 3 in ten thousands). With the actual count of 2163, the probability is 0.00000017 (less than one in a million chance).

Example 3
Here’s a larger example. A calculation was made by Richard G. E. Pinch that there are 20,138,200 many Carmichael numbers up to $10^{21}$. Let’s compare the actual probability and the probability based on the upper bound. The following is the upper bound of $C(10^{21})$.

$\displaystyle C(10^{21})<10^{21} \cdot \text{exp}\biggl(-\frac{(\text{ln} \ 10^{21}) \ (\text{ln} \ \text{ln} \ \text{ln} \ 10^{21})}{\text{ln} \ \text{ln} \ 10^{21}} \biggr) \approx 4.6 \cdot 10^{13}$

The actual count of 20,138,200 is about $2 \cdot 10^{7}$. So $4.6 \cdot 10^{13}$ is an inflated estimate. The following shows the probability of randomly selecting an odd integer that is Carmichael (both actual and inflated).

$\displaystyle \text{inflated probability}=\frac{4.6 \cdot 10^{13}}{0.5 \cdot 10^{21}}=\frac{4.6 \cdot 10^{13}}{5 \cdot 10^{20}}=\frac{0.92}{10^{7}} \approx \frac{1}{10.9 \cdot 10^6} <\frac{1}{10^6}$

$\displaystyle \text{actual probability}=\frac{2 \cdot 10^{7}}{0.5 \cdot 10^{21}}=\frac{2 \cdot 10^{7}}{5 \cdot 10^{20}}=\frac{0.4}{10^{13}} = \frac{1}{25 \cdot 10^{12}} <\frac{1}{10^{12}}$

Even with the inflated upper bound, the chance of randomly picking a Carmichael number is less than one in a million. With the actual count of 20,138,200, the chance of randomly picking a Carmichael number is less than one in a trillion!

Remark
The number $10^{21}$ is quite small in terms of real world applications. For example, in practice, the RSA algorithm requires picking prime numbers that are at least 512-bit long. The largest 512-bit numbers are approximately $10^{154}$. What is the chance of randomly picking a Carmichael number in this range? First, let’s look at the Carmichael numbers up to the limit $10^{100}$. Then we look at $10^{154}$.

Example 4
Here’s the estimates for $C(10^{100})$ based on the above upper bound.

$\displaystyle C(10^{100})<10^{100} \cdot \text{exp}\biggl(-\frac{(\text{ln} \ 10^{100}) \ (\text{ln} \ \text{ln} \ \text{ln} \ 10^{100})}{\text{ln} \ \text{ln} \ 10^{100}} \biggr) \approx 7.3 \cdot 10^{68}$

$\displaystyle \text{probability}=\frac{7.3 \cdot 10^{68}}{0.5 \cdot 10^{100}}=\frac{7.3 \cdot 10^{68}}{5 \cdot 10^{99}}=\frac{1.46}{10^{31}} \approx \frac{1}{6.8 \cdot 10^{30}} <\frac{1}{10^{30}}$

Thus the chance of randomly picking a Carmichael number under $10^{100}$ is less than one in $10^{30}$, i.e., practically zero.

Example 5
Here’s the example relevant to the RSA algorithm. As mentioned above, the RSA algorithm requires that the modulus in the public key is a product of two primes. The current practice is for the modulus to be at least 1024 bits. Thus each prime factor of the modulus is at least 512-bit. A 512-bit number can be as large as $10^{154}$ in decimal terms. When picking candidate for prime numbers, it is of interest to know the chance of picking a Carmichael number. We can get a sense of how small this probability is by asking: picking an odd integer under the limit $10^{154}$, what is the chance that it is a Carmichael number? Here’s the estimates:

$\displaystyle C(10^{154})<10^{154} \cdot \text{exp}\biggl(-\frac{(\text{ln} \ 10^{154}) \ (\text{ln} \ \text{ln} \ \text{ln} \ 10^{154})}{\text{ln} \ \text{ln} \ 10^{154}} \biggr) \approx 3.7 \cdot 10^{107}$

$\displaystyle \text{probability}=\frac{3.7 \cdot 10^{107}}{0.5 \cdot 10^{154}}=\frac{7.4}{10^{47}}=\frac{0.74}{10^{46}} < \frac{1}{10^{46}}$

Thus a randomly selected odd integer under $10^{154}$ has a less than one in $10^{46}$ chance of being a Carmichael number!

Example 6
In some cases, for stronger security, the modulus in the RSA should be longer than 1024 bits, e,g, 2048 bits. If the modulus is a 2048-bit number, each prime in the modulus is a 1024-bit number. A 1024-bit number can be as large as $10^{308}$ in decimal terms. In picking an odd integer under the limit $10^{308}$, what is the chance that it is a Carmichael number? Here’s the estimates:

$\displaystyle C(10^{308})<10^{308} \cdot \text{exp}\biggl(-\frac{(\text{ln} \ 10^{308}) \ (\text{ln} \ \text{ln} \ \text{ln} \ 10^{308})}{\text{ln} \ \text{ln} \ 10^{308}} \biggr) \approx 5 \cdot 10^{219}$

$\displaystyle \text{probability}=\frac{5 \cdot 10^{219}}{0.5 \cdot 10^{308}}=\frac{5 \cdot 10^{219}}{5 \cdot 10^{307}} \approx \frac{1}{10^{88}}$

Thus a randomly selected odd integer under $10^{308}$ has a less than one in $10^{88}$ chance of being a Carmichael number!

Remark
The above examples demonstrate that Carmichael numbers are rare. Even though the Fermat primality test “fails” for these numbers, the Fermat test is still safe to use because Carmichael numbers are hard to find. However, if you want to eliminate the error case of Carmichael numbers, you may want to consider using a test that will never misidentify Carmichael numbers. One possibility is to use the Miller-Rabin test.

____________________________________________________________________________

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

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

In a previous post called Solving Quadratic Congruences, we discuss the solvability of the quadratic congruence

$x^2 \equiv a \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

where $p$ is an odd prime and $a$ is relatively prime to $p$. In this post, we continue to discuss the solvability of equation (1) from the view point of quadratic residues. In this subsequent post, we discuss specific algorithms that produce solutions to such equations.

____________________________________________________________________________

Definition

Let $p$ be an odd prime. Let $a$ be an integer that is not divisible by $p$ (equivalently relatively prime to $p$). Whenever equation (1) has solutions, we say that the number $a$ is a quadratic residue modulo $p$. Otherwise, we say that the number $a$ is a quadratic nonresidue modulo $p$. When the context is clear, the word quadratic is sometimes omitted.

The term quadratic residues is more convenient to use. Instead of saying the equation $x^2 \equiv a \ (\text{mod} \ p)$ has a solution, we say the number $a$ is a quadratic residue for the modulus in question. The significance of the notion of quadratic residue extends beyond the convenience of having a shorter name. It and and the Legendre symbol lead to a large body of beautiful and deep results in number theory, the quadratic reciprocity theorem being one of them.

One property of the quadratic congruence equation (1) is that when equation (1) has solutions, it has exactly two solutions among the set $\left\{1,2,3,\cdots,p-1 \right\}$ (see Lemma 1 in the post Solving Quadratic Congruences). Thus among the integers in the set $\left\{1,2,3,\cdots,p-1 \right\}$, $\displaystyle \frac{p-1}{2}$ of them are quadratic residues and the other half are quadratic nonresidues modulo $p$.

For example, consider the modulus $p=11$. Among the numbers in the set $\left\{1,2,3,\cdots,10 \right\}$, the numbers $1,3,4,5,9$ are quadratic residues and the numbers $2,6,7,8,10$ are quadratic nonresidues. See the following two tables.

$\displaystyle \begin{bmatrix} x&\text{ }&x^2 \equiv \ (\text{mod} \ 11) \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1 \\ 2&\text{ }&4 \\ 3&\text{ }&9 \\ 4&\text{ }&5 \\ 5&\text{ }&3 \\ 6&\text{ }&3 \\ 7&\text{ }&5 \\ 8&\text{ }&9 \\ 9&\text{ }&4 \\ 10&\text{ }&1 \end{bmatrix}$

The above table shows the least residues of $x^2$ for $x \in \left\{1,2,3,\cdots,10 \right\}$. It shows that there $x^2$ can only be $1,3,4,5,9$. Thus these are the quadratic residues. The table below shows the status of residue/nonresidue among the integers in $\left\{1,2,3,\cdots,10 \right\}$.

$\displaystyle \begin{bmatrix} x&\text{ }&\text{residue or nonresidue mod } 11 \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&\text{residue} \\ 2&\text{ }&\text{nonresidue} \\ 3&\text{ }&\text{residue} \\ 4&\text{ }&\text{residue} \\ 5&\text{ }&\text{residue} \\ 6&\text{ }&\text{nonresidue} \\ 7&\text{ }&\text{nonresidue} \\ 8&\text{ }&\text{nonresidue} \\ 9&\text{ }&\text{residue} \\ 10&\text{ }&\text{nonresidue} \end{bmatrix}$

____________________________________________________________________________

Legendre Symbol

The notion of quadratic residues is often expressed using the Legendre symbol, which is defined as follows:

$\displaystyle \biggl(\frac{a}{p}\biggr)=\left\{\begin{matrix}1&\ \text{if } a \text{ is a quadratic residue modulo }p \\{-1}&\ \text{if } a \text{ is a quadratic nonresidue modulo }p \end{matrix}\right.$

The bottom number $p$ in the above notation is an odd prime. The top number $a$ is an integer that is not divisible by $p$ (equivalently relatively prime to $p$). Despite the appearance, the Legendre symbol is not the fraction of $a$ over $p$. It follows from the definition that the symbol has the value of one if the equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions. It has the value of negative one if the equation $x^2 \equiv a \ (\text{mod} \ p)$ has no solutions.

For example, $\displaystyle \biggl(\frac{a}{11}\biggr)=1$ for $a=1,3,4,5,9$ and and $\displaystyle \biggl(\frac{a}{11}\biggr)=-1$ for $a=2,6,7,8,10$. To evaluate $\displaystyle \biggl(\frac{11}{3}\biggr)$, consider the equation $x^2 \equiv 11 \ (\text{mod} \ 3)$, which is equivalent to the equation $x^2 \equiv 2 \ (\text{mod} \ 3)$. This last equation has no solutions. Thus $\displaystyle \biggl(\frac{11}{3}\biggr)=-1$.

The quadratic reciprocity law discussed below allows us to calculate $\displaystyle \biggl(\frac{11}{3}\biggr)$ by flipping $\displaystyle \biggl(\frac{3}{11}\biggr)$. In certain cases, flipping the symbol keeps the same sign. In other cases, flipping introduces a negative sign (as in this example).

____________________________________________________________________________

Basic Properties

Euler’s Criterion is a formula that determines whether an integer is a quadratic residue modulo an odd prime. We have the following theorem. A proof of Euler’s Criterion is found in this post.

Theorem 1 (Euler’s Criterion)

Let $p$ be an odd prime number. Let $a$ be a positive integer that is not divisible by $p$. Then the following property holds.

$\displaystyle \biggl(\frac{a}{p}\biggr) \equiv \displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p)$

The following lemma shows a connection between the notion of quadratic residue and the notion of primitive roots.

Lemma 2

Let $p$ be an odd prime. Let $g$ be a primitive root modulo $p$. Let $a$ be a positive integer that is not divisible by $p$. Then we have the following equivalence.

1. The number $a$ is a quadratic residue modulo $p$ if and only if $a \equiv g^{2k} \ (\text{mod} \ p)$ for some integer $k$.
2. Or equivalently, the number $a$ is a quadratic nonresidue modulo $p$ if and only if $a \equiv g^{2k+1} \ (\text{mod} \ p)$ for some integer $k$.

Proof of Lemma 2
A primitive root $g$ exists since the modulus $p$ is prime (see Theorem 1 in the post Primitive roots of prime moduli). Furthermore, any integer that is not divisible by $p$ is congruent to a unique element of the set $\left\{g^1,g^2,g^3,\cdots,g^{p-1} \right\}$. Thus for the number $a$ in question, either $a \equiv g^{2k}$ or $a \equiv g^{2k+1}$. We can conclude that the first bullet point in the lemma is equivalent to the second bullet point.

We prove the first bullet point. First we show the direction $\Longleftarrow$. Suppose $a \equiv g^{2k} \ (\text{mod} \ p)$. Clearly the equation $x^2 \equiv a \ (\text{mod} \ p)$ has a solution since $(g^k)^2 \equiv a \equiv g^{2k} \ (\text{mod} \ p)$.

Now we show the direction $\Longrightarrow$. We prove the contrapositive. Suppose that $a \equiv g^{2k+1} \ (\text{mod} \ p)$. We wish to show that $a$ is a quadratic nonresidue modulo $p$. Suppose not. Then $t^2 \equiv a \ (\text{mod} \ p)$ for some $t$. It follows that $p \not \lvert \ t$. Note that if $p \ \lvert \ t$, $p \ \lvert \ a$, which is not true. By Fermat’s little theorem, we have $t^{p-1} \equiv 1 \ (\text{mod} \ p)$. We have the following derivation.

$\displaystyle (g^{2k+1})^{\frac{p-1}{2}} \equiv (t^{2})^{\frac{p-1}{2}} \equiv t^{p-1} \equiv 1 \ (\text{mod} \ p)$

On the other hand, we can express $\displaystyle (g^{2k+1})^{\frac{p-1}{2}}$ as follows:

$\displaystyle (g^{2k+1})^{\frac{p-1}{2}} \equiv g^{k(p-1)} \cdot g^{\frac{p-1}{2}} \equiv (g^{p-1})^k \cdot g^{\frac{p-1}{2}} \equiv 1^k \cdot g^{\frac{p-1}{2}} \equiv g^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$

Note that the last congruence $g^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$ contradicts the fact that $g$ is a primitive root modulo $p$ since $p-1$ is the least exponent that such that $g^{p-1} \equiv 1 \ (\text{mod} \ p)$. So $a$ cannot be a quadratic residue modulo $p$. We have proved that if $a \equiv g^{2k+1} \ (\text{mod} \ p)$, then $a$ is a quadratic nonresidue modulo $p$. Equivalently, if $a$ is a quadratic residue modulo $p$, then $a \equiv g^{2k} \ (\text{mod} \ p)$. Thus the lemma is established. $\blacksquare$

We can also obtain an alternative proof by using Theorem 1 (Euler’s Criterion). We show $\Longleftarrow$ of both bullet points.

First, $\Longleftarrow$ of the first bullet point. Suppose $a \equiv g^{2k} \ (\text{mod} \ p)$. Then $\displaystyle (g^{2k})^{\frac{p-1}{2}} \equiv (g^{p-1})^k \equiv 1^k \equiv 1 \ (\text{mod} \ p)$. Thus $\displaystyle \biggl(\frac{a}{p}\biggr)=1$ and $a$ is a quadratic residue modulo $p$ by Euler’s Criterion.

Now $\Longleftarrow$ of the second bullet point. Suppose $a \equiv g^{2k+1} \ (\text{mod} \ p)$. Then $\displaystyle (g^{2k+1})^{\frac{p-1}{2}} \equiv (g^{p-1})^k \cdot g^{\frac{p-1}{2}} \equiv g^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$. The last congruence $g^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$ because $g$ is a primitive root. Thus $\displaystyle \biggl(\frac{a}{p}\biggr)=-1$ and $a$ is a quadratic nonresidue modulo $p$ by Euler’s Criterion. $\blacksquare$

Remark
Each number in the set $\left\{1,2,3,\cdots,p-1 \right\}$ is congruent to a power of the primitive root $g$ in question. Lemma 2 indicates that the even powers are the quadratic residues while the odd powers are the quadratic nonresidues. The following lemma is a corollary of Lemma 2.

Lemma 3

Let $p$ be an odd prime. Then we have the following.

1. If $a$ and $b$ are quadratic residues modulo $p$, then $ab$ is a quadratic residue modulo $p$.
2. If $a$ is a quadratic residue and $b$ is a quadratic nonresidue modulo $p$, then $ab$ is a quadratic nonresidue modulo $p$.
3. If $a$ and $b$ are quadratic nonresidues modulo $p$, then $ab$ is a quadratic residue modulo $p$.

Proof of Lemma 3
Let $g$ be a primitive root modulo $p$. Then we express each residue or nonresidue as a power of $g$ and then multiply the two powers of $g$ by adding the exponents as in the following.

$\displaystyle g^{2j} \cdot g^{2k}=g^{2(j+k)}$

$\displaystyle g^{2j} \cdot g^{2k+1}=g^{2(j+k)+1}$

$\displaystyle g^{2j+1} \cdot g^{2k+1}=g^{2(j+k+1)}$

The first product above has an even exponent. Thus the product of two quadratic residues is a quadratic residue (the first bullet point). The second product above has an odd exponent. Thus the product of a quadratic residue and a quadratic nonresidue is a nonresidue (second bullet point). The third product above has an even exponent. Thus the product of two nonresidues is a residue. $\blacksquare$

One part of the following theorem is a corollary of Lemma 3.

Theorem 4

Let $p$ be an odd prime. Then we have the following results.

1. If $p \not \lvert \ a$ and $a \equiv b \ (\text{mod} \ p)$, then $\displaystyle \biggl(\frac{a}{p}\biggr)=\biggl(\frac{b}{p}\biggr)$.
2. If $p \not \lvert \ a$, then $\displaystyle \biggl(\frac{a^2}{p}\biggr)=1$.
3. if $p \not \lvert \ a$ and $p \not \lvert \ b$, then $\displaystyle \biggl(\frac{a}{p}\biggr) \cdot \biggl(\frac{b}{p}\biggr)=\biggl(\frac{ab}{p}\biggr)$.

Proof of Theorem 4
The first and second bullets points are straightforward. We prove the third bullet point, which follows from Lemma 3. Given $a$ and $b$, they would fall into one of the three cases of Lemma 3. Translating each case of Lemma 3 will give the correct statement in Legendre symbol. $\blacksquare$

____________________________________________________________________________

Quadratic reciprocity is a property that indicates how $\displaystyle \biggl(\frac{p}{q}\biggr)$ and $\displaystyle \biggl(\frac{q}{p}\biggr)$ are related when both $p$ and $q$ are odd prime. Even thought the statement of the theorem is easy to state and understand, it is an unexpected and profound result. Our goal here is quite simple – state the theorem and demonstrate how it can be used to simplify calculations. We have the following theorems.

Let $p$ and $q$ be two distinct odd prime numbers. The following statement holds.

$\displaystyle \biggl(\frac{q}{p}\biggr)=\left\{\begin{matrix} \displaystyle \biggl(\frac{p}{q}\biggr) &\ \text{if } p \equiv 1 \ (\text{mod} \ 4) \text{ or } q \equiv 1 \ (\text{mod} \ 4) \\{\displaystyle -\biggl(\frac{p}{q}\biggr)}&\ \text{if } p \equiv q \equiv 3 \ (\text{mod} \ 4) \end{matrix}\right.$

Theorem 6

Let $p$ and $q$ be two distinct odd prime numbers. The following statement holds.

$\displaystyle \biggl(\frac{2}{p}\biggr)=\left\{\begin{matrix} 1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 8) \text{ or } p \equiv 7 \ (\text{mod} \ 8) \\{-1}&\ \text{if } p \equiv 3 \ (\text{mod} \ 8) \text{ or } p \equiv 5 \ (\text{mod} \ 8) \end{matrix}\right.$

Theorem 7

Let $p$ and $q$ be two distinct odd prime numbers. The following statement holds.

$\displaystyle \biggl(\frac{-1}{p}\biggr)=\left\{\begin{matrix} 1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 4) \\{-1}&\ \text{if } p \equiv 3 \ (\text{mod} \ 4) \end{matrix}\right.$

Theorems 4, 5, 6 and 7 are tools for evaluating Legendre symbols. We demonstrate with examples.

____________________________________________________________________________

Examples

Example 1
Is $1776$ a quadratic residue modulo the prime $1777$?

We evaluate the symbol $\displaystyle \biggl(\frac{1776}{1777}\biggr)=\biggl(\frac{-1}{1777}\biggr)$. Note that $1777 \equiv 1 \ (\text{mod} \ 4)$. By Theorem 7, $\displaystyle \biggl(\frac{-1}{1777}\biggr)=1$. It follows that $1776$ is a quadratic residue modulo the prime $1777$. Furthermore, $x^2 \equiv 1776 \ (\text{mod} \ 1777)$ has solutions.

Example 2
Solve $x^2 \equiv 899 \ (\text{mod} \ 50261)$.

Note that $50261$ is a prime while $899$ is not since $899=29 \cdot 31$. After applying Theorem 4, we have:

$\displaystyle \biggl(\frac{899}{50261}\biggr)=\displaystyle \biggl(\frac{29}{50261}\biggr) \displaystyle \biggl(\frac{31}{50261}\biggr)$.

Now we can start using quadratic reciprocity.

\displaystyle \begin{aligned} \displaystyle \biggl(\frac{899}{50261}\biggr)&=\displaystyle \biggl(\frac{29}{50261}\biggr) \biggl(\frac{31}{50261}\biggr) \\&=\displaystyle \biggl(\frac{50261}{29}\biggr) \biggl(\frac{50261}{31}\biggr) \\&=\displaystyle \biggl(\frac{4}{29}\biggr) \biggl(\frac{10}{31}\biggr) \\&=\displaystyle \biggl(\frac{2}{29}\biggr)^2 \biggl(\frac{2}{31}\biggr) \biggl(\frac{5}{31}\biggr) \\&=(-1)^2 \cdot 1 \cdot 1 \\&=1 \end{aligned}

The above derivation is the result of applying Theorems 4, 5 and 7. Of particular importance is the repeated applications of Theorem 5 (Quadratic Reciprocity) so that the numbers in the Legendre symbols are much smaller than the ones we start with.

As useful as it is, the theorem for quadratic reciprocity does not show us how to solve the equation $x^2 \equiv 899 \ (\text{mod} \ 50261)$. See Example 2 in the post Solving Quadratic Congruences to see how it can be solved.

____________________________________________________________________________

$\copyright \ 2013 - 2015 \text{ by Dan Ma}$
Revised December 9, 2015