Part 2:  Primes Related to Corollary 7.1


From Corollary 7.1 it follows that the only solution kernals n,m with n equal to a power of a prime are of the form



where k is any integer such that m is a prime. The only such values with k < 200 are:



The first two of these (with k = 1 or 3) do not give solution kernels because n £ 8 (see Proposition 7), but the pair m,n for k = 7 is a solution kernel.


When searching for primes of the form m = 2k-1 + k we can immediately exclude all even values of k, because they give m divisible by 2. We can also exclude many other values of k, as described in the following propositions.


Proposition 8:  If k is odd and k-2 is divisible by exactly t powers of 3, then 2k-1 + k  is also divisible by exactly t powers of 3.


Proof:  The premise implies that k = c3t + 2, for some odd integer c co-prime to 3, so we have



Thus, we need only show that the quantity in parentheses is divisible by at least t + 1 powers of 3 for any non-negative integer t and odd integer c. Since c is odd, we can write c = 2d + 1 for some non-negative integer d. Then, with t = 0, the quantity in parentheses can be written



Noting that 4 = 1 (mod 3), it's clear that this quantity is divisible by 3 for any integer d. Therefore, the exponential term is congruent to -1 (mod 3), which allows us to write



where t = 0. Taking the cube of both sides gives



which shows that



is congruent to -1 modulo 3t+2. Therefore, adding 1 to this quantity gives an integer divisible by 3t+2. By induction, it follows that for every t, the quantity



is divisible by t+1 powers of t, which proves that the quantity



is divisible by exactly t powers of 3 (recalling that c is co-prime to 3).


Proposition 9:  If qn = (k+1)/2 is an odd prime power, then q divides 2k-1 + k.


Proof:  The premise implies k = 2qn – 1, so we have



The quantity in parentheses is congruent to 0 (mod q) by Fermat's Little Theorem, so the entire quantity is divisible by q.


Proposition 10:  If  q = 2k + 1  is a prime, and 2 is a square modulo q, then q divides  2k-1 + k.


Proof:  The premise implies  k = (q-1)/2, so we have



Multiplying by 2 gives



Thus, if 2 is a square modulo q, it follows that the quantity in brackets is congruent to 0 (mod q), so the entire quantity is divisibly by q. □


Proposition 11:  If k is of the form 20c + 9 or 20c + 11, then 2k-1 + k is divisible by 5.


Proof:  If k = 20c + 9 then we have



Noting that 24 = 1 (mod 5) and that 9 = -1 (mod 5), it follows immediately that this quantity is divisible by 5.


If k = 20c + 11, then we have



Noting that 22 = -1 (mod 5) and that 10c+5 is always odd, it's clear that the first term on the right side is always congruent to -1 (mod 5). Also, 11 is congruent to +1 (mod 5), so the entire quantity is divisible by 5. □


Discussion:  Proposition 11 can be generalized to give an infinite family of divisibility tests. Notice that the integers sk = 2k-1 + k satisfy the linear recurrence



with initial values s1 = 2 and s2 = 4. When the elements of this sequence are evaluated modulo the prime p, they are periodic with a period dividing tp = p(p-1). Thus, identifying the "zero terms" gives a set of arithmetic sequences such that if k is in one of these sequences, then sk is divisible by p. This approach gives the following odd-valued arithmetic sequences:



With just these sequences we can exclude all k values less than 100 (other than 1, 3, and 7) except for k = 27, 43, and 67, all of which can be excluded by direct factorization. Indeed this approach allows us to determine that 2k-1 + k is not prime for any other k (besides 1, 3, and 7) less than 200. The smallest integer k > 7 such that  m = 2k-1 + k  is prime is 237, which gives the following 72-digit prime:



The next (probable) prime, found by H. Zeisel, corresponds to k = 1885, and for a long time this was the largest value of k known to yield a prime (or probable prime). Then, in November 1999, Nuutti Kuosa reported that he had tested up to 2(51674-1) + 51674 and had found that 2(k-1) + k is a probable prime with k = 51381. This prime has 15467 digits. Notice that suitable k values are more rare than suitable Mersenne exponents, because the simple divisibility conditions described above exclude large classes of k values. These criteria can be summarized as follows:


(i)   If k is even, then so is sk.

(ii) If k-2 is odd and divisible by n powers of 3, then sk is also divisible by n powers of 3.

(iii) If qn = (k+1)/2 is a power of a prime q, then q divides sk.

(iv) If q = 2k+1 is a prime, and 2 is a square (mod q), then q divides sk.

(v) For any odd prime p with w = ordp(2), there are w residues r modulo pw such that if k = r modulo pw then p divides sk.


To elaborate on criterion (v), notice that for any prime p we can consider whether there exists a number q such that



for every integer j. In other words, 2(k-1) + k  is divisible by p whenever k is congruent to q modulo p(p-1). The modulus p(p-1) was chosen so that it has the two properties of being zero mod p and being an exponent that gives unity mod p (by Fermat's Little Theorem). Obviously since 2(p-1) = 1 (mod p), and since jp(p-1) = 0 mod p, we can reduce the above to simply



Hence if we can find an integer q that satisfies (2), then it also satisfies (1) for every j.


Now, for every odd prime p there are p-1 integers q in the range 1 to p(p-1)-1 that satisfy congruence (2). A table of these q values for the first few odd primes is given below:



Of course, in practice we can omit the even values of q (which comprise exactly half of the values), because they yield an even value of k. The values of q for any given prime p represent a closed set (mod p) of powers of 2 times one particular base. For example, with p = 11 the values of q reduced modulo p are {3, 8, 10, 9, 4, 1, 2, 5, 7, 6} respectively, which represents a complete set of non-zero residues mod 11. These can be arranged as a geometric series in powers of 2 (mod 11) as follows: {1, 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, ...}, where each number is 2 times the previous number in the cycle. Since the order of 2 (mod 11) is 10, we get all 10 residues.


However, this isn't always the case. For example, with p = 7 the reduced q values modulo 7 are {3, 5, 6, 3, 5, 6}, which represents only half of the non-zero residues (mod 7), but as always this is a complete cycle under doubling, because 2(3) = 6, 2(6) = 5, and 2(5) = 3, all modulo 7. Hence, although there are p-1 distinct q values in the range 1 to p(p-1)-1, the number of distinct residue classes (mod p) represented among these q values is just equal to the order of 2 (mod p), i.e., the smallest exponent w such that 2w = 1 (mod p).


An extreme example of this is with p = 31, where we have 30 values of q that satisfy (2), but these fall into only 5 distinct residue classes modulo 31 because the order of 2 (mod 31) is just 5. Here's a summary of these q values.



These q values can be expressed in the form



where j ranges from 0 to 5, and wp is the order of 2 (mod p), and the coefficients are



Notice that the values of Bi (which are just the reduced values q mod p) are precisely the negatives of the powers of 2 (mod p).


For another example, with p = 43, the order of 2 (mod 43) is w43 = 14, so the 42 suitable values of q are given by equation (3) with j ranging from 0 to 2 (the upper index 2 being (p-1)/wp - 1) and with the coefficients



In general, to satisfy the congruence 2q-1 + q = 0 (mod p) we have q = -2(q-1) (mod p), which means there exists an integer "a" such that



Also, the exponent q-1 on 2 will give a distinct result (mod p) only for distinct residues of q-1 modulo the order of 2 (mod p). Letting w denote this order, i.e., w = ordp(2), we can set



for integers A, B, and m. Eliminating q from these two equations gives



(Notice that the right hand side of the above equation is of the form 2j-1 + j.) So, for any prime p, we set w equal to the order of 2 (mod p), and then we solve the above linear equation with m = 0, 1,.., q-1. For each of these values of m, we take the smallest (p-1)/w solutions, and from those B values we compute q = 1 + m + Bw. This gives all p-1 values suitable values of q modulo p(p-1), but we can reduce this by just considering the suitable values modulo pw, of which there are exactly w.


For example, with p = 31 we have w = 5, and the minimal solutions of



with m = 0, 1, 2, 3, and 4 are (A,B) = (2,12), (4,24), (2,11), (2,10), and (1,2) respectively. From the relation q - 1 = m + Bw we then infer that the suitable values of q are any numbers congruent modulo 155 to 61, 122, 58, 54, and 15 respectively. In other words, we have found that 2k-1 + k is divisible by 31 if k is any number of the form 155n+15, 155n+54, 155n+58, 155n+61, or 155n+122. For example, setting k=15 gives 2k-1 + k = 16399 = (31)(529). Even for negative values of n, the numerator of the resulting reduced fraction is divisible by 31, as would be expected, because the denominator is a pure power of 2, which is coprime to 31, so the divisions are unique modulo p.


Table of Contents