General Divisibility Theory

All odd numbers take the form k.2ⁿ +1 for some k and n, with k odd. It so happens that any factors of a Fermat number F_m must take the form k.2ⁿ +1 for some n such that n- m ³ 2. It also happens that there is a straightforward and easily implemented theorem for primality when k < 2ⁿ. Primes of the form k.2ⁿ +1 are called Robinson primes. The search for factors of Fermat numbers and the search for large primes in general give ample justification for a detailed investigation of the divisibility properties of odd numbers when in this form.

The mathematical prerequisites are basic. We shall take for granted the Fundamental Theorem of Arithmetic, that is, given two (positive) integers a and b, there exist integers q and r such that a = qb + r where 0 £ r < b. We shall also use Fermat's Little Theorem, that is, for a prime p and integer q such that p does not divide q, we have q^{p- 1} º 1 mod p.

For a particular value of k, we shall sieve over the exponent n. This means that we attempt to remove as many n as possible (in a given range) from consideration as primes by finding factors. In the following, k is always odd.

Fermat's Little Theorem tells us that for all odd primes p, we have 2^{p- 1} º 1 mod p. It is therefore obvious that there exists a minimal value e > 0, called the exponent of p to base 2, such that 2^e º 1 mod p and, for all 0 < f < e, 2^f ¹ 1 mod p. It is a straightforward corollary that e divides p- 1.

For an odd prime p, if there exists r such that p divides k.2^r +1, then p divides k.2ⁿ +1 if and only if n º r mod e, where e is the exponent of p to base 2.

By the Fundamental Theorem, there exists q such that n = qe + r. We then have k.2ⁿ +1 º k.2^qe+r +1 º k.(2^e)^q.2^r + 1 º k.2^r +1 º 0 mod p, as required. On the contrary, suppose there exists n ¹ r mod e such that p divides k.2ⁿ +1. Then n = qe + r + s for some q and s, chosen so that 0 < s < e. Then k.2ⁿ + 1 º k.2^r.2^s + 1 º 0 mod p. Since k.2^r º - 1 mod p, this implies that 2^s º 1 mod p, contradicting the minimality of e. Hence result.

For an odd prime p and odd k, if p does not divide k, then p divides k.2^r +1 if and only if 2^x + k º 0 mod p for some x such that r + x º 0 mod e.

Suppose r exists. Choose q such that qe ³ r. We have k.2^r º - 1 º - 2^qe mod p. We can divide by 2^r to obtain

k º - 2^{qe- r} mod p. Take x = qe - r. On the contrary, suppose 2^x + k º 0 mod p. Then k º - 2^x mod p. Let r = qe - x for some q. We multiply both sides by 2- ^x to obtain k.2- ^x º - 1 mod p. Since 2^qe º 1 mod p, we can insert 2^qe and add 1 to either side to obtain k.2^{qe- x} + 1 º 0 mod p, that is, k.2^r + 1 º 0 mod p, as required. Hence result.

In Theorem 2, if r exists, it is unique mod e.

Suppose not. Then p divides both k.2^r +1 and k.2^s +1 for 0 £ r, s < e. Suppose s > r and let t = s - r. Then

0 º 2^t.(k.2^r +1) - (k.2^s +1) º (2^t - 1) mod p, that is 2^t º 1 mod p, which contradicts the minimality of e. Hence result.

For an odd prime p, 2^f º 1 mod p if and only if f is a multiple of the exponent e of p to base 2. Thus 2^f - 1 factors into primes of exponent dividing f. This also means that the number of primes with a given exponent is finite.

Suppose 2^f º 1 mod p and let f = qe + r for some q and r, with 0 < r < e. Then 2^f º 2^qe+r º 2^r º 1 mod p, which contradicts the minimality of e. Thus r = 0. The contrary is immediate from the definition of e. Hence result.

Given a fixed value of k, this sieve proceeds as follows. For each possible value of exponent e, up to a given limit, we identify the primes in the factorisation of 2^e - 1 that do not occur in the factorisation of any smaller number of this form. The primes so obtained are (all) those with exponent e by Lemma 1. We then check this set of primes to see if they divide any one of the numbers 2^x + k for 0 £ x < e. If p divides 2^x + k, then by definition p does not divide k, and we also let r = - x mod e. Then by Theorem 1, p divides k.2^r + 1 and so divides k.2ⁿ + 1 for any n of the form qe + r where q > 0. The list of Nash congruences k.2^r + 1 º 0 mod p built up in this way, identified more simply by the pair (p,r), is called the Nash sieve (to whatever limit is placed on e). Chris Nash homepage. Theorem 2 is used in an actual implementation so that for each p being considered, we can check whether p divides either 2^q + k or k.2^q + 1 for q running from 0 to [e/2] and take r to be either - q mod e or q respectively. As soon as one or other of these divisions is true, the search for that p can be halted immediately by Corollary 1.

The Nash-Jobling implementation of the Nash sieve, called psieve, avoids the burden of having to factorise 2^e - 1 by calculating the greatest common factor between 2^e - 1 and 2^x + k for 0 £ x < e, and extracting any new primes that appear. This program has a large number of optional parameters, relating to subjects that we shall be introducing from now on.

For a given value of k, if (p,r) is a congruence obtained in the above manner, then p is said to "cover" the values of n = qe + r for any q, and, logically, n is said to be covered by p. Applying the Nash sieve to a fixed range of n to eliminate from consideration any value covered by (at least) one of the primes leaves a list of n which either have to be tested for primality directly or subjected to a larger sieve. The count of those n not covered after applying the Nash sieve is called the Nash weight. The standard Nash weight is calculated over the range 100000 £ n < 110000 and a limit on the exponent e of 256.

As long as the ranges we are working over are suitably large for both n and e, a zero Nash weight identifies a Sierpinski number, that is, a value of k for which there is no prime of the form k.2ⁿ +1 for any n. In this case, the primes in the Nash sieve comprise what is known as a "covering set" for k. Some of the primes may be redundant as they cover the same values of n, and so the idea of a covering set is modified to include the idea of minimality, that is, a covering set no subset of which is a covering set. The Sierpinski modulus of a covering set is the least common multiple of the exponents of the members of the set. For a given k, if every exponent from 1 to m can be covered by primes of exponent dividing m, then it follows that k is a Sierpinski number with modulus at most m. Removing redundancy will produce the covering set. The smallest known Sierpinski number is 78557, which has covering set {3,5,7,13,19,37,73} and modulus 36. Any smaller Sierpinski number would have to have an enormous covering set and huge modulus, and, amongst those values of k < 78557 for which no Robinson primes are known, this is unlikely. Follow these links for Sierpinski numbers and covering sets.

Values of low, but distinctly non-zero, Nash weight, typically less than 100, allow a search for Robinson primes to be pushed quickly to very high limits on n, with the hope of a very large prime being found. For very low scores, less than 30 say, it is possible that a small set of primes covers all but a few values of n, and that adding primes carefully to this set through some algorithm will eventually produce a covering set, possibly infinite. Another possibility is that there are values of k that satisfy the Sierpinski property for all but a finite set of exponents. These "almost Sierpinski" numbers are the subject of current research.

Logically, a quick way of ensuring a reasonably low Nash weight is to choose k that are not divisible by small primes, thereby increasing the likelihood of obtaining congruences involving these primes. Follow this link for more on this subject.

Values of k with a high Nash weight (typically greater than 5000) are prized as they are potentially rich sources of very large Robinson primes. Such k occur infrequently (there are only six values of k < 10000 with Nash weight above 5000). However, by being selective, one can find or generate values of k which have Nash weight considerably higher still. For example, the value k = 302627325 has a Nash weight of 7093. High Nash weights are a result of a lack of effective congruences. A quick way of ensuring a reasonably high score is therefore to consider k that are divisible by several small primes, since this means that Theorem 2 cannot be applied and so congruences not found. Indeed, for the value of k given above, the smallest prime providing a congruence is 19.

If p is a prime such that p divides k.2ⁿ +1, then p also divides (k+2p).2ⁿ +1, obviously. Thus k+2p has the same divisibility properties as k with respect to p. Another way of viewing this is that k and k+2p have the same Nash congruence with respect to p. The idea extends to sets of primes. Thus, if P is a set of primes, and P also represents the product of the set, then k+2P has the same divisibility properties as k with respect to the set of primes. Similarly, if p divides k.2ⁿ +1 and k > 2p then p divides (k- 2p).2ⁿ +1. Repeating if necessary, we can see that p divides k'.2ⁿ +1 where k' = k mod 2p. This also holds for set of primes, that is, if P is as before, then k mod 2P has the same divisibility properties as k with respect to P.

If p divides k.2ⁿ +1, then p divides (2k+p).2^{n- 1} +1, shifting the divisibility propertes of k with respect to p by one exponent. Thus if k has a Nash congruence (p,r), then 2k+p has Nash congruence (p,r- 1). This also extends to sets of prime P, so that replacing k by 2k+P affects each of the Nash congruences associated with the members if P in the same way. As with other iterations, we can apply the reduction argument to this non-trivially to obtain the Keller iteration k ® (2k+P) mod 2P.

If k is a Sierpinski number and P is the product of the primes in the covering set for k, then all the numbers generated by the Keller iteration are also Sierpinski numbers with the same covering set. This iterative process repeats with period equal to the Sierpinski modulus m, since at this point all the Nash congruences re-align. The sequence of repeated numbers so generated is called a Keller cycle. The simpler iteration k ® (k+2P) provides an infinite sequence of Sierpinski numbers. Applying the Keller iteration to any one of these values will re-create the same Keller cycle. For every Sierpinski number k with covering set P such that k > 2P, there is then a base value k' = k mod 2P, such that k' < 2P, and k' appears in a Keller cycle. Thus there is a finite number of base values, and therefore also of Keller cycles, for each finite covering set. For actual examples and more theory, go to Sierpinski numbers.

Theorems 1 and 2 have analogues for numbers of the form k.2ⁿ - 1. Thus, for an odd prime p and odd number k, if there exists r such that p divides k.2^r - 1, then p divides k.2ⁿ - 1 if and only if n º r mod e, where e is the exponent of p to base 2, and if p does not divide k, then p divides k.2^r - 1 if and only if 2^x - k º 0 mod p for some x such that r + x º 0 mod e. Hence we can build up Nash congruences, apply the Nash sieve and obtain Nash weights exactly as before. In order to differentiate, we shall refer to Nash weights associated with k.2ⁿ +1 and k.2ⁿ - 1 as positive and negative Nash weights respectively. Analogously to the positive case, values of k for which there is no prime of the form k.2ⁿ - 1 are called Riesel numbers.

If p divides k.2ⁿ +1 then p divides (2p- k).2ⁿ - 1.

Since k.2ⁿ º - 1 mod p, we have (k- 2p).2ⁿ º - 1 mod p. Multiplying both sides by - 1, we obtain (2p- k).2ⁿ º 1 mod p. Hence result.

It is obvious that the reverse is also true. The result is also true if p is replaced by a set of primes P. The result is also true if 2P < k, in which case we just take 2P- k mod 2P instead.

As the above implies, if P is a set of primes that produce Nash congruences with respect to numbers of the form k.2ⁿ +1 for some odd k, then k' = 2P- k (mod 2P if k < 2P) has the same Nash congruences with respect to numbers of the form k.2ⁿ - 1. In particular, k and k' have the same Nash weight, that is, k has the same positive Nash weight as k' has negative Nash weight. This is true when k is a Sierpinski number with P as its covering set. In this case, k' is a Riesel number. Thus there is a direct correlation between Sierpinski and Riesel numbers and so only the positive half need be studied.

Rather than generate and apply Nash congruences in the manner associated with the Nash sieve, an alternative is to proceed sequentially through all primes up to a chosen limit. The nature of the calculation of the exponent e allows us to find the value x defined above as a by-product. The choice of primes may also be restricted by placing a limit on e to speed up the algorithm. For example, we may choose to consider all primes less than 2^r, but place a limit on e of 2^s for s £ r. Weights can be calculated using this sieve in exactly the same way as before. Overhead may be reduced by having a prepared list of primes and their exponents, in which case only the x values need to be calculated. This sieve is used to search for numbers of high Nash weight.

The Nash sieve can be modified to narrow the search for twin primes of the form k.2ⁿ - 1 and k.2ⁿ +1. Basically, both a positive and a negative sieve are applied to the value of k and a Nash weight obtained by counting the number of exponents not covered by either sieve. The larger this weight, the more likely that twin primes will occur. The program psieve has an option to calculate this weight.

A Cunningham chain of the first kind is a sequence of the form p, 2p- 1, 4p- 1, etc. and a Cunningham chain of the second kind is a sequence of the form p, 2p+1, 4p+1, etc. The first prime in a Cunningham chain of the first kind of length 2 is commonly known as a Sophie-Germain prime. Chains of the first kind appear naturally amongst those numbers of the form k.2ⁿ - 1, and chains of the second amongst those numbers of the form k.2ⁿ +1. The longer the length of a chain, the greater the restriction on the form of k. For instance, chains of length 2 require k º 3 mod 6 and chains of length 4 require k º 15 mod 30. A Nash weight may be calculated for a particular length m by counting the number of distinct sequences of exponents of length at least m remaining after applying a Nash sieve. A slightly different weight may be obtained by removing the word "distinct" in the preceding sentence.

Lifchitz has defined a Bi-Twin as a set of 4 primes of the form k.2ⁿ ± 1 and k.2ⁿ⁺¹ ± 1. Here we have two sets of twin primes, a Cunningham chain of the first kind and a Cunningham chain of the second kind. We may extend this by considering a Bi-Chain to be simultaneous Cunningham chains of the first and second kinds with the same k values and n ranges. The smallest Bi-Twin (Bi-Chain of length 2) is the set {5,7,11,13}, where k = 3 and n = 1 & 2.

For more on chains in general.

URL : www.glasgowg43.freeserve.co.uk/nashdef.htm