Pepin’s Primality Test

A Fermat number is of the form F_n=2^{2^{n}}+1 where n is a nonnegative integer. A Fermat prime is a Fermat number that is a prime number. The first five Fermat numbers F_0 to F_4 are known to be prime. Pierre de Fermat (1601-1665) conjectured that all Fermat numbers are prime. In 1732, Euler discovered a counterexample by showing that F_5 is composite with F_5=641 \times 6700417. The challenge for working with Fermat numbers is that the numbers grow very rapidly. However, Fermat numbers have many interesting properties. See here for a more detailed look. In this post, we discuss Pepin’s test, which is a primality test solely for Fermat numbers, as well as a sequence of integers that are associated with Fermat numbers. Out of this sequence of integers comes the notion of elite prime numbers.

The following are two versions of the Pepin’s test. Theorem 1 is proved in this previous post.

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

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

To determine whether a Fermat number F_n is prime, simply raise 3 (or 5) to the exponent of (F_n-1)/2 modulo F_n. If the result is congruent to -1, then F_n is prime. Otherwise it is composite. The exponentiation can be performed using the fast powering algorithm (also called square-and-multiply). The idea is to use the binary expansion of the exponent to convert the exponentiation into a series of squarings and multiplications. For Pepin’s test, the exponent is a power of 2. Thus the binary expansion is a 1 followed by a number of zeros. As a result, in programming the “square-and-multiply”, we only need to program the squarings.

The above two versions of Pepin’s test use 3 and 5 as bases. An interesting and natural question arises. What are all the numbers that can serve as bases for the Pepin’s test? In fact, there are many other bases. What would be the property that unites all the possible bases? The sequence A129802 in OEIS describes all possible bases for use in Pepin’s test. In this post, we give a formulation of Pepin’s test that takes into account all the possible bases in this sequence. We also discuss the prime numbers in the sequence, which are also captured in the sequence A102742 (these are called elite prime numbers).

___________________________________________________________________

The Periodic Nature of Fermat Numbers

Let a be any positive integer with a \ge 3. Consider all Fermat numbers F_n reduced modulo a, i.e. F_n \ (\text{mod} \ a). We call these values the Fermat remainders modulo a. Since there are only a many such values, i.e. 0, 1, 2, \cdots, a-1 and since Fermat numbers can be derived by the recursive formula

    F_{n+1}=(F_n-1)^2+1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (0)

the Fermat remainders are periodic. Let’s look at an example.

Let a=41. The following shows the first several Fermat remainders modulo 41. Each value is computed from the previous value via the recursive relation (0), which is then reduced modulo 41.

    F_0 \equiv 3 \ (\text{mod} \ 41)

    F_1 \equiv 5 \ (\text{mod} \ 41)

    F_2 \equiv 17 \ (\text{mod} \ 41)

    F_3 \equiv 257 \equiv 11 \ (\text{mod} \ 41)

    F_4 \equiv 101 \equiv 19 \ (\text{mod} \ 41)

    F_5 \equiv 325 \equiv 38 \ (\text{mod} \ 41)

    F_6 \equiv 1370 \equiv 17 \ (\text{mod} \ 41)

It is clear the Fermat remainders 17, 11, 19, 38 repeat themselves as n increases. For Fermat remainders modulo 41, the periodicity starts at F_2 and the length of the period is 4 (we call this the Fermat period).

Let’s describe idea behind the example more generally. Because any Fermat remainder must be an element of \left\{0,1,\cdots,a-1 \right\}, there exist at least two Fermat numbers sharing the same remainder, say F_h and F_k with h<k. Assume that h and k are the smallest possible choices. In the modulo 41 example, h would be 2 and k would be 6. As a result, F_h is the starting point of the period and L=k-h is the length of the Fermat period.

Based on the discussion in the above paragraph, for any positive integer a \ge 3, the Fermat remainders modulo a are periodic with the repeating remainders starting at some Fermat number F_h. The length of the Fermat period is the smallest positive integer L satisfying the congruence F_{h+j} \equiv F_{h+j+m \cdot L} \ (\text{mod} \ a) for all j=0,1,\cdots,L-1 and for all positive integer m.

The symbol (\frac{p}{q}) is a Legendre symbol if the bottom number is a prime number, in which case the value of the symbol is 1 or -1. If the bottom number is a composite number, then it is a Jacobi symbol with possible values 0, 1 or -1.

We now wish to evaluate the symbol (\frac{a}{F_n}) where the bottom part is a Fermat number and the top part is a possible base for Pepin’s test. Consider the following derivation.

    \displaystyle \biggl(\frac{a}{F_n}\biggr)=\biggl(\frac{F_n}{a}\biggr)=\biggl(\frac{r}{a}\biggr) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

The first Jacobi symbol can be flipped without changing sign because F_n \equiv 1 \ (\text{mod} \ 4) for all n \ge 1. This is due to the law of quadratic reciprocity of Jacobi symbol (see bullet # 6 in Theorem 6 here). The number r in the top part of the third Jacobi symbol represents all the possible Fermat remainders modulo a. For example, if a=41, r would be 17, 11, 19 or 38. The above relation in Jacobi symbol is how we tie Fermat remainders with the Pepin’s test.

___________________________________________________________________

The Sequences

The following theorem gives the linkage between Fermat remainders and the Pepin’s test.

Theorem 3
Let a be a positive integer where a \ge 3. The following conditions are equivalent.

  1. The Jacobi symbol (\frac{r}{a})=-1 for all Fermat remainders r modulo a.
  2. There is a positive integer h such that the Jacobi symbol (\frac{a}{F_n})=-1 for all n \ge h.

Proof of Theorem 3
Note that if condition 1 is not true, then there is one Fermat remainder r such that the Jacobi symbol (\frac{r}{a})=1. Since the Fermat remainders are periodic, via relation (1) above there are infinitely many F_n with (\frac{a}{F_n})=1. Thus condition 2 is not true. In other words, 2 \rightarrow 1 holds. On the other hand, if condition 2 is not true, then condition 1 is not true. \square

Any positive integer a belongs to the sequence A129802 if and only of one of the conditions in Theorem 1 holds. Note that 2 does not belong to the sequence. To see this, note that F_{n} \equiv 1  \ (\text{mod} \ 2) for all n. So there is only one Fermat remainder modulo 2, namely 1. Since the Legendre symbol (\frac{1}{2})=1, condition 1 in Theorem 1 is not true. Thus all possible members of the sequence A129802 must be 3 or higher. The numbers 3 and 5 both belong to the sequence. Both numbers have only one Fermat remainder, namely 2. Note that F_{n} \equiv 2  \ (\text{mod} \ 3) for all n \ge 1 and F_{n} \equiv 2  \ (\text{mod} \ 5) for all n \ge 2. Also note that the Legendre symbols (\frac{2}{3})=-1 and (\frac{2}{5})=-1.

What if we limit the scope of Theorem 3 to just the prime numbers? The following is the translation of Theorem 3 where p is a prime number (using p to replace a).

Theorem 4a
Let p be a prime number. The following conditions are equivalent.

  1. The Legendre symbol (\frac{r}{p})=-1 for all Fermat remainders r modulo p.
  2. There is a positive integer h such that the Legendre symbol (\frac{F_n}{p})=-1 for all n \ge h.

Condition 2 of Theorem 4a should start with the Jacobi symbol (\frac{a}{F_n}). Since it can be flipped without changing sign, it become the Legendre symbol (\frac{F_n}{a}). Next, the following theorem is obtained by rewriting Theorem 4a using the meaning of the Legendre symbol.

Theorem 4b
Let p be a prime number. The following conditions are equivalent.

  1. For each Fermat remainders r modulo p, r is a quadratic nonresidue modulo p
  2. For each Fermat remainders r modulo p, the congruence r^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p) holds.
  3. There is a positive integer h such that the Fermat number F_n is a quadratic nonresidue modulo p for all n \ge h.

Note that condition 2 in Theorem 4b is due to Euler’s criterion.

Any prime number p that satisfies any one of the conditions in Theorem 4b is said to be an elite prime number. Thus an elite prime can be used as a base for the Pepin’s test and is a member of the sequence A129802. In fact, another sequence A102742 is to capture all the elite prime numbers.

Note that 3 and 5 are elite primes as is the prime number 41. The Fermat remainders modulo 41 are 17, 11, 19 and 38 (as shown above). All of the 4 Fermat remainders are quadratic nonresidue modulo 41. The Legendre symbols have value -1 as shown below:

    \displaystyle \biggl(\frac{17}{41}\biggr)=\biggl(\frac{11}{41}\biggr)=\biggl(\frac{19}{41}\biggr)=\biggl(\frac{38}{41}\biggr)=-1

Before further discussing elite primes, let’s have a more general statement of Pepin’s test.

___________________________________________________________________

Pepin’s Test – General Version

Theorem 5 (Pepin’s Test)
Let a \ge 3 be an integer such that there exists a positive integer h such that the Jacobi symbol (\frac{a}{F_n})=-1 for all n \ge h. In other words, a is a member of the sequence A129802. Then for any n \ge h, the Fermat number F_n is a prime number if and only if a^{(F_n-1) / 2} \equiv -1 \ (\text{mod} \ F_n).

Proof of Theorem 5
Let a \ge 3 be a number that satisfies the requirement in Theorem 5, i.e. it is a member of the sequence A129802. Let n \ge h. Suppose that F_n=2^{2^n}+1 is prime. Then the symbol (\frac{a}{F_n}) is a Legendre symbol. By the Euler’s criterion, we have a^{(F_n-1) / 2} \equiv -1 \ (\text{mod} \ F_n).

Suppose that the congruence a^{(F_n-1) / 2} \equiv -1 \ (\text{mod} \ F_n) holds. Then by Lucas primality test, F_n is prime. For the details, see the proof of Theorem 7 in this previous post. \square

Theorem 5 is a version of Pepin’s test that takes into account of all the possibilities for a base. Any number in the sequence A129802 will work. This version is more interesting from a mathematical standpoint. In practice, to use Pepin’s test, we must first settle on a base. Pick a number from list of A129802 or find some number a that satisfies one condition in Theorem 3. It is also important to determine the least number h for the condition in Theorem 3. The h is the lower bound for the F_n that can be tested by Pepin’s test. Of course, it is handy to use 3 or 5 as a base. Thus the versions such as Theorem 1 and Theorem 2 above are useful in practice. Mathematically Theorem 5 is more interesting. It brings out the concept of the integer sequence A129802 and the notion of elite prime.

___________________________________________________________________

More on the Sequences

There is one natural question about the A129802 (possible bases for Pepin’s test) and the sequence A102742 (possible prime bases for Pepin’s test, the elite primes). Does each sequence contain infinitely many numbers? The answer is not known for the second sequence (the elite primes). It is not known whether there are infinitely many elite primes. However, we can show that the first sequence infinitely many members.

Theorem 6

  • If a is a member of the sequence A129802, then the number 2 \times a is also a member of the sequence.
  • If a is a member of the sequence A129802, then for any integer k \ge 0, the number 2^k \times a is also a member of the sequence.

Proof of Theorem 6
We prove the first bullet point. The second follows from the first. Since a is in the sequence A129802 (i.e. it satisfies Theorem 3), there is a least h such that (\frac{a}{F_n})=-1 for all n \ge h. The following derivation shows that (\frac{2a}{F_n})=-1 for all n \ge h.

    \displaystyle \biggl(\frac{2a}{F_n}\biggr)=\biggl(\frac{2}{F_n}\biggr) \times \biggl(\frac{a}{F_n}\biggr)=\biggl(\frac{F_n}{2}\biggr) \times \biggl(\frac{F_n}{a}\biggr)=\biggl(\frac{1}{2}\biggr) \times -1=-1

In the above derivation, a property of Jacobi symbol is used along with the fact that 1 is a quadratic residue modulo 2 and the fact that (\frac{a}{F_n})=(\frac{F_n}{a})=-1. \square

Since 3 is a base for Pepin’s test, 3, 6, 12, 24, 48, 96, … are also bases for Pepin’s test.

___________________________________________________________________

Elite Primes

From the perspective of Fermat numbers, elite prime numbers are simply prime numbers that can serve as bases for Pepin’s primality test for Fermat numbers. Of course this is not a good working definition. Theorem 5 tells us that any prime number that can work as a base for Pepin’s test satisfies the conditions in Theorem 4b (or 4a). Thus we can define elite primes by Theorem 4b. Any odd positive integer p is an elite prime if it satisfies anyone of the conditions in Theorem 4b. We introduce the notion of elite prime by way of Pepin’s test of primality of Fermat numbers. Of course, it is possible to define the notion by using only the conditions in Theorem 4b.

As of the writing of this post, there are 29 known elite primes. The smallest are 3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041. The largest is 3,580,135,407,617, about 3.58 trillion. According to the prime number theorem, there are approximately 124 billion prime numbers in this range. So elite primes are very sparse in the number line. No one know whether there are infinitely many elite primes.

How does one test whether a prime number is an elite prime? One way is to use Theorem 4b. Identify the Fermat remainders modulo the prime p. Compute the congruence r^{\frac{p-1}{2}} \ (\text{mod} \ p) for each remainder r. If r^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p) for all r, then p is an elite prime. it turns out that if p is indeed elite, the calculation to verify is quite light. If p is not elite, there usually is a Fermat remainder early on that disproves the eliteness. We close with two examples.

Example 1
Verify that the largest known elite prime 3,580,135,407,617 is indeed elite.

Let p = 3,580,135,407,617. Then p-1=2^{16} \times 54,628,531. This means that the period will start at or before F_{16}. The following shows the Fermat remainders.

    F_0 \equiv 3
    F_1 \equiv 5
    F_2 \equiv 17
    F_3 \equiv 257
    F_4 \equiv 65537
    F_5 \equiv 4294967297
    F_6 \equiv 3302442361075
    F_7 \equiv 3290048612191
    F_8 \equiv 2705228890692
    F_9 \equiv 3257180532505
    F_{10} \equiv 517702690191
    F_{11} \equiv 690766084782
    F_{12} \equiv 1306969066177
    F_{13} \equiv 2982034914426
    F_{14} \equiv 3080321286431
    F_{15} \equiv 123155921421
    F_{16} \equiv 3185964351132
    F_{17} \equiv 2462332130355
    F_{18} \equiv 3164234988981
    F_{19} \equiv 395355620647
    F_{20} \equiv 2009257348278
    F_{21} \equiv 2441138263337
    F_{22} \equiv 499814121188
    F_{23} \equiv 123155921421

The Fermat period starts at F_{15}. The length of the period is 8 (the remainders are in bold). Let r_j denote the remainder of F_j. Now raise each remainder to the power of \frac{p-1}{2} modulo p. The following shows the results.

    (r_{15})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)

    (r_{16})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)

    (r_{17})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)

    (r_{18})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)

    (r_{19})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)

    (r_{20})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)

    (r_{21})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)

    (r_{22})^{\frac{p-1}{2}} \equiv 3580135407616 \equiv -1 \ (\text{mod} \ p)

The calculation shows that each Fermat remainder is a quadratic nonresidue modulo 3,580,135,407,617. Thus it is an elite prime. \square.

Example 2
The next prime number beyond the elite prime in Example 1 is p = 3,580,135,407,647. Show that it is not elite.

Note that p-1 = 2 x 1,790,067,703,823. Because the exponent in the power of 2 is 1, the period would begin at F_1 or F_0. For some reason, the length of the Fermat period for a non-elite prime can be very long. The following shows the first 13 or 14 remainders.

    F_0 \equiv 3
    F_1 \equiv 5
    F_2 \equiv 17
    F_3 \equiv 257
    F_4 \equiv 65537
    F_5 \equiv 4294967297
    F_6 \equiv 3302287785295
    F_7 \equiv 2157778759259
    F_8 \equiv 2823039261272
    F_9 \equiv 1745925786363
    F_{10} \equiv 1237739799756
    F_{11} \equiv 2960576514326
    F_{12} \equiv 258269474223
    F_{13} \equiv 2361028595996

Fortunately one of the early remainders disproves the eliteness. The following shows that calculation.

    (r_{0})^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)
    (r_{1})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)
    (r_{2})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)
    (r_{3})^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)
    (r_{4})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)
    (r_{5})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)
    (r_{6})^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)
    (r_{7})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)
    (r_{8})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)
    (r_{9})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)
    (r_{10})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)
    (r_{11})^{\frac{p-1}{2}} \equiv 3580135407646 \equiv -1 \ (\text{mod} \ p)
    (r_{12})^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)
    (r_{13})^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)

Even though the Fermat period may be very long in this case, there are several Fermat remainders early that show r^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p). This shows that the prime in this example cannot be elite. \square

The notion of elite primes is an interesting one. Even though the initial motivation is Pein’s test – a primality test for Fermat numbers, the notion of elite prime is interesting in its own right. There had been a lot of research done, both computationally and mathematically. See the references listed in the two OEIS sequences A129802 and A102742.

___________________________________________________________________
\copyright \ \ 2016 \ \text{Dan Ma} Let

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s