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 2n +1. Suppose that n has an odd prime factor p, so that n = kp for some k. Let q = 2k +1. Then 2k º -1 (mod q), so 2n º 2kp º (2k)p º (-1)p (mod q). Since p is odd, we have 2n º -1 (mod q), and so 2n +1 cannot be prime. Hence for 2n +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 Fm = 2n +1, where n = 2m.

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

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

Proof : Suppose Fm is prime. Now Fm = 22k +1 = 4k +1 º 5 (mod 12) for some k. By Lemma 4.8, we have (3/Fm) = -1, which is all we need, by Lemma 4.2(iii). In other words, if Fm is prime, 3 is a primitive root of Fm. Conversely, we can invoke Lemma 3.5 with a = 3 and k = 1 to establish that Fm 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 Fm (m ³ 2) is of the form k*2m+2 +1.

Proof : Let Fm = 2n where n = 2m, and suppose that Fm has a factor p. Then 2n º -1 (mod p), and so 22n º 1 (mod p). By Fermat's Little Theorem, 2n = 2m+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 2m+1 divides (p-1)/2, so 2m+2 divides p-1, as required.

This is one of the main reasons why numbers of the form k.2n + 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*225 +1 divides F23

3*241 +1 divides F38

21*241 +1 divides F39

425*279 +1 divides F77

247*2302 +1 divides F298

431*22099 +1 divides F2089

57*225010 +1 divides F25006

3*2382449 +1 divides F382447

168329*27187 +1 divides F7181

491628159*2669 +1 divides F667

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

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.2m+1 +1 rather than k.2m+2 +1. In this respect, having tables of primes of the form k.2n +1 is a distinct benefit, since it avoids the need to reproduce possible divisors. Note that as with Fermat numbers, in order for an +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 : 2n -1. Suppose that n is not prime, so that n = pk for some prime p and integer k > 1, and let q = 2p -1. Then since 2p º 1 (mod q), we have 2n º 2pk º 1 (mod q), so 2n -1 cannot be prime. Hence n must be prime.

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

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

Lemma 5.3 (Lucas Test). Define the sequence Sn as follows : S0 = 4, Sk+1 = Sk2 -2. Then Mp is prime if and only if Mp divides Sp- 2.

Proof : The sequence Sn is obtained from the Lucas sequence Vn(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 Mp is of the form 2kp+1 for some k.

Proof : Let q be a prime divisor of Mp. Then 2p º 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 2q-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 Mp is of the form q º ±1 (mod 8).

Proof : Suppose q = 2n+1 is an odd prime factor of Mp. Let a = 2(p+1)/2. Then a2 -2 = 2p+1 -2 = 2Mp º 0 (mod q). Hence aq-1 = a2n º 2n (mod q). Since gcd(a, q) = 1, we have aq-1 º 1 (mod q). Hence 2n º 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 2n -1, and, in particular, if n is also prime, then q | Mn (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!1.

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#2n ±1, n!r.2n ±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*2n +1. A Woodall Number is a number of the form n*2n -1. A generalised Cullen is of the form n*an +1, and a generalised Woodall is of the form n*an -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. (10n - 1)/9. A generalised repunit is a number of the form (bn -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 n2 + 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 n2 + 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

1. There are infinitely many primes of the form n2 +1

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

1. There are infinitely twin primes of the form n2 +1, n2 +3

The famous formula n2 + 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 47n2 - 1701n + 10181 provides distinct primes for n = 0 to n = 42, and the polynomial 36n2 - 810n + 2753 provides distinct primes for n = 0 to n = 44.

Back with n2 + n + 41, if we keep searching, we find that the number of primes of this form for n £ 106 is 261080, which is a very high density of primes. Can we find other values a such that n2 + n + a produces even more primes ? In fact, a = 27941 provides 286128 primes of this form for n £ 106 and a = 21425625701 provides 361841 primes for n £ 106. Another polynomial that provides a high density of primes is 2n2 - 199. The most prolific quadratic currently known is 2n2 - 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 :

1. 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 S0 ³ S, such that every integer greater than 1 is the sum of at most S0 primes. Goldbach's conjecture is then equivalent to the statement S0 = 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 S0 to be obtained. Separate arguments, based on the proof of Lemma 8.1, have since been used to reach S0 £ 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 = p1e1p2e2… Let Pk be the set of positive integers such that the sum of the exponents e1, e2, … is less than or equal to k. Members of the set Pk are sometimes called k-almost-primes.

Hence P1 is the set of primes, and P2 is the set of primes, squares of primes and products of two distinct primes.

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

Lemma 5.7 (Chen). Every sufficiently large even integer is in P1 + P2.

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

There are other conjectures along these lines, for instance

1. 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 :

1. There are infinitely many primes of the form n3 +1
2. 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*2m +1, among other reasons as they provide potential factors of Fermat Numbers as shown above.