# Mersenne Prime

A Mersenne number is an integer that is one less than a power of 2, i.e. it is of the form $2^n-1$ where $n$ is a positive integer. A Mersenne prime number (or a Mersenne prime) is a Mersenne number that happens to be a prime number. This post is a brief discussion on Mersenne prime.

Because Mersenne numbers are exponential, they increase very rapidly. The first several Mersenne numbers $2^n-1$ starting with $n$ = 2.

3, 7, 15, 31, 63, 127, 255, 511, 1,023, 2,047, 4,095, 8,191, 16,383, 32,767, ……

It is clear from these examples that not all Mersenne numbers are prime (e.g. 15 and 63). In the above list, the numbers in red are prime and the ones in blue are composite. Note that the ones with composite exponent $n$ are composite: 15 ($n$ = 4), 63 ($n$ = 6), 255 ($n$ = 8), 511 ($n$ = 9) …. This is no coincidence.

Whenever $n$ is composite, the Mersenne number $2^n-1$ is also composite.

The fact follows from the following identity.

\displaystyle \begin{aligned} 2^{ab}-1&=(2^a-1) \ (1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}) \\&=(2^b-1) \ (1+2^b+2^{2b}+2^{3b}+\cdots+2^{(a-1)b}) \end{aligned}

Thus if we are interested in finding numbers $2^n-1$ that are prime, we must start with an exponent $n$ that is prime. For ease of discussion, define $M_p=2^p-1$ and assume that $p$ is prime.

Mersenne primes have a long history. Long before the computer age, people had been doing primality testing on Mersenne numbers. The first four Mersenne primes $M_p$, for $p$ = 2, 3, 5, and 7, were known in antiquity. The next Mersenne prime $M_{13}$ was discovered before 1461. People at that time thought that $M_p$ is prime whenever $p$ is prime. In 1536, Hudalricus Regius found that $M_{11}=2^{11}-1=2047=23 \times 89$. In 1603, Pietro Cataldi showed that $M_p$ is prime for $p$ = 17 and 19.

The name of Mersenne prime was due to the connection with the French monk Marin Mersenne. In his 1644 book Cognita Physico-Mathematica, Mersenne stated that $M_p$ is prime when $p$ = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257. Some of these claims were later determined to be wrong. His list also missed some correct Mersenne primes. From then on, his name was attached to this particular type of prime numbers.

The next discovery of a Mersenne prime (after Pietro Cataldi), $M_{31}$, was made by Leonhard Euler in 1772. The one found after Euler’s, $M_{127}$, was made by Edouard Lucas in 1876. There were three more Mersenne primes discovered before the computer age – $M_{61}$ in 1883 by Ivan Pervushin, $M_{89}$ and $M_{107}$ by R. E. Powers in 1911 and 1914, respectively.

In the pre-computer age, there were long stretches of time in between discoveries of Mersenne primes. For example, it took almost 200 years after Pietro Cataldi for the next Mersenne prime to emerge (discovered by Euler). There were about 100 years in between Euler’s discovery and Lucas’ discovery.

Another important contribution made by Lucas is a test that he developed to test Mersenne numbers to see if they are prime. The test was originally developed in 1856 and later improved by him in 1878. It was further improved by Derrick Henry Lehmer in the 1930s. The test is now known as the Lucas-Lehmer test.

Lucas-Lehmer Test. Define a sequence of positive integers $S_0, S_1, S_2, S_3, \cdots$ such that $S_0=4$ and $S_j=S_{j-1}^2-2$ where $j \ge 1$. Suppose that $p \ge 3$. Then $M_p=2^p-1$ is a Mersenne prime if and only if $M_p$ divides $S_{p-2}$.

To perform the test, start with $S_0=4$ and recursively calculate $S_j=S_{j-1}^2-2$ until $S_{p-2}$ is obtained. Then perform the division of $S_{p-2}$ by $M_p$. If $S_{p-2}$ is divisible by $M_p$, then $M_p$ is prime. If $S_{p-2}$ is not divisible by $M_p$, then $M_p$ is composite. It is interesting that when $M_p$ is found to be composite in this manner, the compositeness of $M_p$ is established without finding any prime factors of $M_p$.

The computer discoveries of Mersenne primes began in 1952 by Raphael Robinson. The Lucas–Lehmer test is the primality test used by the Great Internet Mersenne Prime Search (GIMPS) to discover large primes. GIMPS is a distributed computing project on the Internet for finding large prime numbers.

As of the writing of this post (May 25, 2017), a total of 49 Mersenne primes had been discovered. The latest one is $M_{74207281}$, with over 22 million digits, which was found in January 2016.

Despite of the computation advance, there are still many fundamental questions that are still not known about Mersenne primes. For example, how many Mersenne primes are there? It is not even known whether the set of Mersenne primes is finite or infinite. It is also not known whether infinitely many Mersenne numbers with prime exponents are composite.

Because of the Lucas-Lehmer test, whenever someone finds a new largest prime number, it is usually a Mersenne prime. So every few years or so, Mersenne prime is on the news for the reason of being discovered. For up-to-date information or to learn more about basic facts, go to the Mersenne prime website and the Wikipedia entry on Mersenne primes.

____________________________________________________________________________
$\copyright$ 2017 – Dan Ma

# Fermat numbers

Two previous posts (here and here) present an alternative proof that there are infinitely many prime numbers using the Fermat numbers. Specifically, the proof is accomplished by pointing out that the prime factors of the Fermat numbers form an infinite set. This post takes a look at Fermat numbers in more details.

A Fermat number is of the form $\displaystyle F_n=2^{2^n}+1$ where $n=0,1,2,3,\cdots$. The numbers grow very rapidly since each Fermat number is obtained by raising 2 to a power of 2. The first several terms are 3, 5, 17, 257, 65,537, 4,294,967,297. They are named after the French mathematicians Pierre de Fermat (1601-1665). He demonstrated that the first 5 Fermat numbers $F_0$, $F_1$, $F_2$, $F_3$, $F_4$ are prime and conjectured that all Fermat numbers are prime. In 1732, Euler provided a counterexample to the conjecture by showing that

$\displaystyle F_5=2^{2^5}+1=2^{32}+1=4294967297=641 \times 6700417$

Any Fermat number that is also a prime number is said to be a Fermat prime. Other than $F_0$, $F_1$, $F_2$, $F_3$, $F_4$, no additional Fermat primes have been discovered.

Euler likely did not factor $F_5$ by trial division. Euler discovered that the prime factors of Fermat numbers have a specific form. This discovery led to 641 being a factor of $F_5$. We discussed this result and other basic facts of Fermat numbers as well as the Pepin’s test, which is a primality testing algorithm that works on Fermat numbers as well as the Pepin’s test.

____________________________________________________________________________

Basic Results

One interesting fact is that Fermat numbers can be defined (or generated) recursively. Any Fermat number can be derived by taking the product of all the preceding Fermat numbers plus 2. Another basic fact is that the Fermat numbers are pairwise relatively prime, i.e. any two Fermat numbers have no common factor other 1. These two facts are stated in Theorem 1 and Theorem 2 below, which are proved in this previous post.

Theorem 1
For $n \ge 1$, we have the following results:

• $F_n=(F_{n-1}-1)^2+1$.
• $F_n=F_0 \times \cdots \times F_{n-1}+2$.

Theorem 2
For $i \ne j$, $F_i$ and $F_j$ are relatively prime.

A corollary of Theorem 1 and Theorem 2 is that there are infinitely many prime numbers. Another corollary of Theorem 1 is that all Fermat numbers, except for the first two, end in the digit of 7.

Corollary 3
There are infinitely many prime numbers.

Corollary 4
For $n \ge 2$, the last digit of $F_n$ is 7.

To see Corollary 3, if $F_n$ is prime, then let $p_n=F_n$. If not, let $p_n$ be the smallest prime factor of $F_n$. By Theorem 2, the prime numbers $p_n$ are pairwise relatively prime, hence pairwise distinct.

To see Corollary 4, note that $F_n \equiv 2 \ (\text{mod} \ F_j)$ for $j (this follows from Theorem 1). In particular, $F_n \equiv 2 \ (\text{mod} \ 5)$. Equivalently, $F_n-2=5k$ for some integer $k$. Since all $F_n$ are odd, $k$ is odd. Thus $k=2j+1$ for some $j$ and $F_n-2=10j+5$. Subtracting 5 on both sides gives $F_n-7=10j$. This means that $F_n \equiv 7 \ (\text{mod} \ 10)$.

____________________________________________________________________________

The Prime Factors of Fermat Numbers

The Fermat numbers $F_0$ to $F_{4}$ are prime. No additional Fermat primes had been identified since the time of Fermat. The Fermat numbers $F_5$ to $F_{11}$ have been completely factored. With a few exceptions, the numbers $F_{12}$ to $F_{43}$ are partially factored. The exceptions: $F_{20}$ and $F_{24}$ are shown to be composite (with no known factors) while $F_{33}$ to $F_{35}$ and $F_{40}$ and $F_{41}$ have unknown status. Beyond $F_{43}$, there is a long list of partially factored $F_n$ for $43. For the most up to date factoring status of Fermat numbers, see here.

There are no known Fermat primes other than the first five ($F_0$ to $F_4$). For the Fermat numbers beyond $F_4$, there are only finite number of them that are known to be composite. There are interesting and natural questions that can be raised about Fermat numbers. Is there another Fermat prime? Are there infinitely many Fermat primes (Eisenstein 1844)? Are there infinitely many composite Fermat numbers? Is $F_n$ composite for all $n>4$?

In this section, we consider some basic facts about prime factors of Fermat numbers. What if we relax the definition of Fermat numbers by considering the numbers $2^m+1$ where $m$ is a nonnegative integer that does not necessarily have to be a power of 2? Can $2^m+1$ be a prime number? It turns out that if we want to look at $2^m+1$ that are prime numbers, we have to restrict our attention to Fermat numbers. This is stated more formally in Theorem 5.

Theorem 5
If $2^m+1$ is a prime number, then $m$ is a power of 2.

Proof of Theorem 5
Let $2^m+1$ be a prime number. Let $m=b \times 2^w$ where $w \ge 0$ and $b \ge 1$ is odd. Now $2^m+1=(2^{2^w})^b+1$. To make it easy to see the argument, let $A=2^{2^w}$ and $B=-1$. Note that $(2^{2^w})^b+1=A^b-B^b$. Furthermore $A-B=2^{2^w}+1$ divides $A^b-B^b$. This means that $2^{2^w}+1$ is a factor of $2^m+1$. Since $2^m+1$ is prime, $2^{2^w}+1=2^m+1$. That implies that $b=1$. As a result, $m=2^w$. $\square$

Theorem 5 is a useful result. It tells us that 2 raised to odd power plus 1 can never be prime. For example, $2^{11}+1$ is not prime. Without any calculation, we known that $2^w+1$ is composite if $w$ = 2,305,843,009,213,693,953. On the other hand, 2 raised to any even power is not prime as long as the even power is not a power of 2. For example, $2^{20}+1$ is not prime. Just to be clear, when $m$ is a power of 2, it does not mean $2^m+1$ is a prime. The Fermat number $F_5$ is a counterexample. The property in Theorem 5 is a necessary and not a sufficient condition. So far we only know of five example of prime $2^m+1$ where $m$ is a power of 2. We next consider the prime factors of a Fermat number.

Theorem 6 (Euler-Lucas)
For any integer $n \ge 2$, any prime factor $p$ of $F_n=2^{2^n}+1$ is of the form $p=k \times 2^{n+2}+1$ for some integer $k$.

Proof of Theorem 6
Let $p$ be a prime factor of $F_n$. From the definition of Fermat numbers, observe that $2^{2^n} \equiv -1 \ (\text{mod} \ p)$. Squaring both sides gives $2^{2^{n+1}} \equiv 1 \ (\text{mod} \ p)$. We claim that the order of the element 2 modulo $p$ is $2^{n+1}$. Suppose the order of the element 2 modulo $p$ is $2^{j}$ where $j, equivalently $j \le n$. Then $2^{2^{j}} \equiv 1 \ (\text{mod} \ p)$ and $2^{2^{n}} \equiv 1 \ (\text{mod} \ p)$, a contradiction. Thus the claim is true.

Furthermore, the order of 2 modulo $p$ would divide $\phi(p)=p-1$ where $\phi(\cdot)$ is the Euler's phi function (see corollary 5 here). Thus $2^{n+1}$ would divide $p-1$ or $p=j \times 2^{n+1}+1$ for some $j$.

The result in the preceding paragraph is the result of Euler. Now to the improvement by Lucas. Since $n \ge 2$, $p \equiv 1 \ (\text{mod} \ 8)$. By the second supplement to the law of quadratic reciprocity (Theorem 8 found here), the element 2 is a quadratic residue modulo $p$. This means that $r^2 \equiv 2 \ (\text{mod} \ p)$ for some integer $r$. Raise both sides to $2^{n+1}$ gives $r^{2^{n+2}} \equiv 2^{2^{n+1}} \equiv 1 \ (\text{mod} \ p)$. We claim that the order of the element $r$ modulo $p$ is $2^{n+2}$. Suppose the order of the element $r$ modulo $p$ is $2^{j}$ where $j, or equivalently $j \le n+1$. Then $r^{2^{j}} \equiv 1 \ (\text{mod} \ p)$ and $r^{2^{n+1}} \equiv 1 \ (\text{mod} \ p)$. Note that $r^{2^{n+1}} \equiv (r^2)^{2^n} \equiv 2^{2^n} \equiv 1 \ (\text{mod} \ p)$. This contradicts the congruence $2^{2^n} \equiv -1 \ (\text{mod} \ p)$ observed earlier. The claim is established.

As a result of the fact that the order of the element $r$ modulo $p$ is $2^{n+2}$, $2^{n+2}$ divides $\phi(p)=p-1$. Equivalently, $p=k \times 2^{n+2}+1$ for some $k$. $\square$

When a Fermat number is determined to be composite (e.g. via Theorem 7 below), Theorem 6 indicates that its prime factors are of a certain form. For the Fermat number $F_5$, the factor 641 can be derived as follows. First, note the following two relations.

$641=5 \times 2^7+1$

$641=5^4+2^4$

From the first fact, $5 \cdot 2^7 \equiv -1 \ (\text{mod} \ 641)$. Raising both sides to 4 gives $5^4 \cdot 2^{28} \equiv 1 \ (\text{mod} \ 641)$. From the second fact, $5^4 \equiv -2^4 \ (\text{mod} \ 641)$. Combining the two congruences gives $-2^4 \cdot 2^{28} \equiv - 2^{32} \equiv 1 \ (\text{mod} \ 641)$, which means that 641 divides $F_5=2^{32}+1$.

____________________________________________________________________________

Primality Testing of Fermat Numbers

Because the Fermat numbers grow so rapidly, factoring large Fermat numbers is a challenge. However, there is a polynomial-time algorithm that determines the primality of a Fermat number (see Theorem 7 below). But even this test is limited because of the rapid growth of Fermat numbers.

Theorem 7 (Pepin’s Test)
For $n \ge 1$, the Fermat number $F_n=2^{2^n}+1$ is a prime number if and only if $\displaystyle 3^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n)$.

Proof of Theorem 7
Suppose that $F_n=2^{2^n}+1$ is prime where $n \ge 1$. We claim that the number 3 is a quadratic nonresidue modulo $F_n$. Once this is established, the congruence $\displaystyle 3^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n)$ would follow by appealing to Euler’s criterion (see Theorem 1 here). To see the claim, note that

$\displaystyle \biggl( \frac{3}{F_n} \biggr)=\biggl( \frac{F_n}{3} \biggr)=\biggl( \frac{2}{3} \biggr)=-1$

The above symbols are Legendre symbols since $F_n$ is a prime number. The first symbol can be flipped without changing the sign since $F_n \equiv 1 \ (\text{mod} \ 4)$. This is according to the law of quadratic reciprocity (see Theorem 6 here). It follows from the first bullet point in Theorem 1 that $F_n \equiv 2 \ (\text{mod} \ 3)$ for all $n \ge 1$. Thus the second Legendre symbol above is the same as the third symbol. Lastly, 2 is a quadratic nonresidue modulo 3. Thus the third Legendre symbol above equals -1. By Euler’s criterion, this means that the congruence $\displaystyle 3^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n)$ holds.

The other direction uses Lucas’ primality test, which is a test that proves the primality for any integer $p$ such that the factorization of $p-1$ is completely known. Fermat numbers fit the requirement since $F_n-1$ is a power of 2. For the statement and proof of Lucas’ primality test, see Theorem 1 here. To show the other direction, suppose that $\displaystyle 3^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n)$ where $n \ge 1$. Clearly, $\displaystyle 3^{F_n-1} \equiv 1 \ (\text{mod} \ F_n)$. By Lucas’ primality test, $F_n$ is prime. $\square$

The number 3 is the base used in the Pepin’s test as stated in Theorem 7. Other bases can be used, e.g. 5. The following is the Pepin’s test using 5 as the base.

Theorem 8 (Pepin’s Test)
For $n \ge 2$, the Fermat number $F_n=2^{2^n}+1$ is a prime number if and only if $\displaystyle 5^{\frac{F_n-1}{2}} \equiv -1 \ (\text{mod} \ F_n)$.

The proof for Theorem 8 works similarly. If $F_n$ is prime, it can be shown that 5 is a quadratic nonresidue modulo $F_n$.

To determine whether a given Fermat number $F_n$ is prime, simply compute the congruence $\displaystyle 3^{\frac{F_n-1}{2}} \ (\text{mod} \ F_n)$. If the result is -1, then $F_n$ being tested is a prime number. If the congruence is not -1, then $F_n$ is composite. Note that the results from Pepin’s test can only tell whether the given Fermat number is prime or composite. If the test result says composite, it does not indicate what the factors are. The following shows the test results for $F_4$ to $F_{10}$.

$\displaystyle 3^{\frac{F_4-1}{2}} \equiv 65536 \equiv -1 \ (\text{mod} \ F_4)$

$\displaystyle 3^{\frac{F_5-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_5)$
where $T$ = 10,324,303
and $F_5$ = 4,294,967,297

$\displaystyle 3^{\frac{F_6-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_6)$
where $T$ = 11,860,219,800,640,380,469
and $F_6$ = 18,446,744,073,709,551,617

$\displaystyle 3^{\frac{F_7-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_7)$
where $T$ = 110,780,954,395,540,516,579,111,562,860,048,860,420
and $F_7$ = 340,282,366,920,938,463,463,374,607,431,768,211,457

$\displaystyle 3^{\frac{F_8-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_8)$
where $T$ = 005,864,545,399,742,183,862,578,018,016,183,410,025,465,491,904,722,516,203,269,973,267,547,486,512,819
and $F_8$ = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,937

$\displaystyle 3^{\frac{F_9-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_9)$
where $T$ =
03,487,842,192,292,834,160,828,677,804,926,452,873,307,656,935,026,758,634,839,951,511,167,913,561,583
764,893,191,647,059,299,508,808,058,740,314,515,096,456,032,583,684,082,248,245,196,170,211,101,691,254
and $F_9$ =
13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,030,073
546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,649,006,084,097

$\displaystyle 3^{\frac{F_{10}-1}{2}} \equiv T \not \equiv -1 \ (\text{mod} \ F_{10})$
where $T$ =
387,619,810,475,491,122,179,739,047,140,959,275,426,443,598,784,645,243,238,994,975,074,552,393,367
151,669,166,056,942,068,042,567,969,383,237,719,504,044,259,561,712,002,215,552,049,762,078,784,904
229,994,959,756,192,565,270,005,114,398,071,628,663,530,167,797,163,602,701,669,757,405,752,156,537
276,004,764,083,329,886,967,333,347,443,567,401,688,754,399,623,980,380,190,579,140,626,590,345,932,472,472
and $F_9$ =
179,769,313,486,231,590,772,930,519,078,902,473,361,797,697,894,230,657,273,430,081,157,732,675,805
500,963,132,708,477,322,407,536,021,120,113,879,871,393,357,658,789,768,814,416,622,492,847,430,639
474,124,377,767,893,424,865,485,276,302,219,601,246,094,119,453,082,952,085,005,768,838,150,682,342
462,881,473,913,110,540,827,237,163,350,510,684,586,298,239,947,245,938,479,716,304,835,356,329,624,224,137,217

____________________________________________________________________________

Remarks

The above calculations can be performed on a calculator that can handle modular exponentiation or be programmed in a computer. The above calculations point to the reality that it is much easier to determine the status of primality/compositeness of a number than the factorization. For example, the compositeness of $F_8$ was known in 1909 but the factors were not found until 1980.

The modular exponentiations displayed above, 3 raised to $(F_n-1)/2$, can be accomplished by performing a series of squaring and multiplications. This approach is called the square-and-multiply approach or the fast powering algorithm. In this algorithm, the binary expansion of the exponent is used to convert the exponentiation into a series of squarings and multiplications. See here for a description of the fast powering algorithm. See here for a simpler description. One interesting point that can be made about the calculation for the Pepin’s test is that the exponent is a power of 2. As a result, there is only one non-zero bit in the binary expansion (the highest bit). So the square-and-multiply only consists of squarings. In any programming attempt, the “multiply” part can be skipped.

The algorithm described in Theorem 7 (Pepin’s test) is a polynomial-time algorithm assuming that the input $F_n$ is written in binary or decimal numbers. It seems that one can simply apply Pepin’s test on larger and larger Fermat numbers to gain more insight on the open questions on Fermat numbers. However, Pepin’s test, though efficient, is also a limited test. Because the exponent in the test is a power of 2 that increases rapidly, the test reaches a computational limit rather quickly.

Let’s look at the computational limit through $F_{33}$, which is the least Fermat number with unknown status. It has 2,585,827,973 decimal digits. In applying Pepin’s test, the exponent would be $2^{2^{33}-1}$, which has $2^{33}$ = 8,589,934,593 many bits in the binary expansion (that’s the number of squarings required in the fast powering algorithm, over 8.5 billions)! Thus applying Pepin’s test (in conjunction with the fast powering algorithm) on the larger Fermat numbers is no small feat. The following comments from [1] give a good perspective on the Pepin’s test.

The first Fermat number of unresolved character is thus $F_{33}$. By conventional machinery and Pepin test, the resolution of $F_{33}$ would take us well beyond the next ice age! So the need for new algorithms is as strong as can be for future work on giant Fermat numbers.

According to the comments made in Wikipedia, Pepin’s test had been used 8 times in resolving the prime/composite status of Fermat numbers. To tackle large Fermat numbers, technology improvement (hardware, software and algorithm) will be needed. Thus progress may take decades or more.

There is one interesting question about Pepin’s test. What are all the possible bases that can be used in this test? Are there other bases beside 3 and 5? This is discussed in in another blog post.

____________________________________________________________________________

Reference

1. Crandall R., Pomerance C,Prime Numbers, A Computational Perspective, Second Edition, Springer, New York, 2005

____________________________________________________________________________
$\copyright \ 2016 \text{ by Dan Ma}$

# Tweaking a proof of the infinitude of primes

This blog presents two proofs of the infinitude of primes. The first one is the standard proof that is due to Euclid (around 300 BC). The second one is due to Christian Goldbach (from a letter to Leonhard Euler in 1730). This post attempts to generalize the second one. The goal is to capture the essence of the proof and in the process gains a better perspective. Reading the second proof is not a prerequisite. The reader is welcome to compare the argument here with the previous proof to appreciate the economy that is in the tweaked proof.

____________________________________________________________________________

The Tweak

The existence of the following sequence will imply that there are infinitely many prime numbers.

There is a sequence of positive odd integers $x_0,x_1,x_3, \cdots$ such that

• $x_0 < x_1 < x_3 < \cdots$,
• any two elements of the sequence are relatively prime, i.e. for $i \ne j$, the terms $x_i$ and $x_j$ have no common divisor other than 1.

If such a sequence exists, we can infer an infinite sequence of prime numbers. Note that each term $x_j$ is a product of distinct primes. Let $p_j$ be the smallest prime factor of $x_j$. The prime numbers $p_j$ must be distinct since the elements in the sequence $x_0,x_1,x_3, \cdots$ are pairwise relatively prime.

How do we know if such a sequence exists? It can be defined recursively. Let $x_0 be any odd positive integers that are relatively prime. For example, $x_0=3$ and $x_1=5$. Another example: $x_0=21$ and $x_1=55$. Then for each $n>1$, let $x_n=x_0 \times x_1 \times \cdots \times x_{n-1}+2$. Clearly the sequence is increasing. To see that any two terms of the sequence are relatively prime, let $j and let $d$ be a common divisor of $x_j$ and $x_n$. Since $d$ divides $x_j$, it is clear that $d$ divides $x_0 \times x_1 \times \cdots \times x_{n-1}$. This means that $d$ divides $x_n-x_0 \times x_1 \times \cdots \times x_{n-1}=2$. With $d$ being odd and $d$ dividing 2, it must be that $d=1$.

The proof in the previous post essentially uses the above argument with the first two terms fixed at $x_0=3$ and $x_1=5$. With these two initial choices, it can be shown that the sequence $x_0,x_1,x_3, \cdots$ consists of the Fermat numbers. It is nice to know that the resulting sequence consists of the Fermat numbers. However, for proving that primes are infinite, the fact about Fermat numbers is immaterial. For example, if the initial two terms are $x_0=21$ and $x_1=55$, the same argument will still lead to an infinite sequence of prime numbers. Using Fermat numbers is one way to derive the sequence in question. Sometimes a broader picture picture can be obscured by being too specific in the argument.

____________________________________________________________________________

An Equivalent Statement

The above argument for the infinitude of primes points to the fact that the existence of an infinite sequence of prime numbers is reduced to the existence of a sequence as described in the above argument. We have the following theorem.

Theorem
The following two statements are equivalent.

• There exists a sequence of positive odd integers $x_0,x_1,x_3, \cdots$ such that $x_0 < x_1 < x_3 < \cdots$ and such that any two terms of the sequence are relatively prime.
• There are infinitely many prime numbers.

It is clear that if there are infinitely many primes, the sequence $x_0,x_1,x_3, \cdots$ can simply be made the primes. So one direction is obvious. The other direction is proved by the above argument.

The theorem essentially says that the “infinity” of primes is identical to the “infinity” of numbers that are pairwise relatively prime. Of course, the purpose of discussing the latter is to give an argument that there are infinitely many primes.

____________________________________________________________________________
$\copyright \ 2016 \text{ by Dan Ma}$

# The Jacobi symbol

The Jacobi symbol is a generalization of the Legendre symbol. In this post, we define the Jacobi symbol and discuss some of its important properties. The Legendre symbol (coupled with the law of reciprocity) is a useful tool in determining whether a number is a quadratic residue modulo an odd prime. However, the Legendre symbol is also restrictive since the bottom argument must be a prime. The Jacobi symbol generalizes the Legendre symbol and in many cases is easier to evaluate than the Legendre symbol. This is demonstrated in several examples.

____________________________________________________________________________

Defining The Jacobi Symbol

The Legendre symbol is $\displaystyle \biggl(\frac{a}{p}\biggr)$ where the bottom argument is always an odd prime and the top argument can be any integer. When $a$ is an integer that is relatively prime to the odd prime $p$, the Legendre symbol $\displaystyle \biggl(\frac{a}{p}\biggr)$ carries information on whether the integer $a$ is quadratic residue modulo $p$. The following gives the definition of the Legendre symbol.

$\displaystyle \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl} 0 &\ \text{if } a \equiv 0 \ (\text{mod} \ p) \\ 1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a \text{ is a quadratic residue modulo }p\\ -1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a \text{ is a quadratic nonresidue modulo }p \end{array} \right.$

The Jacobi symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$ has the same look as the Legendre symbol. The top argument can be any integer. The bottom argument is an odd positive integer. If the odd positive integer $n>1$ has the prime factorization $n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_t^{e_t}$, the Jacobi symbol is defined as follows:

$\displaystyle \biggl(\frac{a}{n}\biggr)=\biggl(\frac{a}{p_1}\biggr)^{e_1} \times \biggl(\frac{a}{p_2}\biggr)^{e_2} \times \cdots \times \biggl(\frac{a}{p_t}\biggr)^{e_t}$

For convenience, we define $\displaystyle \biggl(\frac{a}{1}\biggr)=1$. A slightly different, but equivalent, definition is that whenever the odd integer $n>1$ has the prime factorization $n=q_1 \times q_2 \times \cdots \times q_k$ (the prime numbers $q_j$ are not necessarily distinct), the symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$ is defined as follows:

$\displaystyle \biggl(\frac{a}{n}\biggr)=\biggl(\frac{a}{q_1}\biggr) \times \biggl(\frac{a}{q_2}\biggr) \times \cdots \times \biggl(\frac{a}{q_k}\biggr)$

The Jacobi symbol is defined using the Legendre symbol according to the prime factorization of the bottom argument.

____________________________________________________________________________

Properties of The Jacobi Symbol

Now that the Jacobi symbol has been defined based on the Legendre symbol, there are two natural questions.

• Does the value of $\displaystyle \biggl(\frac{a}{n}\biggr)= \pm 1$ indicates that $a$ is a quadratic residue or nonresidue modulo $n$?
• The Legendre symbol follows a set of rules (e.g. the law of quadratic reciprocity) that make the Legendre symbol a versatile tool. Does the Jacobi symbol follow these rules? Conceptually, evaluating the Jacobi symbol requires factoring the bottom argument of the symbol. On the surface, this appears to be a limitation. However, if the Jacobi symbol follows the rules for the Legendre symbol including the law of quadratic reciprocity, it will be just as easy to evaluate the Jacobi symbol.

For the first question, the following is true: If $a$ is a quadratic residue modulo $n$, then $\displaystyle \biggl(\frac{a}{n}\biggr)=1$. The contrapositive of this statement is that if $\displaystyle \biggl(\frac{a}{n}\biggr)=-1$, then the number $a$ is a quadratic nonresidue modulo the odd integer $n$, i.e. the equation $x^2 \equiv a \ (\text{mod} \ n)$ has no solutions. However, the value of $\displaystyle \biggl(\frac{a}{n}\biggr)=1$ does not imply that $a$ is a quadratic residue modulo $n$. For example, $\displaystyle \biggl(\frac{2}{15}\biggr)=1$ but the equation $x^2 \equiv 2 \ (\text{mod} \ 15)$ has no solutions. Note that both equations $x^2 \equiv 2 \ (\text{mod} \ 3)$ and $x^2 \equiv 2 \ (\text{mod} \ 5)$ have no solutions. This means that the value of $\displaystyle \biggl(\frac{2}{15}\biggr)=1$ is the product of two Legendre symbols of -1.

Theorem 1
Let $n$ be an odd positive integer. Let $a$ be such that $\text{GCD}(a,n)=1$. Then If $a$ is a quadratic residue modulo $n$, then $\displaystyle \biggl(\frac{a}{n}\biggr)=1$. The converse does not hold if $n$ is not a prime.

Proof
Suppose that $a$ is a quadratic residue modulo $n$, i.e. the equation $x^2 \equiv a \ (\text{mod} \ n)$ has a solution. Let $n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_t^{e_t}$ be the prime factorization of $n$. Let $m_i=p_i^{e_i}$ for each $i$. By the Chinese remainder theorem, the equation $x^2 \equiv a \ (\text{mod} \ m_i)$ has a solution for each $i=1,2,\cdots,t$. it then follows that the equation $x^2 \equiv a \ (\text{mod} \ p_i)$ has a solution too for each $i=1,2,\cdots,t$. Hence the Legendre symbol $\displaystyle \biggl(\frac{a}{p_i}\biggr)=1$ for each $i$. It follows that the Jacobi symbol $\displaystyle \biggl(\frac{a}{n}\biggr)=1$. $\square$

For the second question, the rules that are obeyed by the Legendre symbol are also obeyed by the Jacobi symbol. Some of the rules are easily seen to carry over to the Jacobi symbol. The fact that the law of quadratic reciprocity and the two supplements are obeyed by the Jacobi symbol is not entirely obvious from the definition. However the proof is not difficult. We give a complete proof here.

Lemma 2
Let $a$ and $b$ be odd positive integers. The following two conditions hold.

$\displaystyle \frac{a-1}{2} \times \frac{b-1}{2} \equiv \frac{ab-1}{2} \ (\text{mod} \ 2)$

$\displaystyle \frac{a^2-1}{8} \times \frac{b^2-1}{8} \equiv \frac{(ab)^2-1}{8} \ (\text{mod} \ 2)$

Proof
The lemma is established by the following derivation:

$\displaystyle \frac{ab-1}{2}-\biggl[\frac{a-1}{2}+\frac{b-1}{2} \biggr]=\frac{ab-a-b+1}{2}=\frac{(a-1)(b-1)}{2}$

$\displaystyle \frac{(ab)^2-1}{8}-\biggl[\frac{a^2-1}{8}+\frac{b^2-1}{8} \biggr]=\frac{(ab)^2-a^2-b^2+1}{8}=\frac{(a^2-1)(b^2-1)}{8}$

Because both $a$ and $b$ are odd integers, the right-hand-side of both equations are even integers and thus $\equiv 0 \ (\text{mod} \ 2)$. $\square$

Theorem 3 (Properties of Jacobi Symbol)

1. $\displaystyle \biggl(\frac{a}{n}\biggr) = \left\{ \begin{array}{rl} 0 &\ \text{if } \text{GCD}(a,n) >1 \\ \pm 1 &\ \text{if } \text{GCD}(a,n)=1 \end{array} \right.$
2. $\text{ }$

3. If $n$ is a prime, then the Jacobi symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$ coincides with the Legendre symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$.
4. $\text{ }$

5. If $a \equiv b \ (\text{mod} \ n)$, then $\displaystyle \biggl(\frac{a}{n}\biggr)=\biggl(\frac{b}{n}\biggr)$.
6. $\text{ }$

7. The Jacobi symbol is multiplicative when the bottom argument is fixed, i.e. $\displaystyle \biggl(\frac{ab}{n}\biggr)=\biggl(\frac{a}{n}\biggr) \biggl(\frac{b}{n}\biggr)$.
8. $\text{ }$

9. The Jacobi symbol is multiplicative when the upper argument is fixed, i.e. $\displaystyle \biggl(\frac{a}{mn}\biggr)=\biggl(\frac{a}{m}\biggr) \biggl(\frac{a}{n}\biggr)$.
10. $\text{ }$

11. (The law of quadratic reciprocity)
Let $a$ and $b$ be relatively prime odd positive integers. Then

$\displaystyle \biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)=(-1)^{(a-1)/2 \times (b-1)/2}$

Equivalently, $\displaystyle \biggl(\frac{a}{b}\biggr) = \left\{ \begin{array}{rl} \displaystyle \biggl(\frac{b}{a}\biggr) &\ \text{if } a \equiv 1 \ (\text{mod} \ 4) \text{ or } b \equiv 1 \ (\text{mod} \ 4) \\ \displaystyle -\biggl(\frac{b}{a}\biggr) &\ \text{if } a \equiv b \equiv 3 \ (\text{mod} \ 4) \end{array} \right.$

12. (First supplement to the law of quadratic reciprocity)
Let $n$ be an odd positive integer. Then

$\displaystyle \biggl(\frac{-1}{n}\biggr)=(-1)^{(n-1)/2}$.

Equivalently, $\displaystyle \biggl(\frac{-1}{n}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } n \equiv 1 \ (\text{mod} \ 4) \\ -1 &\ \text{if } n \equiv 3 \ (\text{mod} \ 4) \end{array} \right.$

13. (Second supplement to the law of quadratic reciprocity)
Let $n$ be an odd positive integer. Then

$\displaystyle \biggl(\frac{2}{n}\biggr)=(-1)^{(n^2-1)/8}$.

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

Proof
For the first bullet point, if the top argument and the bottom argument have a prime factor in common, then one of the Legendre symbols that make up the Jacobi symbol is zero. If the top argument and the bottom argument have no prime factor in common, then all the Legendre symbols that make up the Jacobi symbol is either 1 or -1.

The second point is clear. If the bottom argument is an odd prime, the definition of Jacobi symbol leads to the Legendre symbol.

For bullet points 3, 4 and 5, simply write out the Jacobi symbol and then use the corresponding properties of the Legendre symbol.

Now the proof of bullet point 6 (the law of quadratic reciprocity). Let $a$ and $b$ be relatively prime. Let $a=p_1 \times p_2 \times \cdots \times p_w$ and $b=q_1 \times q_2 \times \cdots \times q_t$ be their prime factorizations. Note that the primes $p_i$ are not necessarily distinct and the primes $q_i$ are not necessarily distinct. However, $p_i \ne q_j$ since $a$ and $b$ are relatively prime. Consider the following derivation of the product $\displaystyle \biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)$.

\displaystyle \begin{aligned}\biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)&=\prod \limits_{i=1}^t \biggl(\frac{a}{q_i}\biggr) \ \prod \limits_{j=1}^w \biggl(\frac{b}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \ \prod \limits_{j=1}^w \prod \limits_{i=1}^t \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \ \prod \limits_{i=1}^t \prod \limits_{j=1}^w \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w (-1)^{(p_j-1)/2 \times (q_i-1)/2} \\&=(-1)^E \end{aligned}

where

$\displaystyle E=\sum \limits_{i,j} \biggl[\frac{p_j-1}{2} \times \frac{q_i-1}{2} \biggr]$

The bullet point 6 is established after the quantity $E$ is simplified as follows:

\displaystyle \begin{aligned} \sum \limits_{i,j} \biggl[\frac{p_j-1}{2} \times \frac{q_i-1}{2} \biggr]&=\sum_j \biggl[\sum_i \frac{q_i-1}{2}\biggr] \frac{p_j-1}{2} \\&\equiv \sum_j \biggl[ \frac{b-1}{2}\biggr] \frac{p_j-1}{2} \ \ \ \text{ Use Lemma 2}\\&\equiv \frac{b-1}{2} \sum_j \frac{p_j-1}{2} \\&\equiv \frac{b-1}{2} \frac{a-1}{2} \ (\text{mod} \ 2) \ \ \ \text{ Use Lemma 2} \end{aligned}

Now consider the bullet point #7 (the first supplement to the law of quadratic reciprocity). The proof is an induction proof on the number of prime factors of $n$. If $n$ is a prime, then it is done. So we assume $n=p_1 \times p_2$ (not necessarily distinct). Consider the following derivation:

\displaystyle \begin{aligned} \biggl(\frac{-1}{n}\biggr)&=\biggl(\frac{-1}{p_1}\biggr) \biggl(\frac{-1}{p_2}\biggr) \\&=(-1)^{(p_1-1)/2} \ (-1)^{(p_2-1)/2} \\&=(-1)^{(p_1-1)/2+(p_2-1)/2} \\&\equiv (-1)^{(p_1 \times p_2 -1)/2} \ \ \ \ \ \text{Use Lemma 2} \\&\equiv (-1)^{(n -1)/2} \ (\text{mod} \ 2) \end{aligned}

It is a straightforward argument that whenever the property is true for $n$ being a product of $k$ primes, the property is true for $n$ being a product of $k+1$ primes. Thus bullet 7 is established.

The proof of bullet point 8 (the second supplement to the law of quadratic reciprocity) is also an induction proof on the number of prime factors of $n$. The most important case is the of two prime factors.

\displaystyle \begin{aligned} \biggl(\frac{2}{n}\biggr)&=\biggl(\frac{2}{p_1}\biggr) \biggl(\frac{2}{p_2}\biggr) \\&=(-1)^{(p_1^2-1)/8} \ (-1)^{(p_2^2-1)/8} \\&=(-1)^{(p_1^2-1)/8+(p_2^2-1)/8} \\&\equiv (-1)^{((p_1 \times p_2)^2 -1)/8} \ \ \ \ \ \text{Use Lemma 2} \\&\equiv (-1)^{(n^2 -1)/8} \ (\text{mod} \ 2) \end{aligned}

With the 2-case established, it is straightforward to carry out the remainder of the induction proof of bullet 8. $\square$

____________________________________________________________________________

Examples

Example 1
Evaluate $\displaystyle \biggl(\frac{1783}{7523}\biggr)$, an example where both the upper and lower arguments are primes. In the previous post, the example is calculated using only Legendre symbol. Here we work it in Jacobi symbol. As much as possible, we flip the symbol without factoring.

\displaystyle \begin{aligned} \biggl(\frac{1783}{7523}\biggr)&=-\biggl(\frac{7523}{1783}\biggr) \\&=-\biggl(\frac{391}{1783}\biggr) \ \ *\\&=\biggl(\frac{1783}{391}\biggr) \\&=\biggl(\frac{219}{391}\biggr) \ \ *\\&=-\biggl(\frac{391}{219}\biggr) \\&=-\biggl(\frac{172}{219}\biggr) \\&=-\biggl(\frac{2}{219}\biggr)^2 \biggl(\frac{43}{219}\biggr) \\&=-\biggl(-1\biggr)^2 (-1) \biggl(\frac{219}{43}\biggr) \\&=\biggl(\frac{4}{43}\biggr) \\&=1 \end{aligned}

One advantage of using Jacobi symbol is that when the upper argument is an odd integer that is not prime, we can still flip it (the steps with *). Then reduce and then flip again until we reach a point with small numbers. Thinking in Legendre symbol only, the steps with * cannot be flipped. As Jacobi symbols, they can be flipped freely as long as the arguments are odd integers. The advantage may not be apparent in this example. When the composite integers are large to the point that their factorizations are in effect not obtainable, this advantage is huge. $\square$

Example 2
Evaluate $\displaystyle \biggl(\frac{a}{p}\biggr)$ where $p=$ 1298351, an odd prime and $a=$ 756479. This is Example 2 in this previous post. The number $a$ is not a prime. Here we use Jacobi symbol to demonstrate that factoring is not needed. We can start by flipping. We have the following derivation.

\displaystyle \begin{aligned} \biggl(\frac{756479}{1298351}\biggr)&=-\biggl(\frac{1298351}{756479}\biggr) \\&=-\biggl(\frac{541872}{756479}\biggr) \\&=-\biggl(\frac{2}{756479}\biggr)^4 \times \biggl(\frac{33867}{756479}\biggr) \\&=-\biggl(1\biggr)^4 \times (-1) \biggl(\frac{756479}{33867}\biggr) \\&=\biggl(\frac{11405}{33867}\biggr) \\&=\biggl(\frac{33867}{11405}\biggr) \\&=\biggl(\frac{11057}{11405}\biggr) \\&=\biggl(\frac{11405}{11057}\biggr) \\&=\biggl(\frac{348}{11057}\biggr) \\&=\biggl(\frac{2}{11057}\biggr)^2 \biggl(\frac{87}{11057} \biggr) \\&=\biggl(1\biggr)^2 \biggl(\frac{11057}{87} \biggr) \\&=\biggl(\frac{8}{87}\biggr) \\&=\biggl(\frac{2}{87} \biggr)^3 \\&=1 \end{aligned}

Note that the original symbol to evaluate is a Legendre symbol. The interim steps are done with Jacobi symbol as much as possible. With the Jacobi way, the symbol is flipped, reduced and flipped again multiple times. The derivation seems long. However, the flip-reduce-flip is much faster than factoring when the numbers involved are large. $\square$

Example 3
Evaluate $\displaystyle \biggl(\frac{a}{n}\biggr)$ where $n=$ 12408107 and $a=$ 4852777. Both numbers are not prime. The symbol has to be evaluated as a Jacobi symbol.

\displaystyle \begin{aligned} \biggl(\frac{4852777}{12408107}\biggr)&=\biggl(\frac{12408107}{4852777}\biggr) \\&= \biggl(\frac{2702553}{4852777}\biggr) \\&= \biggl(\frac{4852777}{2702553}\biggr) \\&= \biggl(\frac{2150224}{2702553}\biggr) \\&= \biggl(\frac{2}{2702553}\biggr)^4 \biggl(\frac{134389}{2702553}\biggr) \\&= \biggl(1\biggr)^4 \biggl(\frac{2702553}{134389}\biggr) \\&= \biggl(\frac{14773}{134389}\biggr) \\&= \biggl(\frac{134389}{14773}\biggr) \\&= \biggl(\frac{1432}{14773}\biggr) \\&= \biggl(\frac{2}{14773}\biggr)^3 \biggl(\frac{179}{14773}\biggr) \\&= \biggl(-1\biggr)^3 \biggl(\frac{14773}{179}\biggr) \\&= - \biggl(\frac{95}{179}\biggr) \\&= - (-1) \biggl(\frac{179}{95}\biggr) \\&=\biggl(\frac{84}{95}\biggr) \\&=\biggl(\frac{2}{95}\biggr)^2 \biggl(\frac{21}{95}\biggr) \\&=\biggl(1\biggr)^2 \biggl(\frac{95}{21}\biggr) \\&=\biggl(\frac{11}{21}\biggr) \\&=\biggl(\frac{21}{11}\biggr) \\&=\biggl(\frac{10}{11}\biggr) \\&=\biggl(\frac{2}{11}\biggr) \biggl(\frac{5}{11}\biggr) \\&=\biggl(-1\biggr) \biggl(\frac{11}{5}\biggr) \\&=-\biggl(\frac{6}{5}\biggr) \\&=-\biggl(\frac{2}{5}\biggr) \biggl(\frac{3}{5}\biggr) \\&=-\biggl(-1\biggr) \biggl(\frac{5}{3}\biggr) \\&=\biggl(\frac{2}{3}\biggr) \\&=-1 \end{aligned}

The above derivation seems long in that there are quite a few steps. But many of the steps are flip-reduce-flip-reduce that are easy to do. The steps are all done without factoring, except when the top argument is an even number. The Jacobi symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$ is -1. In this case, it gives definite information about the status of quadratic nonresidues. We know for sure that $a$ is a quadratic nonresidue modulo the odd integer $n$, i.e. the equation $x^2 \equiv a \ (\text{mod} \ n)$ has no solutions. $\square$

Example 4
Evaluate $\displaystyle \biggl(\frac{a}{n}\biggr)$ where $n=$ 48746413 and $a=$ 17327467. Both numbers are not prime. As in Example 3, the symbol is evaluated using Jacobi symbol.

\displaystyle \begin{aligned} \biggl(\frac{17327467}{48746413}\biggr) &=\biggl(\frac{48746413}{17327467}\biggr) \\&=\biggl(\frac{14091479}{17327467}\biggr) \\&=-\biggl(\frac{17327467}{14091479}\biggr) \\&=-\biggl(\frac{3236168}{14091479}\biggr) \\&=-\biggl(\frac{2}{14091479}\biggr)^3 \biggl(\frac{404521}{14091479}\biggr) \\&=-\biggl(1\biggr)^3 \biggl(\frac{14091479}{404521}\biggr) \\&=- \biggl(\frac{337765}{404521}\biggr) \\&=- \biggl(\frac{404521}{337765}\biggr) \\&=- \biggl(\frac{66756}{337765}\biggr) \\&=- \biggl(\frac{2}{337765}\biggr)^2 \biggl(\frac{16689}{337765}\biggr) \\&=- \biggl(-1\biggr)^2 \biggl(\frac{337765}{16689}\biggr) \\&=-\biggl(\frac{3985}{16689}\biggr) \\&=-\biggl(\frac{16689}{3985}\biggr) \\&=-\biggl(\frac{749}{3985}\biggr) \\&=-\biggl(\frac{3985}{749}\biggr) \\&=-\biggl(\frac{240}{749}\biggr) \\&=-\biggl(\frac{2}{749}\biggr)^4 \biggl(\frac{15}{749}\biggr) \\&=-\biggl(-1\biggr)^4 \biggl(\frac{749}{15}\biggr) \\&=-\biggl(\frac{14}{15}\biggr) \\&=-\biggl(\frac{-1}{15}\biggr)\\&=-(-1)\\&=1 \end{aligned}

The result of $\displaystyle \biggl(\frac{a}{n}\biggr)=1$ gives ambiguous information about the status of $a=$ 17327467 being a quadratic residue or nonresidue modulo $n=$ 48746413. In this case, the Jacobi symbol cannot tell us whether the equation $x^2 \equiv a \ (\text{mod} \ n)$ has a solution. In such a case, the only way to know the status of quadratic residue is to know some additional information, namely the factoring of the numbers. This example is small enough that $a=$ 3049 x 5683 and $n=$ 7109 x 6857. With this information, the Jacobi symbol can be set up as follows:

\displaystyle \begin{aligned} \biggl(\frac{17327467}{48746413}\biggr) &=\biggl(\frac{17327467}{7109}\biggr) \biggl(\frac{17327467}{6857}\biggr)=(-1) (-1)=1 \end{aligned}

By knowing the factoring of $n$, the original Jacobi symbol is a product of two Legendre symbols. It can be shown that both of these Legendre symbols are -1. These two Legendre symbols corresponds to these two equations: $x^2 \equiv a \ (\text{mod} \ 7109)$ and $x^2 \equiv a \ (\text{mod} \ 6857)$. The Legendre values of -1 indicate that these two equations have no solutions. By the Chinese remainder theorem, the equation $x^2 \equiv a \ (\text{mod} \ 7109 \times 6857)$ has no solutions. Hence $a=$ 17327467 is a quadratic nonresidue modulo $n=$ 48746413=7109 x 6857. $\square$

____________________________________________________________________________

One versatile feature of the Jacobi symbol is that it can be used in evaluating the Legendre symbol, as shown in Example 1 and Example 2. The original Legendre symbol in Example 1 have arguments that are both odd prime and thus can be flipped right away. However, there are numbers in the interim steps that are odd and not prime. With the use of the Jacobi symbol, these interim numbers do have to be factored. The original Legendre symbol in Example 2 has a top argument that is odd and not prime. Treating it as a Jacobi symbol, it can be flipped right away. When numbers involved in Legendre symbol evaluation are large such that the factoring is not obtainable, the Jacobi symbol can be flipped and reduced and flipped again to obtain the answer of the Legendre symbol. The Jacobi symbol plays an outsize role in the evaluation of the Legendre symbol and thus is a pivotal tool in determining whether a number is a quadratic residue modulo an odd prime $p$ or the solvability of the equation $x^2 \equiv a \ (\text{mod} \ p)$.

Example 3 shows that when the Jacobi symbol produces the value of -1, the top argument $a$ is a quadratic nonresidue modulo the lower argument $n$. Example 4 shows that when the Jacobi symbol produces the value of 1, the picture is murky. In such a case, settling the question of whether the top argument $a$ is a quadratic nonresidue modulo the lower argument $n$ requires additional information. Example 4 shows that if we can factor the lower argument $n$, then evaluating the individual Legendre symbols (based on the prime factors) will help answer the original question. This points to the possibility that solving the equation $x^2 \equiv a \ (\text{mod} \ n)$ is not feasible when the factorization of a large composite modulus $n$ is not obtainable.

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

# Another look at the fundamental theorem of arithmetic

This is the first post of a series of blog posts on the Chinese remainder theorem, often abbreviated CRT. In this post, we take another look at the fundamental theorem of arithmetic. This post is background for the next post, which will show that CRT can be built step by step from the fundamental theorem of arithmetic.

Links to the other posts in the series:
second post, third post, fourth post.

Every integer can be factored into a product of primes in essentially one way. This fact is called the fundamental theorem of arithmetic. For example, the number 84 is 2 x 2 x 3 x 7. The ordering of the primes is not important here since, for example, 2 x 2 x 3 x 7 is the same as 3 x 2 x 7 x 2. The example of 84 seems to suggest that the fundamental theorem of arithmetic is simply an exercise at the elementary school. In general, factoring a number is a very hard problem. For integers with hundreds or thousands of digits, finding the factors may take more seconds than the number of atoms in the universe! The fundamental theorem of arithmetic guarantees that such factorization exists for any integer, large or small. Because of this, the prime numbers are the building blocks of the integers (the atoms of arithmetic).

What is the importance of knowing that every integer can be factored into prime numbers in a unique way? A short answer is that the fundamental theorem of arithmetic is a foundation result. A vast array of mathematical structures are built on this foundation. The fundamental theorem of arithmetic is the beginning point of many mathematical stories. In this and subsequent posts, we highlight one such example. We show that the Chinese remainder theorem follows from the fundamental theorem of arithmetic. CRT combines beauty and utility. Even though CRT has been known for at least 1,000 years, it continues to present new applications in many areas, e.g. in coding theory, cryptography and the theory of computing. Surprisingly, the proof of CRT is quite simple. CRT follows from a lemma that is equivalent to the fundamental theorem of arithmetic. As a result, the discussion in this and the subsequent posts is a clear demonstration of the power of the fundamental theorem of arithmetic.

In this post, we discuss the fundamental theorem of arithmetic. In the next posts, we discuss CRT.

____________________________________________________________________________

The lemma

The starting point is the following lemma.

Lemma A
Let $a$, $b$ and $d>0$ be integers. Suppose that $\text{GCD}(a,d)=1$, i.e. the greatest common divisor of $a$ and $d$ is 1. If $d \lvert (a \cdot b)$, then $d \lvert b$.

Proof
Suppose that $\text{GCD}(a,d)=1$. By the extended Euclidean algorithm, the linear diophantine equation $ax+dy=1$ is solvable in integers. Let $x$ and $y$ be integers that satisfy this equation. Multiply this equation by $b$ to obtain $abx+dby=b$. Since $d \lvert (a \cdot b)$, $d$ divides both terms on the left hand side of the last equation. Thus $d \lvert b$. $\square$

Lemma A is a simple statement. The proof is also simple, simply using the extended Euclidean algorithm, which is the Euclidean algorithm working backward. the Euclidean alogorithm consists, at heart, of a series of divisions to derive the greatest common divisor. As discussed below, the simple Lemma A leads to the fundamental theorem of arithmetic and Lemma A can also be derived from the fundamental theorem of arithmetic.

____________________________________________________________________________

The fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that any positive integer greater than 1 can be expressed as a product of primes and that the factorization is unique. The theorem is proved in this previous post. Here, we show that it is equivalent to Lemma A.

Theorem B
The following conditions are equivalent:

1. The statement of Lemma A.
2. (Euclid’s lemma) If $p$ is a prime number and $p \lvert (a \cdot b)$, then either $p \lvert a$ or $p \lvert b$.
3. (Fundamental Theorem of Arithmetic) Every positive integer $n>1$ can be written as a product of prime numbers and that this product (called a factorization) is unique.

Condition 2 is usually referred to as the Euclid’s lemma. Condition 3 is, of course, a statement of the fundamental theorem of arithmetic. The story we would like to tell is that Lemma A is equivalent to the fundamental theorem of arithmetic. Thus any consequence of Lemma A is also a consequence of the fundamental theorem of arithmetic.

The proof of $1 \rightarrow 2 \rightarrow 3$ is done in this previous post. We also like to point out one additional argument is needed to establish the equivalence of the three conditions. The proof to establish the fundamental theorem of arithmetic in the previous post uses an induction argument to show that every integer is a product of prime numbers. So condition 2 plus the induction argument establish condition 3. The role of condition 2 is to establish the uniqueness of the product of primes. We only need to show $3 \rightarrow 1$.

Proof
$3 \rightarrow 1$
Suppose that $a$ and $d$ have no prime factors in common and that $d \lvert (a \cdot b)$. So we have $a \cdot b=d \cdot m$ for some integer $m$. By condition 3, we can express $a$ and $d$ as a product of primes as follows:

$\displaystyle p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_t^{\alpha_t} \times b=q_1^{\delta_1} \cdot q_2^{\delta_2} \cdots q_r^{\delta_r} \times m$

The numbers $p_i$ are the prime factors of $a$ and the numbers $q_i$ are the prime factors of $d$. The exponents $\alpha_i$ and $\delta_j$ are positive integers. Note that $p_i \ne q_j$ for any $i$ and $j$. Each $q_i^{\delta_i}$ must appear in the prime factorization of the left-hand side. Since $q_i^{\delta_i}$ cannot appear in the factorization of $a$, it must be in the factorization of $b$. $\square$

The loop $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ shows the equivalence of the three statements. From a logical standpoint, any one of these statements is the fundamental theorem of arithmetic. As a demonstration of the power of the fundamental theorem of arithmetic, the next post shows that the Chinese remainder theorem is derived using Lemma A.

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

# Counting Fermat witnesses

For the Fermat primality test, looking for a Fermat witness is the name of the game. Given an integer $n$ for which the “prime or composite” status is not known, if you can find a Fermat witness for $n$, you can conclude decisively that $n$ is not a prime number. If $n$ is a composite number in reality (but the status is not known to you), how likely is it to find a Fermat witness? In other words, when you use the Fermat primality test on a composite integer, what is the probability of the test giving the correct answer? Or what is the probability of making a mistake? In this post we answer these questions by having a detailed look at Fermat witnesses. This is done through a theorem (see Theorem 1 below) and by counting the numbers of Fermat witnesses of a series of composite integers.

____________________________________________________________________________

Fermat witness

What is a Fermat witness? A Fermat witness is a number that violates the conclusion of Fermat’s little theorem. Here’s the theorem:

Fermat’s little theorem
If $n$ is a prime number and if $a$ is an integer that is relatively prime to $n$, then $a^{n-1} \equiv 1 \ (\text{mod} \ n)$.

If we can find a number $a$ that is relatively prime to $n$ such that $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$, then we know for sure that $n$ is composite. Such a number $a$ is said to be a Fermat witness for the compositeness of $n$. For convenience, we say that a potential Fermat witness for the compositeness of $n$ is any integer $a$ in the interval $1 that is relatively prime to $n$.

To use the Fermat primality test on the integer $n$, we examine a random sample of potential Fermat witnesses for $n$. If one of the potential Fermat witnesses in the sample turns out to be a Fermat witness for $n$, we know with certainty that $n$ is composite. If none of the potential Fermat witnesses in the random sample is a Fermat witness, then $n$ is a likely a prime number.

As with most diagnostic tests, a test can make two types of mistakes – false positives or false negatives. For primality testing, we define a positive result as the outcome that says the number being tested is a prime number and a negative result as the outcome that says the number being tested is a composite number. Thus a false positive is identifying a composite number as a prime number and a false negative is identifying a prime number as a composite number. For the Fermat test, there is no false negative (see Case 1 in the next section). If the Fermat test gives a negative result, it would be a true negative.

On the other hand, the Fermat test can give a false positive. There are two cases for false positives. In one case (Case 2a), the probability of a false positive can be made as low as possible. For the other case (Case 2b), the probability of a false positive is virtually 100%.

____________________________________________________________________________

Looking at different cases

If $n$ is a prime number in reality (but the status is not known before the testing), the Fermat test will always give the correct result. The Fermat test will never make the mistake of declaring a prime number as composite. What if is $n$ is a composite number in reality? How would the test behave? It turns out that if $n$ is a composite number that has a Fermat witness, the test is an effective probabilistic primality test. On the other hand, if $n$ is a composite number that has no Fermat witness, the test will identify $n$ as a prime number (so the test fails completely). Here’s the cases we just describe:

• Case 1. $n$ is a prime number.
• Case 2. $n$ is a composite number.
• Case 2a. $n$ is a composite number that has a Fermat witness.
• Case 2b. $n$ is a composite number that has no Fermat witness.

Let’s look at the cases in more details. If $n$ is a prime number in reality, then it satisfies Fermat’s little theorem. The congruence $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ is always true. So the Fermat test will always give the correct result when the number being tested is a prime number in reality. In Case 1, it will never identify a prime number as a composite number. As mentioned above, the probability of a false negative is zero.

If $n$ is a composite number that has at least one Fermat witness, there is a chance that the Fermat test can identify $n$ as a prime (i.e. a false positive). However, the probability of making a mistake can be reducdd by increasing the number of potential witnesses to be calculated. Indeed, if we sample $k$ potential witnesses, there is at most a $2^{-k}$ chance of getting a wrong result. In Case 2a, the probability of error can be made so small that it is practically zero for all practical purposes. In this case, the Fermat test can work truly as a probabilistic primality test. In this case, the probability of a false positive can be made as small as possible.

The last case (Case 2b) is the weakest link in the Fermat test. Any composite number $n$ such that $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ for all $a$ relatively prime to $n$ is said to be a Carmichael number. When the Fermat test is applied on such a number, it will never give the correct conclusion (i.e. it will always give a false positive). It does not matter how many potential Fermat witnesses that are calculated. In fact, calculating $a^{n-1} \ (\text{mod} \ n)$ for a large number of values of $a$ can lead one to believe that this number $n$ is a prime number. In this case, the probability of a false positive is virtually 100%. So the case of Carmichael numbers cannot be totally ignored. There are infinitely many Carmichael numbers (proved in 1994). Fortunately, it is harder and harder to find Carmichael numbers as you move up in the number line. For an illustration that Carmichael numbers are rare, see a discussion in this previous post.

We will see below that for the composite numbers in Case 2a, the Fermat test has a very small probability of a false positive (identifying a composite number as a prime number). On the other hand, for the composite numbers in Case 2b, the Fermat test has a 100% probability of a false positive. Of course, when you test a number for primality, you do not know in advance what case it is. Thus the presence of Carmichael numbers is a concern.

____________________________________________________________________________

A floor for the count of Fermat witnesses

Theorem 1 below sets a floor for Fermat witnesses. Once again, in this theorem we only care about the composite numbers that have at least one Fermat witness. Recall that a potential Fermat witness for the compositeness of $n$ is an integer $a$ in the interval $1 such that $a$ and $n$ are relatively prime, i.e., $\text{GCD}(a,n) = 1$.

Theorem 1
Let $n$ be a composite integer that has at least one Fermat witness. Then at least half of the potential witnesses for the compositeness of $n$ are Fermat witnesses.

Proof of Theorem 1
Let $a$ be a Fermat witness for $n$. We claim that if $b$ is a potential Fermat witness that is not a Fermat witness, then $a \cdot b$ is a Fermat witness for $n$. First of all, $a \cdot b$ is relatively prime to $n$. Note that the product if two numbers, each of which is relatively prime to $n$, is once again a number that is relatively prime to $n$ (see Lemma 4 in this previous post). Thus $a \cdot b$ is a potential Fermat witness for $n$. The following shows that $a \cdot b$ is a Fermat witness for $n$.

$(a \cdot b)^{n-1}=a^{n-1} \cdot b^{n-1} \equiv a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$

In the above derivation, we use the fact that $a$ is a Fermat witness for $n$ and that $b$ is not a Fermat witness for $n$, which means that $b^{n-1} \equiv 1 \ (\text{mod} \ n)$.

If all the potential Fermat witnesses are Fermat witnesses, then we are done since the conclusion of the theorem is true. Assume that at least one potential Fermat witness is not a Fermat witness. In fact, the following enumerates all potential Fermat witnesses that are not Fermat witnesses:

$b_1,\ b_2,\ \cdots, \ b_k$

where $k \ge 1$ and $b_i \not \equiv b_j \ (\text{mod} \ n)$ for all $i \ne j$. By the claim established earlier, the following numbers are all Fermat witnesses for $n$.

$a \cdot b_1, \ a \cdot b_2, \ \cdots, \ a \cdot b_k$

The above Fermat witnesses are all distinct. If $ab_i \equiv ab_j \ (\text{mod} \ n)$ where $i \ne j$, then we can multiply both sides by $a^{-1}$ and obtain $b_i \equiv b_j \ (\text{mod} \ n)$, which is not possible. What we have proved is that if there exists one Fermat witness for $n$ and if there are $k$ many distinct potential Fermat witnesses that are not Fermat witnesses, then there are at least $k$ many Fermat witnesses for $n$. This means that at most half of the potential witnesses are non-Fermat witnesses (if there are more than half, we get a contradiction). Thus at least half of the potential Fermat witnesses are Fermat witnesses. $\blacksquare$

There is another way to state Theorem 1. Recall that Euler’s phi function $\phi(n)$ is defined to be the number of integers $a$ in the interval $1 that are relatively prime to $n$. In other words, $\phi(n)$ is the count of the potential Fermat witnesses for $n$. With this in mind, Theorem 1 can be restated as the following:

Corollary 2
Let $n$ be a composite integer that has at least one Fermat witness. Then the number of Fermat witnesses for the compositeness of $n$ is at least $\displaystyle \frac{\phi(n)}{2}$.

____________________________________________________________________________

The significance of Theorem 1

Theorem 1 gives a floor on Fermat witnesses for one type of composite numbers, namely the composite numbers that have at least one Fermat witness (put another way, the composite numbers that are not Carmichael numbers). More importantly, Theorem 1 allows us to estimate the probability of error when using the Fermat test on such composite numbers.

When applying the Fermat test on a composite integer $n$ that has at least one Fermat witness, the only scenario in which the Fermat test can make an error (aside from calculation errors of course) is that all the random selections of $a$ are not Fermat witnesses. So you are so unlucky that you happen to pick all values of $a$ that are not Fermat witnesses. What is the probability of that?

Randomly select a potential Fermat witness for $n$, there is at least 50% chance that it is a Fermat witness and at most 50% chance that it is not a Fermat witness. We have the following statement:

If $n$ is a composite number that has at least one Fermat witness, and if you sample one potential Fermat witness for $n$, there is at most a 50% chance that it is not a Fermat witness.

If you pick two values of $a$ at random, there is at most $0.5^2=0.25=25 \%$ chance that both are not Fermat witnesses. If you pick three values of $a$ at random, there is at most $0.5^3=0.125=12.5 \%$ chance that you pick non-Fermat witnesses three times in a row. If you pick 10 potential witnesses at random, there is at most

$0.5^{10}=0.000977=0.0977 \%$

chance that all ten values of $a$ are not Fermat witnesses. In general, we can make the following statement:

If $n$ is a composite number that has at least one Fermat witness, then when sampling $k$ many potential Fermat witnesses for $n$, the probability that none of the $k$ potential witnesses is Fermat witness is $0.5^k$.

Recall that the only scenario in which the Fermat test can make a mistake when testing a composite number belonging to Case 2a is that the random sample of values of $a$ contains only non-Fermat witnesses. Thus when the sample size is large, the probability of error can be made very small.

The bottom line is that the more potential witnesses you sample, the less likely that you won’t pick a Fermat witness (i.e., it is more likely that you will pick one). Picking a Fermat witness is essentially a coin toss. If you toss a fair coin many times, it is not likely to get all tails (it is likely to get at least one head).

The calculation for each potential witness $a$ is $a^{n-1} \ (\text{mod} \ n)$. Exponentiation in modular arithmetic can be done using the fast powering algorithm, which is an efficient algorithm that involves repeated squarings and multiplications. Thus if the composite number $n$ happens to be a composite number with a Fermat witness, the Fermat test is very efficient (when used with the fast powering algorithm) and accurate.

Of course, when you test the primality of a number, you do not know which case it belongs to. If you want to avoid the case of Carmichael numbers entirely, you might want to try a primality test that can detect Carmichael numbers (e.g. the Miller-Rabin test).

____________________________________________________________________________

Counting examples

To reinforce the discussion in the previous sections, we count the Fermat witnesses for 10 integers. They are all small numbers (the largest one is a little over 200,000). These integers are composite integers that are not Carmichael numbers. So each has at least one Fermat witness. To count the witnesses, we create a computer program to determine the witness status for all $a$ in $1 that are relatively prime to $n$. The counts are shown in the following matrix.

Composite integers that are not Carmichael numbers

$\left[\begin{array}{rrrrrrrrr} \text{ } & \text{ } & \text{ } & \text{ } & \text{Fermat Witness} & \text{ } & \text{Fermat Witness} & \text{ } & \text{Fermat Witness} \\ n & \text{ } & \phi(n) & \text{ } & \text{Yes} & \text{ } & \text{No} & \text{ } & \text{Yes} \ \% \\ \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ 91 & \text{ } & 72 & \text{ } & 36 & \text{ } & 36 & \text{ } & 50 \% \\ 221 & \text{ } & 192 & \text{ } & 176 & \text{ } & 16 & \text{ } & 91.67 \% \\ 341 & \text{ } & 300 & \text{ } & 200 & \text{ } & 100 & \text{ } & 66.67 \% \\ 5,777 & \text{ } & 5,616 & \text{ } & 5,600 & \text{ } & 16 & \text{ } & 99.72 \% \\ 10,873 & \text{ } & 10,660 & \text{ } & 10,656 & \text{ } & 4 & \text{ } & 99.96 \% \\ 21,809 & \text{ } & 21,504 & \text{ } & 21,248 & \text{ } & 256 & \text{ } & 98.81 \% \\ 50,113 & \text{ } & 42,948 & \text{ } & 42,912 & \text{ } & 36& \text{ } & 99.92 \% \\ 73,861 & \text{ } & 73,312 & \text{ } & 73,296 & \text{ } & 16 & \text{ } & 99.98 \% \\ 100,097 & \text{ } & 99,396 & \text{ } & 99,392 & \text{ } & 4 & \text{ } & 100 \% \\ 201,217 & \text{ } & 200,260 & \text{ } & 200,256 & \text{ } & 4 & \text{ } & 100 \% \end{array}\right]$

The first column is the 10 integers from 91 to 201,217. The second column is Euler’s phi function, which is the count of all integers $a$ that are relatively prime to $n$, which is the count of the potential Fermat witnesses for $n$. For $n=91$, there are 72 potential Fermat witnesses where exactly half are Fermat witnesses. For the other numbers on the list, the percentages of Fermat witnesses are a lot more than 50%. In fact, for most of them, the Fermat witness percentages are over 99%. For the last two numbers on the list the percentage is virtually 100%.

Consider 201,217, the last number on the list. Applying the Fermat test on the number, it will be hard not to pick up a Fermat witness. With only 4 potential witnesses that are not Fermat witness, it is certain to find one Fermat witness when more than 4 numbers are sampled. In fact, even if just 4 numbers are sampled, there is a virtually 100% chance that a Fermat witness will be found.

Take the number in the above table that has the largest number of non-Fermat witnesses ($n=21,809$), which has 256 non-Fermat witnesses. It has 21,504 potential witnesses. Out of a random sample of 20 such potential Fermat witnesses, the probability that none of them is a Fermat witness is $3.24 \cdot 10^{-39}$, which is practically zero.

The above calculations show that for composite numbers that have at least one Fermat witness, the Fermat test is very accurate with a very high probability. The key is to sample a large enough number of potential witnesses. However for Carmichael numbers, it is totally different story.

As discussed earlier, a Carmichael number is a composite number $n$ that has no Fermat witnesses. Specifically a composite number $n$ is a Carmichael number if $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ for all integers $a$ such that $1 and $a$ and $n$ are relatively prime. The following table is a demonstration of this property.

The first ten Carmichael numbers

$\left[\begin{array}{rrrrrrrrr} \text{ } & \text{ } & \text{ } & \text{ } & \text{Fermat Witness} & \text{ } & \text{Fermat Witness} & \text{ } & \text{Fermat Witness} \\ n & \text{ } & \phi(n) & \text{ } & \text{Yes} & \text{ } & \text{No} & \text{ } & \text{Yes} \ \% \\ \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ 561 & \text{ } & 320 & \text{ } & 0 & \text{ } & 320 & \text{ } & 0 \% \\ 1,105 & \text{ } & 768 & \text{ } & 0 & \text{ } & 768 & \text{ } & 0 \% \\ 1,729 & \text{ } & 1,296 & \text{ } & 0 & \text{ } & 1,296 & \text{ } & 0 \% \\ 2,465 & \text{ } & 1,792 & \text{ } & 0 & \text{ } & 1,792 & \text{ } & 0 \% \\ 2,821 & \text{ } & 2,160 & \text{ } & 0 & \text{ } & 2,160 & \text{ } & 0 \% \\ 6,601 & \text{ } & 5,280 & \text{ } & 0 & \text{ } & 5,280 & \text{ } & 0 \% \\ 8,911 & \text{ } & 7,128 & \text{ } & 0 & \text{ } & 7,128& \text{ } & 0 \% \\ 10,585 & \text{ } & 8,064 & \text{ } & 0 & \text{ } & 8,064 & \text{ } & 0 \% \\ 15,841 & \text{ } & 12,960 & \text{ } & 0 & \text{ } & 12,960 & \text{ } & 0 \% \\ 29,341 & \text{ } & 25,920 & \text{ } & 0 & \text{ } & 25,920 & \text{ } & 0 \% \end{array}\right]$

The above table lists out the first ten Carmichael numbers. Though we can show that each one of them is a Carmichael number by using the Korselt’s Criterion (see here but you have to first factor the numbers). We calculate the Fermat witness status for each potential witness for each $n$ in the table. The above table is a visual demonstration of the fact that the column for the Fermat witnesses is entirely zero! So if you happen to test the primality on such numbers using the Fermat test, you will conclude that they are prime numbers unless you happen to sample a value of $a$ whose GCD with $n$ is greater than one (i.e., the only way you can determine the compositeness of a Carmichael number is to stumble into a GCD witness).

Fermat test does what it does well with the exception of Carmichael numbers. As mentioned earlier, if you want to avoid the trap of working with Carmichael numbers (as rare as they are), you can always switch to a test that will always detect Carmichael numbers (e.g. Miller-Rabin test).

____________________________________________________________________________

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

# Factorization versus primality testing

Let $n$ be a large positive integer whose “prime versus composite” status is not known. One way to know whether $n$ is prime or composite is to factor $n$ into its prime factors. If there is a non-trivial factor (one that is neither 1 nor $n$), it is composite. Otherwise $n$ is prime. This may sound like a reasonable approach in performing primality testing – checking whether a number is prime or composite. In reality, factoring and primality testing, though related, are very different problems. For a very large number (e.g. with at least 300 decimal digits), it is possible that, even with the state of the art in computing, factoring it may take more than a few million years. On the other hand, it will take a modern computer less than a second to determine whether a 300-digit number is prime or composite. Interestingly this disparity is one reason that makes the RSA work as a practical and secure cryptosystem. In this post, we use the RSA cryptosystem as an example to give a sense that factoring is a “hard” problem while primality testing is an “easy” problem. The primality test used in the examples is the Fermat primality test.

____________________________________________________________________________

The brute force approach

There is a natural and simple approach in factoring, which is to do trial divisions. To factor the number $n$, we divide $n$ by every integer $a$ in the range $1. Once a factor $a$ is found, we repeat the process with the complementary factor $\frac{n}{a}$ until all the prime factors of $n$ are found. This is simple in concept and is sure to produce the correct answer. For applications in cryptography, this brute force approach is essentially useless since the amount of time to try every candidate factor is prohibitively huge. The amount of time required may be more than the age of the universe if the brute force approach is used.

The brute force approach can be improved upon slightly by doing the trial divisions using candidate factors up to $\sqrt{n}$. It is well known that if a composite integer $n$ is greater than one, then it has a prime divisor $d$ such that $1. So instead of dividing $n$ by every number $a$ with $1, we can divide $n$ by every prime number $a$ with $1. But even this improved brute force approach will still take too long to be practical.

Let’s look at a quick example for brute force factoring. Let $n=96638243$. Note that $\sqrt{n}=\sqrt{96638243}=9676$. There are 1192 odd primes less than 9676. In dividing $n$ by these primes, we stop at 127 and we have $n=96638243=127 \cdot 737309$. We now focus the attention on $737309$. Note that $\sqrt{737309}=858.67$ and there are 147 odd primes less than 858. Dividing $737309$ by these 147 candidate factors, we find that none of them is a factor. We can conclude $737309$ is prime. Then we have the factorization $n=96638243=127 \cdot 737309$.

____________________________________________________________________________

Example of RSA

RSA is a public-key cryptosystem and is widely used for secure data transmission. The RSA public key consists of two parts. One is the modulus that is the product of two distinct prime factors. Suppose the modulus is called $N$ and we have $N=pq$ where $p$ and $q$ are distinct prime numbers. How large does $N$ have to be? The larger the $N$ is, the more secure RSA is. The current practice is that for corporate use the modulus is at least a 1024-bit number (the bit size is called the key length). If data is extra sensitive or if the data needs to be retained for a long time, then a larger key length should be used (e.g. 2048-bit). With a 1024-bit modulus $N=pq$, each prime factor is a 512-bit number. The other part of the RSA public key is the encryption key, which is an integer $e$ that is relatively prime to the integer $(p-1) \cdot (q-1)$.

Let’s say we want to generate a 1024-bit modulus. There are two challenges with a key of this size. One is that a reliable way is needed to obtain two prime numbers that are 512-bit long. Given a large integer that is at least 512-bit long, how do we determine reliably that it is prime? Is it possible to factor a 512-bit integer using the brute force approach? The other challenge is from the perspective of an attacker – successful factoring the 1024-bit modulus would break RSA and allow the attacker to read the secret message. Let’s look at the problem of the attacker trying to factor a 1024-bit number. A 1024-bit number is approximately $2^{1024}$. The following calculation converts it to a decimal basis:

$\displaystyle 2^{1024}=(10^{\text{log(2)}})^{1024} \approx 10^{308.25}$

We use $\text{log}(x)$ to denote the logarithm of base 10. Note that $1024 \cdot \text{log}(2)=308.25$. So a 1024-bit number has over 300 digits.

Let’s see what the challenge is if you want to factor a 1024-bit number. Suppose your chosen large number $n$ is such that $n \approx 10^{308}$. Note that $\sqrt{10^{308}}=10^{154}$. According to the improved brute force approach described above, in effect you will need to divide $n$ by every prime number less than $10^{154}$.

Now let’s get an estimate on the number of prime numbers less than $10^{154}$. According to the prime number theorem, the number of prime numbers at most $x$ is approximately

$\displaystyle \pi(x) \approx \frac{x}{\text{ln}x}$

where $\pi(x)$ is the number of primes at most $x$. Then $\pi(10^{154}) \approx 2.82 \cdot 10^{151}$. This is certainly a lot of prime numbers to check.

It is hard to comprehend such large numbers. Let’s put this into perspective. Currently the world population is about 7 billion. Let’s say each person in the world possesses a supercomputer that can check $10^{40}$ prime numbers per second (i.e. to check whether they are factors of the number $n$). This scenario clearly far exceeds the computing resources that are currently available. Suppose that the 7 billion supercomputers are available and that each one can check $10^{40}$ many primes per second. Then in each second, the following is the number of prime numbers that can be checked by the 7 billion supercomputers.

$\displaystyle 7 \cdot 10^9 \cdot 10^{40}=7 \cdot 10^{49} \text{ prime numbers per second}$

The following is the number of seconds it will take to check $2.82 \cdot 10^{151}$ many prime numbers:

$\displaystyle \frac{2.82 \cdot 10^{151}}{7 \cdot 10^{49}} \approx 4 \cdot 10^{101} \text{ seconds}$

The universe is estimated to be about 13 billion years old. The following calculation converts it to seconds.

$13 \text{ billion years}=13 \cdot 10^9 \cdot 365 \cdot 24 \cdot 3600 \approx 4 \cdot 10^{17} \text{ seconds}$

With 7 billion fast suppercomputers (one for each person in the world) running in the entire life of the universe, you can only finish checking

$\displaystyle \frac{4 \cdot 10^{17}}{4 \cdot 10^{101}}=\frac{1}{10^{84}}$

of the $2.82 \cdot 10^{151}$ many prime numbers. Note that $\frac{1}{10^{84}}$ is a tiny portion of 1%. So by taking the entire life of the universe to run the 7 billion supercomputers, each checking $10^{40}$ many candidate prime factors per second, you would not even make a dent in the problem!

The security of RSA rests on the apparent difficulty of factoring large numbers. If the modulus $N=pq$ can be factored, then an eavesdropper can obtain the private key from the public key and be able to read the message. The difficulty in factoring means there is a good chance that RSA is secure. In order to break RSA, an attacker would probably have to explore other possible vulnerabilities instead of factoring the modulus.

By carrying out a similar calculation, we can also see that factoring a 512-bit number by brute force factoring is also not feasible. Thus in the RSA key generation process, it is not feasible to use factoring as a way to test primality. The alternative is to use efficient primality tests such as Fermat test or Miller-Rabin test. The computation for these tests is based on the fast powering algorithm, which is a very efficient algorithm.

____________________________________________________________________________

The story told by RSA numbers

The required time of more than the life of the universe as discussed above is based on the naïve brute force approach of factoring. There are many other factoring approaches that are much more efficient and much faster, e.g., the quadratic sieve algorithm, the number field sieve algorithm, and the general number field sieve algorithm. For these methods, with ample computing resources at the ready, factoring a 1024-bit or 2048-bit number may not take the entire life of the universe but make take decades or more. Even with these better methods, the disparity between slow factoring and fast primality testing is still very pronounced and dramatic.

The best evidence of slow factoring even with using modern methods is from the RSA numbers. The RSA numbers are part of the the RSA Factoring Challenge, which was created in 1991 to foster research in computational number theory and the practical difficulty of factoring large integers. The challenge was declared inactive in 2007. The effort behind the successful factorization of some of these numbers gives us an idea of the monumental challenges in factoring large numbers.

According to the link given in the above paragraph, there are 54 RSA numbers, ranging from 330 bits long to 2048 bits long (100 decimal digits to 617 decimal digits). Each of these numbers is a product of two prime numbers. Of these 54 numbers, 18 were successfully factored (as of the writing of this post). They were all massive efforts involving large groups of volunteers (in some cases using hundreds or thousands of computers), spanning over months or years. Some of methods used are the quadratic sieve algorithm, the number field sieve algorithm, and the general number field sieve algorithm.

The largest RSA number that was successfully factored is the RSA-768, which is 768 bits long and has 232 decimal digits (completed in December 2009). The method used was the Number Field Sieve method. There were 4 main steps in this effort. The first step is the polynomial selection, which took half a year using 80 processors. The second step is the sieving step, which took almost two years on many hundreds of machines. If only using a single core 2.2 GHz AMD Opteron processor with 2 GB RAM, the second step would take about 1500 years! The third step is the matrix step, which took a couple of weeks on a few processors. The final step took a few days, which involved a great deal of debugging.

The number field sieve method is the fastest known method for factoring large numbers that are a product of two primes (i.e. RSA moduli). The effort that went into factoring RSA-768 was massive and involved many years of complicated calculations and processing. This was only a medium size number on the list!

Another interesting observation that can be made is on the RSA numbers that have not been factored yet. There are 36 unfactored numbers in the list. One indication that RSA is secure in the current environment is that the larger numbers in the list are not yet factored (e.g. RSA-1024 which is 1024-bit long). Successful factorization of these numbers has important security implication for RSA. The largest number on the list is RSA-2048, which is 2048-bit long and has 617 digits. It is widely believed that RSA-2048 will stay unfactored in the decades to come, barring any dramatic and significant advance in computing technology.

The factoring challenge for the RSA numbers certainly provides empirical evidence that factoring is hard. Of course, no one should be complacent. We should not think that factoring will always be hard. Technology will continue to improve. A 768-bit RSA modulus was once considered secure. With the successful factorization of RSA-768, key size of 768 bits is no longer considered secure. Currently 1024 bit key size is considered secure. The RSA number RSA-1024 could very well be broken in within the next decade.

There could be new advances in factoring algorithm too. A problem that is thought to be hard may eventually turn out to be easy. Just because everyone thinks that there is no fast way of factoring, it does not mean that no such method exists. It is possible that someone has discovered such a method but decides to keep it secret in order to maintain the advantage. Beyond the issue of factoring, there could be some other vulnerabilities in RSA that can be explored and exploited by attackers.

____________________________________________________________________________

Fermat primality test

We now give some examples showing primality testing is a much better approach (over factoring) if the goal is to check the “prime or composite” status only. We use Fermat primality test as an example.

Example 1
Let $n=15144781$. This is a small number. So factoring would be practical as a primality test. We use it to illustrate the point that the “prime or composite” status can be determined without factoring. One option is to use Fermat’s little theorem (hence the name of Fermat primality test):

Fermat’s little theorem
If $n$ is a prime number and if $a$ is an integer that is relatively prime to $n$, then $a^{n-1} \equiv 1 \ (\text{mod} \ n)$.

Consider the contrapositive of the theorem. If we can find an $a$, relatively prime to $n$ such that $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$, then we know for sure $n$ is not prime. Such a value of $a$ is said to be a Fermat witness for the compositeness of $n$.

If a Fermat witness is found, then we can say conclusively that $n$ is composite. On the other hand, if $a$ is relatively prime to $n$ and $a^{n-1} \equiv 1 \ (\text{mod} \ n)$, then $n$ is probably a prime. We can then declare $n$ is prime or choose to run the test for a few more random values of $a$.

The exponentiation $a^{n-1} \ (\text{mod} \ n)$ is done using the fast powering algorithm, which involves a series of squarings and multiplications. Even for large moduli, the computer implementation of this algorithm is fast and efficient.

Let’s try some value of $a$, say $a=2$. Using an online calculator, we have

$2^{15144780} \equiv 1789293 \not \equiv 1 \ (\text{mod} \ 15144781)$

In this case, one congruence calculation tells us that $n=15144781$ is not prime (if it were, the congruence calculation would lead to a value of one). It turns out that $n=15144781$ is a product of two primes where $n=15144781=3733 \cdot 4057$. Of course, this is not a secure modulus for RSA. The current consensus is to use a modulus that is at least 1024-bit long.

Example 2
Let $n=15231691$. This is also a small number (in relation what is required for RSA). Once again this is an illustrative example. We calculate $a^{15231690} \ (\text{mod} \ 15231691)$ for $a=2,3,4,5,6,7$, the first few values of $a$. All such congruence values are one. We suspect that $n=15231691$ may be prime. So we randomly choose 20 values of $a$ and compute $a^{15231690} \ (\text{mod} \ 15231691)$. The following shows the results.

$\left[\begin{array}{rrr} a & \text{ } & a^{n-1} \ \text{mod} \ n \\ \text{ } & \text{ } & n=15,231,691 \\ \text{ } & \text{ } & \text{ } \\ 3,747,236 & \text{ } & 1 \\ 370,478 & \text{ } & 1 \\ 12,094,560 & \text{ } & 1 \\ 705,835 & \text{ } & 1 \\ 10,571,714 & \text{ } & 1 \\ 15,004,366 & \text{ } & 1 \\ 12,216,046 & \text{ } & 1 \\ 10,708,300 & \text{ } & 1 \\ 6,243,738 & \text{ } & 1 \\ 1,523,626 & \text{ } & 1 \\ 10,496,554 & \text{ } & 1 \\ 10,332,033 & \text{ } & 1 \\ 10,233,123 & \text{ } & 1 \\ 3,996,691 & \text{ } & 1 \\ 4,221,958 & \text{ } & 1 \\ 3,139,943 & \text{ } & 1 \\ 1,736,767 & \text{ } & 1 \\ 12,672,150 & \text{ } & 1 \\ 12,028,143 & \text{ } & 1 \\ 8,528,642 & \text{ } & 1 \end{array}\right]$

For all 20 random values of $a$, $a^{15231690} \equiv 1 \ (\text{mod} \ 15231691)$. This represents strong evidence (though not absolute proof) that $n=15231691$ is a prime. In fact, we can attach the following probability statement to the above table of 20 random values of $a$.

If $n=15231691$ were a composite number that has at least one Fermat witness, there is at most a 0.0000953674% chance that 20 randomly selected values of $a$ are not Fermat witnesses.

In other words, if $n=15231691$ were a composite number that has at least one Fermat witness, there is at most a 0.0000953674% chance of getting 20 1’s in the above computation.

In general, if $n$ has at least one Fermat witness, the probability that all $k$ randomly selected values of $a$ with $1 are not Fermat witnesses is at most $0.5^k$. For $k=20$, $0.5^{20}=0.000000953674$, which is 0.0000953674%. The probability statement should give us enough confidence to consider $n=15231691$ a prime number.

There is a caveat that has to be mentioned. For the above probability statement to be valid, the number $n$ must have at least one Fermat witness. If a number $n$ is composite, we would like the test to produce a Fermat witness. It turns out that there are composite numbers that have no Fermat witnesses. These numbers are called Carmichael numbers. If $n$ is such a number, $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ for any $a$ that is relatively prime to the number $n$. In other words, the Fermat test will always indicate “probably prime” for Carmichael numbers. Unless you are lucky and randomly pick a value of $a$ that shares a common prime factor with $n$, the Fermat test will always incorrectly identify a Carmichael number $n$ as prime. Fortunately Carmichael numbers are rare, even though there are infinitely many of them. In this previous post, we estimate that a randomly selected 1024-bit odd integer has a less than one in $10^{88}$ chance of being a Carmichael number!

The Fermat test is a powerful test when the number being tested is a prime number or a composite number that has a Fermat witness. For Carmichael numbers, the test is likely to produce a false positive (identifying a composite number as prime). Thus the existence of Carmichael numbers is the biggest weakness of the Fermat test. Fortunately Carmichael numbers are rare. Though they are rare, their existence may still make the Fermat test unsuitable in some situation, e.g., when you test a number provided by your adversary. If you really want to avoid situations like these, you can always switch to the Miller-Rabin test.

____________________________________________________________________________

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

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