Section 5 - Special Types of Primes

As is suggested by the results in Section 4, there are certain types of number that lend themselves more readily than others to particular primality tests. The first form we consider is 2ⁿ +1. Suppose that n has an odd prime factor p, so that n = kp for some k. Let q = 2^k +1. Then 2^k º -1 (mod q), so 2ⁿ º 2^kp º (2^k)^p º (-1)^p (mod q). Since p is odd, we have 2ⁿ º -1 (mod q), and so 2ⁿ +1 cannot be prime. Hence for 2ⁿ +1 to be prime, we at least require that n has no odd prime factors, that is, n is a power of 2.

Definition. The Fermat Number F_m = 2ⁿ +1, where n = 2^m.

F_m is prime for m = 0, 1, 2, 3 and 4. However, F₅ = 4294967297 is divisible by 641, and there are no other known prime Fermat Numbers.

Lemma 5.1 (Pepin's Test). n = F_m (m>0) is prime if and only if 3^(n-1)/2 º -1 (mod F_m).

Proof : Suppose F_m is prime. Now F_m = 2^2k +1 = 4^k +1 º 5 (mod 12) for some k. By Lemma 4.8, we have (3/F_m) = -1, which is all we need, by Lemma 4.2(iii). In other words, if F_m is prime, 3 is a primitive root of F_m. Conversely, we can invoke Lemma 3.5 with a = 3 and k = 1 to establish that F_m is prime. Hence result.

In Pepin's Test, the number 3 can be replaced by 5 or 10. This test has been used to verify primality or otherwise of all Fermat Numbers with m £ 22 for which an explicit factor had not previously been found. Since each Fermat Number is almost the square of the previous, the actual size of these grows rapidly as m increases, so that applying Pepin's Test for higher values of m is a massive task. It is therefore reasonable to search for factors in advance. This is aided by the following result.

Lemma 5.2. Every factor of F_m (m ³ 2) is of the form k*2^m+2 +1.

Proof : Let F_m = 2ⁿ where n = 2^m, and suppose that F_m has a factor p. Then 2ⁿ º -1 (mod p), and so 2²ⁿ º 1 (mod p). By Fermat's Little Theorem, 2n = 2^m+1 divides p-1, and so 8 divides p-1 (since m+1 ³ 3). By Lemma 4.4, we have (2/p) º 2^(p-1)/2 º 1 (mod p), and so 2^m+1 divides (p-1)/2, so 2^m+2 divides p-1, as required.

This is one of the main reasons why numbers of the form k.2ⁿ + 1 have been studied so intensively. In fact, I dedicate an entire section to these later.

The search for factors of Fermat numbers is very active, and there are several pieces of software available, and several collaborative ventures (e.g. Durman). The normal way to proceed is to check ranges of possible divisors after performing a quick trial division to remove all but a few from consideration. It is not necessary to perform full primality tests on the possible divisors since any composite divisor can always be factored later, and the reduction in overhead is substantial.

Since Fermat factors are found on a regular basis, I refrain from giving any recent examples. However, some of the older ones are as follows :

5*2²⁵ +1 divides F₂₃

3*2⁴¹ +1 divides F₃₈

21*2⁴¹ +1 divides F₃₉

425*2⁷⁹ +1 divides F₇₇

247*2³⁰² +1 divides F₂₉₈

431*2²⁰⁹⁹ +1 divides F₂₀₈₉

57*2²⁵⁰¹⁰ +1 divides F₂₅₀₀₆

3*2³⁸²⁴⁴⁹ +1 divides F₃₈₂₄₄₇

168329*2⁷¹⁸⁷ +1 divides F₇₁₈₁

491628159*2⁶⁶⁹ +1 divides F₆₆₇

Definition : The generalised Fermat Number GF(a,m) = aⁿ +1, where n = 2^m.

As elsewhere, it is natural to generalise ideas in the hope that further observations can be made. Generalised Fermat Numbers (GFN) have the advantage in having the same form of divisors as normal Fermat divisors, however with k.2^m+1 +1 rather than k.2^m+2 +1. In this respect, having tables of primes of the form k.2ⁿ +1 is a distinct benefit, since it avoids the need to reproduce possible divisors. Note that as with Fermat numbers, in order for aⁿ +1 to be prime, n must be a power of 2. The smallest prime GFN with m > 4 is GF(30,5). Yves Gallot coordinates an active search for prime GFNs. Here are some examples:

GF(102,6)

GF(4026,10)

GF(316970,13)

GF(2167350,15)

GF(48594,16)

The next form that we consider is fairly obvious : 2ⁿ -1. Suppose that n is not prime, so that n = pk for some prime p and integer k > 1, and let q = 2^p -1. Then since 2^p º 1 (mod q), we have 2ⁿ º 2^pk º 1 (mod q), so 2ⁿ -1 cannot be prime. Hence n must be prime.

Definition : The Mersenne Number M_p = 2^p -1, where p is a prime.

M_p is easily verified a prime for p = 2, 3, 5, and 7. However 2¹¹ - 1 = 23*89, so how can we tell when M_p is prime ? It comes as no surprise to find a convenient test available.

Lemma 5.3 (Lucas Test). Define the sequence S_n as follows : S₀ = 4, S_k+1 = S_k² -2. Then M_p is prime if and only if M_p divides S_{p- 2}.

Proof : The sequence S_n is obtained from the Lucas sequence V_n(2, -2) and the proof involves Lucasian primality results which we have not sufficiently explored.

The Lucas Test is ideal for implementation on a computer, and the largest primes in existence at any one time are almost always Mersenne Numbers. Needless to say, there is currently a very large-scale co-ordinated search to find the next larger Mersenne Prime, colloquially known as GIMPS (the Great Internet Mersenne Prime Search), which is responsible for the largest currently known Mersenne primes. The history behind the full list of Mersenne Primes is a fascinating walk through the advancement of algorithmic and computational number theory. Exponents consist of the following:

n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161

The nature of the distributive project GIMPS means that Mersenne Primes are sometimes found out of sequence and it is always possible that new smaller ones may be found until the point where exhaustive searches have been completed to each exponent.

For exponents that are not prime, and for composite Mersenne Numbers, the search for factors takes over. There are several restrictions that can be placed on these.

Lemma 5.4. If p is an odd prime, then any factor of M_p is of the form 2kp+1 for some k.

Proof : Let q be a prime divisor of M_p. Then 2^p º 1 (mod q). Let r be the order of 2 modulo q. Then r | p by Lemma 2.13(ii). Now r ¹ 1, so r = p. We also know that 2^q-1 º 1 (mod q), so that r | q-1, and hence p | q-1. Hence q = tp+1 for some t. If t were odd, then q would be even, which is nonsense, so t is even, that is, t = 2k for some k. Hence result.

Lemma 5.5. If p is an odd prime, then any prime factor of M_p is of the form q º ±1 (mod 8).

Proof : Suppose q = 2n+1 is an odd prime factor of M_p. Let a = 2^(p+1)/2. Then a² -2 = 2^p+1 -2 = 2M_p º 0 (mod q). Hence a^q-1 = a²ⁿ º 2ⁿ (mod q). Since gcd(a, q) = 1, we have a^q-1 º 1 (mod q). Hence 2ⁿ º 1 (mod q), that is, 2^(q-1)/2 º 1 (mod q). By Lemma 4.2(iii), this means (2/q) = 1, and by Lemma 4.4, this means that q º ±1 (mod 8), as required.

An immediate corollary of this is that if q = 2n+1 is an odd prime and q º ±1 (mod 8) then q divides 2ⁿ -1, and, in particular, if n is also prime, then q | M_n (noting that this requires n º 3 (mod 4)). Hence the interest in prime pairs of the form p and 2p+1, i.e. Sophie-Germain primes.

The factorisation of Mersenne composite and related forms is the main task of the Cunningham-Woodall Project. Related projects include those dedicated to factoring using a particular algorithm, e.g. ECMNET.

A number of outstanding conjectures exist regarding Fermat and Mersenne numbers :

1. There are infinitely many prime Fermat numbers
2. There are infinitely many composite Fermat numbers
3. There is at least one generalised Fermat number for every exponent m
4. There are infinitely many prime Mersenne numbers
5. There are infinitely many composite Mersenne numbers

Off the cuff responses to the above, completely unproven, are :

1. False
2. True
3. Maybe
4. Probably
5. True

There are many other special forms of numbers for which the primality tests presented in the previous section may be used. In general, we are interested in n such that n+1 or n-1 is easily decomposed into primes.

In the standard proof, of Euclid, of the infinity of primes, we consider multiplying together all the primes and then adding 1. This suggests another possible source of large primes that would be relatively easy to test, as follows. If the number N is divisible by each member of a set of primes P, then the numbers N+1 and N-1 cannot be divisible by any of the primes in P. Hence if we let P include all the primes up to a fixed limit, then N±1 will have much higher likelihood of being prime.

Definition. A primorial number is an number of the form p#±1, where p is prime and p# represents the product of the primes less than or equal to p.

We can test primorials for primality using Lemma 4.3 or Lemma 4.9, depending on the sign.

p#+1 is prime for p = 2, 3, 5, 7, 11, 31, 379, 1019, 1021, 2657, 3229, 4547, 11549, 13649, 18523, 23801, 24029, 42209, 145823, 366439, 392113

p#-1 is prime for p = 3, 5, 11, 13, 41, 89, 317, 991, 1873, 2053, 2377, 4093, 4297, 4583, 6569, 13033, 15877, 843301, 1098133

There is an active co-ordinated search to find primes of this form here.

Similarly, the number n! is divisible by all the primes less than or equal to n (to various powers), so n!±1 fits the pattern. Primes of this form are called factorial primes.

n!+1 is prime for n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, 340, 399, 427, 872, 1477, 6380, 26951, 110059, 150209

n!-1 is prime for n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, 379, 469, 546, 974, 1963, 3507, 3610, 6917, 21480, 34790, 94550, 103040

There is an active co-ordinated search to find primes of this form here.

Definition : A multifactorial number is a number of the form n*(n- r)*(n- 2r)*…*(n-xr)± 1 where n-(x+1)r < 0. This is abbreviated to n!_r ±1. Hence n! = n!₁.

There is an active co-ordinated search to find primes of this form here.

In fact, we can choose any form of number we like as long as n+1 or n-1 is easily factored, e.g. p#2ⁿ ±1, n!_r.2ⁿ ±1, but these can be taken to ridiculous extremes, for instance, we have :

Definition : A compositorial number is a number of the form (n!/n#) ±1. We ignore the case when n is prime as it takes the same value as the previous.

(n!/n#) +1 is prime for n = 1, 4, 8, 14, 20, 26, 34, 56, 104, 153, 182, 194, 217, 230, 280, 462, 529, 1445

(n!/n#) -1 is prime for n = 4, 6, 8, 16, 21, 34, 39, 45, 50, 72, 76, 133, 164, 202, 216, 221, 280, 496, 605, 2532, 2967, 3337

Definition: A factoprimorial number is a number of the form n!± n#± 1.

n!+n#+1 is prime for n = 1, 2, 3, 4, 5, 6, 8, 17, 18, 24, 95, 96, 142, 1022, 1120, 1580, 6942, 19255, 19401

n!+n#-1 is prime for n = 2, 3, 4, 5, 8, 17, 23, 26, 35, 47, 82, 100, 147, 183, 271, 492, 708, 1116, 1538, 2491, 4207, 4468, 16878

n!-n#+1 is prime for n = 4, 6, 7, 8, 10, 14, 20, 21, 26, 101, 119, 172, 409, 621, 1043, 1204, 1283, 1673, 2003, 4336, 5773, 12913, 13517

n!-n#-1 is prime for n = 4, 5, 20, 92, 106, 266, 308, 343, 583, 597, 903, 1021, 1239, 1314, 2458, 6160, 9627, 10649

The following numbers are of interest.

Definition. A Cullen Number is a number of the form n*2ⁿ +1. A Woodall Number is a number of the form n*2ⁿ -1. A generalised Cullen is of the form n*aⁿ +1, and a generalised Woodall is of the form n*aⁿ -1.

These have been studied for a long time, hence the individual names attached.

There are Cullen numbers at n = 1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881

There are Woodall numbers at n = 2, 3, 6, 30, 75, 81, 115, 123, 249, 362, 384, 462, 512, 751, 822, 5312, 7755, 9531, 12379, 15822, 18885, 22971, 23005, 98726, 143018, 151023, 667071, 1195203, 1268979, 1467763, 2013992, 2367906, 3752948

The current best generalised Woodall and Cullen primes can be found on Ray Ballinger's site.

Generalised Cullen and Woodall numbers are investigated at Paul Leyland's site.

Here is another of the older ideas.

Definition. A repunit is a number which has all n digits equal to 1, i.e. (10ⁿ - 1)/9. A generalised repunit is a number of the form (bⁿ -1)/(b-1).

Standard repunits have been searched for primes to very high values, and give primes and PRPs for

n = 2, 19, 23, 317, 1031 (prime to here) and 49081, 86453, 109297 and 270343 (PRP only)

There is no distributive project currently set up to search for primes amongst the more general form.

How many times have I mentioned Dirichlet's Theorem ? Rephrased, this implies that any polynomial of degree 1 in one unknown with integer coefficients that are relatively prime provides a source of an infinite number of primes. What if we increase the degree of the polynomial ? Consider n² + n + 2. This might look interesting, but always takes an even value, even though the greatest common divisors of the coefficients taken pairwise are equal to 1. Therefore we must restrict ourselves to polynomials which do not have such an easily extracted divisor. The simplest example is n² + 1. If n > 1 and n odd, then this is divisible by 2, so n must be even. This form is prime for n = 1, 2, 4, 6, 10, etc. In fact there are 112 primes for n £ 1000 and 54110 for n £ 1000000. The conjecture

6. There are infinitely many primes of the form n² +1

remains unproven but realistically true. Going even further, Hardy and Littlewood conjectured that

7. There are infinitely twin primes of the form n² +1, n² +3

The famous formula n² + n + 41 provides primes for n = 0 to n = 39 before faltering at n = 40. This encourages us to look for formulae that give longer runs of primes. The polynomial 47n² - 1701n + 10181 provides distinct primes for n = 0 to n = 42, and the polynomial 36n² - 810n + 2753 provides distinct primes for n = 0 to n = 44.

Back with n² + n + 41, if we keep searching, we find that the number of primes of this form for n £ 10⁶ is 261080, which is a very high density of primes. Can we find other values a such that n² + n + a produces even more primes ? In fact, a = 27941 provides 286128 primes of this form for n £ 10⁶ and a = 21425625701 provides 361841 primes for n £ 10⁶. Another polynomial that provides a high density of primes is 2n² - 199. The most prolific quadratic currently known is 2n² - 1584n + 98621, for which 706 values of n £ 1000 give primes. These formulae are no accidents, but arise naturally from modular arguments, as I expand here.

Until now, we have considered primes from a mainly multiplicative viewpoint, not least because of the Fundamental Theorem of Arithmetic. However, there are results and conjectures from additive number theory that pertain to primes. The most famous conjecture in this area is the following :

8. Every even number n > 2 can be expressed as the sum of two primes.

This is a restatement by Euler of the original Goldbach conjecture that every integer n > 5 is the sum of three primes. It remains unproven, but many results have been obtained over the years regarding the following generalisation.

Lemma 5.6. There exists a number S such that every sufficiently large integer is the sum of at most S primes.

Note that this has been proved, and that it automatically implies that there exists a second number S₀ ³ S, such that every integer greater than 1 is the sum of at most S₀ primes. Goldbach's conjecture is then equivalent to the statement S₀ = 2. Vinogradov used very advanced results in analytic number theory to prove that S £ 4. However, his lower bound is too large for a reasonable bound for S₀ to be obtained. Separate arguments, based on the proof of Lemma 8.1, have since been used to reach S₀ £ 6, which still seems a long way from the ultimate target.

The conjecture can be generalised in a different manner.

Definition. For all positive integers n, n can be represented uniquely as a product of primes in the form n = p₁^e1p₂^e2… Let P_k be the set of positive integers such that the sum of the exponents e₁, e₂, … is less than or equal to k. Members of the set P_k are sometimes called k-almost-primes.

Hence P₁ is the set of primes, and P₂ is the set of primes, squares of primes and products of two distinct primes.

The alternative approach is to consider the set P_k + P_h of sums of integers in P_k and P_h. Goldbach's conjecture is then equivalent to the statement that the set P₁ + P₁ covers all even integers n > 2. Any early result of this type is that every sufficiently large even integer belongs to P₉ + P₉, and this was eventually improved to P₂ + P₃. Renyi proved in 1947 that every sufficiently large even integer is in P₁ + P_k for some k, and the best result obtained is the following.

Lemma 5.7 (Chen). Every sufficiently large even integer is in P₁ + P₂.

A nice result that Chen proved at the same time is that is p is a prime, then p + 2 is in P₂, which is close to proving the infinity of twin primes.

There are other conjectures along these lines, for instance

9. Every sufficiently large integer is either a square or the sum of a prime and a square.

Heuristic arguments by Hardy and Littlewood took conjectures F and I even further :

10. There are infinitely many primes of the form n³ +1
11. Every sufficiently large integer is either a cube or the sum of a prime and a cube.

 Such speculation serves little purpose without some concrete mathematical results.

In Section 6, we concentrate on primes of the form k*2^m +1, among other reasons as they provide potential factors of Fermat Numbers as shown above.