# A 22-million digit prime number

The first digits of 2 to 77,232,917 minus 1

The digits in the above picture are the first digits of the newest largest prime number known to humankind. It was discovered on December 26, 2017. The number is equaled to 2 raided to 77,232,917 less 1, making this a Mersenne prime. It has over 22 million digits (23,249,425 to be precise). If we were to write 5 digits per inch, the digits would cover a stretch of highway of over 73 miles in length!

For more on Mersenne primes, see here or Google the Internet.

$\text{ }$

Dan Ma math

Daniel Ma mathematics

Dan Ma prime numbers

$\copyright$ 2018 – Dan Ma

# 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

# Using Fermat’s Little Theorem to Test Primality

Fermat’s little theorem describes a property that is common to all prime numbers. This property can be used as a way to detect the “prime or composite” status of an integer. Primality testing using Fermat’s little theorem is called the Fermat primality test. In this post, we explain how to use this test and to discuss some issues surrounding the Fermat test.

___________________________________________________________________

Describing the test

The Fermat primality test, as mentioned above, is based on Fermat’s little theorem. The following is the statement of 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 the following congruence relationship holds:

$a^{n-1} \equiv 1 (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

The above theorem indicates that all prime numbers possess a certain property. Therefore if a given positive integer does not possess this property, we know for certain that this integer is not prime. Suppose that the primality of an integer $n$ is not known. If we can find an integer $a$ that is relatively prime to $n$ such that $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$, then we have conclusive proof that $n$ is composite. Such a number $a$ is said to be a Fermat witness for (the compositeness of) $n$.

The Fermat test is closedly linked to the notations of probable primes and pseudoprimes. If the congruence relation (1) is true for $n$ and $a$, then $n$ is said to be a probable prime to base $a$. Furthermore, if $n$ happens to be a composite number, then $n$ is said to be a pseudoprime to base $a$. Pseudoprime prime is a composite number that possesses the prime-like property as indicated by (1) for one base $a$.

The Fermat primality test from a compositeness perspective is about looking for Fermat witnesses. If a Fermat witness is found, the number being tested is proved to be composite. On the other hand, the Fermat primality test, from a primality perspective, consists of checking the congruence relation (1) for several bases that are randomly selected. If the number $n$ is found to be a probable prime to all the randomly chosen bases, then $n$ is likely a prime number.

If the number $n$ is in reality a prime number, then the Fermat test will always give the correct result (as a result of Fermat’s little theorem). If the number $n$ is in reality a composite number, the Fermat test can make the mistake of identifying the composite number $n$ as prime (i.e. identifying a pseudoprime as a prime). For most composite numbers this error probability can be made arbitrarily small (by testing a large number of bases $a$). But there are rare composite numbers that evade the Fermat test. Such composite numbers are called Carmichael numbers. No matter how many bases you test on a Carmichael number, the Fermat test will always output Probably Prime. Carmichael numbers may be rare but there are infinitely many of them over the entire number line. More about Carmichael numbers below.

The following describes the steps of the Fermat primality test.

Fermat primality test
The test is to determine whether a large positive integer $n$ is prime or composite. The test will output one of two results: $n$ is Composite or $n$ is Probably Prime.

• Step 1. Choose a random integer $a \in \left\{2,3,\cdots,n-1 \right\}$.
• Step 2. Compute $\text{GCD}(a,n)$. If it is greater than 1, then stop and output $n$ is Composite. Otherwise go to the next step.
• Step 3. Compute $a^{n-1} \ (\text{mod} \ n)$.
• If $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$, then stop and output $n$ is Composite.
• If $a^{n-1} \equiv 1 \ (\text{mod} \ n)$, then $n$ may be a prime number. Do one of the following:
• Return to Step 1 and repeat the process with a new $a$.
• Output $n$ is Probably Prime and stop.

$\text{ }$

The exponentiation in Step 3 can be done by the fast powering algorithm. This involves a series of squarings and multiplications. Even for numbers that have hundreds of digits, the fast powering algorithm is efficient.

One comment about Step 2 in the algorithm. Step 2 could be called the GCD test for primality. If you can find an integer $a$ such that $1 and such that $\text{GCD}(a,n) \ne 1$, then the integer $n$ is certainly composite. Such a number $a$ is called a GCD witness for the compositeness of $n$. So the Fermat test as described above combines the GCD test and the Fermat test. We can use the Euclidean algorithm to find the GCD. If we happen to stumble upon a GCD witness, then we can try another $n$ for a candidate of a prime number. For most composite numbers, it is not likely to stumble upon a GCD witness. Thus when using the Fermat test, it is likely that Step 3 in the algorithm is used.

An example of Fermat primality testing is the post called A primality testing exercise from RSA-100.

____________________________________________________________________________

When using the Fermat test, what is the probability of the test giving the correct result? Or what is the probability of making an error? Because the Fermat test is not a true probabilistic primality test, the answers to these questions are conditional. In one scenario which covers most of the cases, the test works like an efficient probabilistic test. In another scenario which occurs very rarely, the Fermat test fails miserably.

As with most diagnostic tests, the Fermat test can make two types of mistakes – false positives or false negatives. For primality testing discussed in this post, 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. If $n$ is a prime number in reality, the statement of Fermat’s little theorem does not allow the possibility that $n$ be declared a composite number. Thus if the Fermat test gives a negative result, it would be a true negative. In other words, finding a Fermat witness for $n$ is an irrefutable proof that $n$ is composite.

However, there can be false positives for the Fermat test. This is where things can get a little tricky. A composite number $n$ is said to be a Carmichael number if the above congruence relationship (1) holds for all bases $a$ relatively prime to $n$. In other words, $n$ is a Carmichael number if $a^{n-1} \equiv 1 (\text{mod} \ n)$ for all $a$ that are relatively prime to $n$. Saying it in another way, $n$ is a Carmichael number if there exists no Fermat witness for $n$.

The smallest Carmichael number is 561. Carmichael numbers are rare but there are infinitely many of them. The existence of such numbers poses a challenge for the Fermat test. If you apply the Fermat test on a Carmichael number, the outcome will always be Probably Prime. So the Fermat test will always give a false positive when it is applied on a Carmichael number. To put it in another way, with respect to Carmichael numbers, the error probability of the Fermat test is virtually 100%!

So should a primality tester do? To keep things in perspective, Carmichael numbers are rare (see this post). If the primality testing is done on randomly chosen numbers, choosing a Carmichael number is not likely. So the Fermat test will often give the correct results. For those who are bothered by the nagging fear of working with Carmichael numbers, they can always switch to a Carmichael neutral test such as the Miller-Rabin test.

___________________________________________________________________

One bright spot about the Fermat test

There is one bright spot about the Fermat test. When applying the Fermat test on numbers that are not Carmichael numbers, the error probability can be made arbitrarily small. In this sense the Fermat test works like a true probabilistic primality test. Consider the following theorem.

Theorem 1
Let $n$ be a composite integer such that it is not a pseudoprime to at least one base (i.e. $n$ has a Fermat witness). In other words, $n$ is not a Carmichael number. Then $n$ is not a pseudoprime to at least half of the bases $a$ ($1) that are relatively prime to $n$. In other words, $n$ is a pseudoprime to at most half of the bases $a$ ($1) that are relatively prime to $n$.

Theorem 1 means that the Fermat test can be very accurate on composite numbers that are not Carmichael numbers. As long as there is one base to which the composite number is not a pseudoprime (i.e. as long as there is a Fermat witness for the composite number in question), there will be enough of such bases (at least 50% of the possible bases). As a result, it is likely that the Fermat test will find a witness, especially if the tester is willing to use enough bases to test and if the bases are randomly chosen. When a base is randomly chosen, there is at least a 50% chance that the number $n$ is not a pseudoprime to that base (i.e. the Fermat test will detect the compositeness) or putting it in another way, there is at most a 50% chance that the Fermat test will not detect the compositeness of the composite number $n$. So if $k$ values of $a$ are randomly selected, there is at most $0.5^k$ probability that the Fermat test will not detect the compositeness of the composite number $n$ (i.e. making a mistake). So the probability of a false positive is at most $0.5^k$. For a large enough $k$, this probability is practically zero.

Proof of Theorem 1
A base to which $n$ is a pseudoprime or not a pseudoprime should be a number in the interval $1 that is relatively prime to $n$. If $n$ is a pseudoprime to base $a$, then $a$ raised to some power is congruent to 1 modulo $n$. For this to happen, $a$ must be relatively prime to the modulus $n$. For this reason, when we consider a base, it must be a number that is relatively prime to the composite integer $n$ (see the post on Euler’s phi function).

Let $a$ be a base to which $n$ is not a pseudoprime. We make the following claim.

Claim
If $b$ is a number such that $1 and such that $n$ is a pseudoprime to base $b$, then $n$ is not a pseudoprime to base $a \cdot b$.

Since both integers $a$ and $b$ are assumed to be relatively prime to $n$, the product $a \cdot b$ is also relatively prime to $n$ (see Lemma 4 in this post). Now consider the congruence $(ab)^{n-1} \ (\text{mod} \ n)$, which is derived as follows:

$(ab)^{n-1} \equiv 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 $n$ is not a pseudoprime to base $a$ and $n$ is a pseudoprime to base $b$. The above derivation shows that $n$ is not a pseudoprime to base $ab$.

If $n$ is not a pseudoprime to all bases in $1, then we are done. So assume that $n$ is a pseudoprime to at least one base. Let $b_1,b_2,\cdots,b_k$ enumerate all bases to which $n$ is a pseudoprime. We assume that the $b_j$ are all distinct. So $b_i \not \equiv b_j \ (\text{mod} \ n)$ for all $i \ne j$. By the above claim, the composite number $n$ is not a pseudoprime to all the following $k$ numbers:

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

It is also clear that $a \cdot b_i \not \equiv a \cdot b_j \ (\text{mod} \ n)$ for $i \ne j$. What we have just shown is that there are at least as many bases to which $n$ is not a pseudoprime as there are bases to which $n$ is a pseudoprime. This means that $n$ is not a pseudoprime to at least 50% of the bases that are relatively prime to $n$. In other words, as long as there exists one Fermat witness for $n$, at least 50% of the bases are Fermat witnesses for $n$. It then follows that $n$ is a pseudoprime to no more than 50% of the bases relatively prime to $n$. $\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$. With this in mind, Theorem 1 can be restated as the following:

Corollary 2
Let $n$ be a composite integer such that it is not a pseudoprime to at least one base. Then $n$ is not a pseudoprime to at least $\displaystyle \frac{\phi(n)}{2}$ many bases in the interval $1.

___________________________________________________________________

Concluding remarks

Of course, Theorem 1 works only for the composite numbers that are not pseudoprime to at least one base (i.e. they are not Carmichael numbers). When you test the compositeness of a number, you do not know in advance if it is Carmichael or not. On the other hand, if the testing is done on randomly chosen numbers, it is not likely to randomly stumble upon Carmichael numbers. The Fermat test works well for the most part and often give the correct results. If one is concerned about the rare chance of a false positive in the form of a Carmichael number, then the Miller-Rabin test will be a good alternative.

Note:
The original post was written in August 10, 2013. On March 29, 2015, this post is replaced with a blog post called The Fermat primality test from the companion math crypto blog.

___________________________________________________________________
$\copyright \ \ 2013 - 2015 \ \text{Dan Ma}$

# An observation about Mersenne primes

This post concerns an observation about Mersenne primes. The observation will be made after presenting an example.

Mersenne numbers are integers of the form $M_n=2^n-1$ where $n$ is a positive integer. If $M_n$ is a prime number, then $M_n$ is said to be a Mersenne primes. Not all Mersenne numbers are prime. Are there infinitely many Mersenne primes? No one has yet been able to resolve this question. As of the writing of this post, there are only 48 known Mersenne primes, the largest of which is $M_p$ where $p=57885161$, discovered in January 25, 2013. The current largest known Mersenne prime is also the current largest known prime number.

___________________________________________________________________________________________________________________

Example

In this example, $p=57885161$. Since $M_p$ is prime, it is obviously not divisible by any other prime numbers. In particular, $M_p$ is not divisible by any smaller Mersenne primes. We demonstrate this using congruence modulo arithmetic.

We wish to point out that we are not trying to establish the primality of $M_p$ (doing that would take a great amount of super computing resources). This is merely a simple example of working with Mersenne primes and an exercise in doing congruence modulo calculation.

First, show that $M_p=2^p-1$ is not divisible by the Mersenne prime $2^{19}-1=524287$.

If $M_p=2^p-1$ is divisible by $2^{19}-1$, $M_p \equiv 0 \ (\text{mod} \ 2^{19}-1)$. So we need to show $2^p-1 \not \equiv 0 \ (\text{mod} \ 2^{19}-1)$ or $2^p \not \equiv 1 \ (\text{mod} \ 2^{19}-1)$.

Note that $2^{19} \equiv 1 \ (\text{mod} \ 2^{19}-1)$. So it is a matter of subtracting the largest multiple of 19 out of the exponent $p=57885161$. We have $p=57885161=3046587 \cdot 19+8$. We have the following congruence calculation.

$2^{57885161}=(2^{19})^{3046587} \cdot 2^8 \equiv (1)^{3046587} \cdot 2^8=2^8=256 \ (\text{mod} \ 2^{19}-1)$

Since $2^p \equiv 256 \ (\text{mod} \ 2^{19}-1)$ and $256 \ne 1$, $M_p=2^p-1$ is not divisible by $2^{19}-1=524287$.

The number $2^{3217}-1$ is also a Mersenne prime. To show that $M_p=2^p-1$ is not divisible by $2^{3217}-1$, we only need to show $2^p \not \equiv 1 \ (\text{mod} \ 2^{3217}-1)$.

Note that $2^{3217} \equiv 1 \ (\text{mod} \ 2^{3217}-1)$. We have $p=57885161=17993 \cdot 3217 + 1680$. After subtracting multiple of $3217$, we have the remainder $1680$. Thus $2^{57885161}$ congruence modulo $2^{3217}-1$ is reduced to $2^{1680}$ congruence modulo $2^{3217}-1$.

$2^{57885161} \equiv 2^{1680} \ (\text{mod} \ 2^{3217}-1)$

Since $2^{1680}>1$, $2^p \not \equiv 1 \ (\text{mod} \ 2^{3217}-1)$. Thus $M_p=2^p-1$ is not divisible by $2^{3217}-1$.

___________________________________________________________________________________________________________________

An Observation

The above examples lead to the following observation.

If $a$ and $b$ are prime numbers such that $a, then $2^a-1$ is not a divisor of $2^b-1$.

As in the examples, we need to show $2^b \not \equiv 1 \ (\text{mod} \ 2^a-1)$. Note that $2^a \equiv 1 \ (\text{mod} \ 2^a-1)$. According to the division algorithm, we have $b=r + a \cdot k$ where $k$ is some integer and $r$ is the remainder with $0 \le r . The remainder $r$ cannot be zero. If it is, $a$ would divide $b$. But this cannot be since both of them are prime numbers. Since $r \ne 0$, $2^r>1$. We have the following congruence calculation.

$2^b = (2^a)^{k} \cdot 2^r \equiv 2^r \ (\text{mod} \ 2^a-1)$

Since $2^r>1$, $2^b \not \equiv 1 \ (\text{mod} \ 2^a-1)$. Thus $2^b-1$ is not divisible by $2^a-1$.

The above derivation is definitely a much cleaner demonstration than the derivations shown in the above examples.

Another way to state the above statement is that no Mersenne number can be divisible by any smaller Mersenne number.

Note that in the above statement, $2^a-1$ and $2^b-1$ do not need to be primes. Only the exponents $a$ and $b$ need to be primes. There are many Mersenne numbers that are not prime numbers. The smallest is $2^{11}-1=28*89$. Other smaller non-prime Mersenne numbers are $2^{23}-1$ and $2^{29}-1$.

So the above statement says that even when a Mersenne number is composite, it cannot have factors of the form $2^a-1$. It can certainly not have factors in the form of a Mersenne prime. In testing whether $2^b-1$ is a prime, it can be safe to skip any smaller number of the form $2^a-1$. This fact could be useful in testing the primality of a Mersenne number (at least marginally useful).

___________________________________________________________________________________________________________________

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