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^{n} +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^{n} º 2^{kp}
º (2^{k})^{p}
º (-1)^{p}
(mod q). Since p is odd, we have 2^{n} º
-1 (mod q), and so 2^{n} +1
cannot be prime. Hence for 2^{n} +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^{n} +1, where n = 2^{m}.

F_{m} is prime for m
= 0, 1, 2, 3 and 4. However, F_{5} = 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^{n} where n = 2^{m}, and suppose that F_{m}
has a factor p. Then 2^{n} º -1 (mod p), and so 2^{2n}
º 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^{n} + 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^{25} +1 divides
F_{23}

3*2^{41} +1 divides
F_{38}

21*2^{41} +1 divides
F_{39}

425*2^{79} +1
divides F_{77}

247*2^{302} +1
divides F_{298}

431*2^{2099} +1
divides F_{2089}

57*2^{25010} +1
divides F_{25006}

3*2^{382449} +1
divides F_{382447}

168329*2^{7187} +1
divides F_{7181}

491628159*2^{669} +1
divides F_{667}

Definition
: The **generalised Fermat Number** GF(a,m)
= a^{n} +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^{n} +1 is a distinct benefit, since it avoids the need
to reproduce possible divisors. Note that as with Fermat numbers, in order for a^{n} +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^{n} -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^{n} º 2^{pk} º 1 (mod q), so 2^{n} -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^{11} - 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_{0} = 4, S_{k+1} = S_{k}^{2}
-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 = 2^{p+1}
-2 = 2M_{p} º 0 (mod q). Hence a^{q}^{-1} = a^{2n} º 2^{n} (mod q). Since gcd(a, q)
= 1, we have a^{q}^{-1}
º 1 (mod q). Hence 2^{n} º 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^{n}
-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 :

- There are infinitely many prime Fermat numbers
- There are infinitely many composite Fermat numbers
- There is at least one generalised Fermat number for every exponent m
- There are infinitely many prime Mersenne numbers
- There are infinitely many composite Mersenne numbers

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

- False
- True
- Maybe
- Probably
- 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

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

- There
are infinitely many primes of the form n
^{2}+1

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

- There
are infinitely twin primes of the form n
^{2}+1, n^{2}+3

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

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

- 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_{0}
³ S, such that every integer greater
than 1 is the sum of at most S_{0} primes. Goldbach's
conjecture is then equivalent to the statement S_{0} = 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_{0} to be
obtained. Separate arguments, based on the proof of Lemma 8.1, have since been
used to reach S_{0} £ 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_{1}^{e}1p_{2}^{e}2… Let P_{k}
be the set of positive integers such that the sum of the exponents e_{1},
e_{2}, … is less than or equal to k. Members
of the set P_{k} are sometimes called **k-almost-primes**.

Hence P_{1} is the
set of primes, and P_{2} 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_{1} + P_{1} covers all even integers n > 2.
Any early result of this type is that every sufficiently large even integer
belongs to P_{9} + P_{9}, and this was eventually improved to P_{2}
+ P_{3}. Renyi proved in 1947 that every
sufficiently large even integer is in P_{1} + 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_{1} + P_{2}.

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

There are other conjectures along these lines, for instance

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

- There
are infinitely many primes of the form n
^{3}+1 - 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.