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 = 2^{k}^{}^{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 k2 is divisible by exactly t powers of 3, then 2^{k}^{}^{1} + k is also divisible by exactly t powers of 3. 

Proof: The premise implies that k = c3^{t} + 2, for some odd integer c coprime 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 nonnegative integer t and odd integer c. Since c is odd, we can write c = 2d + 1 for some nonnegative 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 3^{t+2}. Therefore, adding 1 to this quantity gives an integer divisible by 3^{t+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 coprime to 3). □ 

Proposition 9: If q^{n} = (k+1)/2 is an odd prime power, then q divides 2^{k1} + k. 

Proof: The premise implies k = 2q^{n} – 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 2^{k}^{}^{1} + k. 

Proof: The premise implies k = (q1)/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 2^{k1} + k is divisible by 5. 

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



Noting that 2^{4} = 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 2^{2} = 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 s_{k} = 2^{k}^{}^{1} + k satisfy the linear recurrence 



with initial values s_{1} = 2 and s_{2} = 4. When the elements of this sequence are evaluated modulo the prime p, they are periodic with a period dividing t_{p} = p(p1). Thus, identifying the "zero terms" gives a set of arithmetic sequences such that if k is in one of these sequences, then s_{k} is divisible by p. This approach gives the following oddvalued 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 2^{k}^{}^{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 = 2^{k}^{}^{1} + k is prime is 237, which gives the following 72digit 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 s_{k}. 
(ii) If k2 is odd and divisible by n powers of 3, then s_{k} is also divisible by n powers of 3. 
(iii) If q^{n} = (k+1)/2 is a power of a prime q, then q divides s_{k}. 
(iv) If q = 2k+1 is a prime, and 2 is a square (mod q), then q divides s_{k}. 
(v) For any odd prime p with w = ord_{p}(2), there are w residues r modulo pw such that if k = r modulo pw then p divides s_{k}. 

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(p1). The modulus p(p1) 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(p1) = 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 p1 integers q in the range 1 to p(p1)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 nonzero 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 nonzero 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 p1 distinct q values in the range 1 to p(p1)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 2^{w} = 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 w_{p} is the order of 2 (mod p), and the coefficients are 



Notice that the values of B_{i} (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 w_{43} = 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 (p1)/w_{p}  1) and with the coefficients 



In general, to satisfy the congruence 2^{q}^{}^{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 q1 on 2 will give a distinct result (mod p) only for distinct residues of q1 modulo the order of 2 (mod p). Letting w denote this order, i.e., w = ord_{p}(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 2^{j}^{}^{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,.., q1. For each of these values of m, we take the smallest (p1)/w solutions, and from those B values we compute q = 1 + m + Bw. This gives all p1 values suitable values of q modulo p(p1), 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 2^{k}^{}^{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 2^{k}^{}^{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. 
