Primes of the Form 2^(k-1) + k
The solution of a certain problem in number theory relies on the
existence of primes of the form
2^(k-1) + k = prime
The only such primes with k < 1000 are k = 1, 3, 7, and 237.
H. Zeisel found one more (probable) prime, with k=1885. For a
long time these were the only five values of k that were known to
yield primes (or probable primes). Bob Silverman gave a heuristic
estimate for the density of these primes suggesting that, although
there are presumably infinitely many such primes, the next one
would probably be extremely large, so that it might never be feasible
to find another one. His estimate was that the number of suitable
k values less than N should be about log log N (which of course is
quite a bit different than saying the number of PRIMES of this form
less than N is log log N, which would be more consistent with the
heuristic estimates for, say, Mersenne primes).
However, I was delighted to receive an email from Nuutti Kuosa in
November 1999 stating that he had test up to 2^(51674-1)+51674
and has found a new probable prime! Specifically, he found that
2^(k-1) + k is a probable prime with k = 51381. This prime
has 15467 digits. This answers Question #8 on the MathPages
Most Wanted List.
Incidentally, part of the reason that suitable k values are more rare
than, say, suitable Mersenne exponents, is that it's possible to
exclude large classes of k values by means of some simple divisibility
criteria that can be deduced for this form. For example, in my little
search up to k=1000 I used the following easily proven facts to seive
out most of the k values. (I'll denote 2^(k-1)+k by s_k.)
(1) If k is even, then so is s_k.
(2) If k-2 is odd and divisible by n powers of 3, then s_k is also
divisible by n powers of 3.
(3) If k = 9 or 11 (mod 20) then 5 divides s_k.
If k = 3, 5, or 13 (mod 42) then 7 divides s_k.
If k = 19, 21, 57, 73, or 105 (mod 110) then 11 divides s_k.
If k = 25, 69, 79, 87, 101, or 107 (mod 156) then 13 divides s_k.
etc.
In general, for any prime p, if k = {any of (p-1)/2 values}
modulo p(p-1) then p divides s_k.
(4) If q = (k+1)/2 is a prime, then q divides s_k.
(5) If q = 2k+1 is a prime, and 2 is a square (mod q), then q
divides s_k.
Does anyone know of any other divisibility criteria for s_k?
Just to elaborate on criteria (2) and (3) a little bit, notice that
for any prime p we can consider whether there exists a number q
such that p divides every number of the form
jp(p-1) + q - 1
2 + jp(p-1) + q = 0 (mod p) (1)
In other words, s^(k-1) + k is divisible by p whenever k is
congruent to q modulo p(p+1). Obviously since 2^(p-1) = 1 (mod p),
and since jp(p-1)=0 mod p, we can reduce the above to simply
q-1
2 + q = 0 (mod p) (2)
Hence if we can find an integer q that satisfies (2), then it also
satisfies (1) every non-negative integer j. Notice that the modulus
p(p-1) is chosen so that it has the two properties of being zero
mod p and being an exponent that gives unity mod p.
Now, it so happens that, 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 brief
table of these q values for the first few odd primes is given below:
p q
--- ----------------------------------------------
3 4 5
5 9 11 12 18
7 3 5 13 24 26 34
11 14 19 21 42 48 56 57 60 73 105
13 25 34 50 69 79 80 84 87 101 107 148 150
If we exclude the even values of q (which comprise exactly half of
the w values, and which obviously yield an even value of k), these
are precisely the residues mentioned in criteria (2) and (3). It's
interesting to note that 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 expressed 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. Also, 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 w 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, it appears that 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 2^w = 1 (mod p).
An extreme example of this is with p=31, where we have 30 values of
w 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.
q
mod p q q q q q q
----- -------- -------- -------- -------- -------- --------
15 15 (0) 170 (5) 325 (10) 480 (15) 635 (20) 790 (25)
23 54 (1) 209 (6) 364 (11) 519 (16) 674 (21) 829 (26)
27 58 (1) 213 (6) 368 (11) 523 (16) 678 (21) 833 (26)
30 61 (1) 216 (6) 371 (11) 526 (16) 681 (21) 836 (26)
29 122 (3) 277 (8) 432 (13) 587 (18) 742 (21) 897 (28)
Thus we see that all the suitable q values for p=31 can be expressed
in the form
q[i,j] = (A_i + j w_p)p + B_i (3)
where j ranges from 0 to 5, and w_p is the order of 2 (mod p), and
the coefficients are
i A_i B_i
--- ----- -----
1 0 15 -16
2 1 23 -8
3 1 27 -4
4 1 30 -1
5 3 29 -2
Notice that the values of B_i are just the negatives of the powers of
2 (mod p). Similarly, with p=43, since the order of 2 (mod 43) is
w_43 = 14, the 42 suitable values of q are given by equation (3) with
j ranging from 0 to 2 (the upper index being (p-1)/w_p - 1) and with
the coefficients
i A_i B_i
--- ----- -----
1 1 42 -1
2 3 8 -1024
3 3 41 -2
4 6 4 -512
5 6 27 -16
6 6 39 -4
7 7 1 -128
8 7 2 -256
9 7 21 -16384
10 9 11 -32
11 9 32 -8192
12 10 16 -4096
13 11 35 -8
14 13 22 -64
In general, to satisfy the congruence
m-1
2 + m = 0 (mod p)
we have m = -2^(m-1) (mod p), which means there exists an integer
"a" such that
m-1
m = ap - 2
Also, the exponent m-1 on 2 will give a distinct result (mod p) only
for distinct residues of m-1 modulo the order of 2 (mod p). Letting
q denote this order, i.e., q = ord_p(2), we say
w
m = Ap - 2 m-1 = w + Bq
for some integer B. Eliminating m from these two equations gives
w
pA - qB = 2 + w + 1
So, for any prime p, we set q equal to the order of 2 (mod p), and
then we solve the above linear equation with w=0,1,..,q-1. For
each of these values of w, we take the smallest (p-1)/q solutions,
and from those B values we compute m = 1 + w + Bq. This gives all
p-1 values suitable values of m modulo p(p-1), but we can reduce
this by just considering the suitable values modulo pq, of which
there are exactly q.
For example, with p=31 we have q=5, and the suitable values of m
are any numbers congruent to 15, 54, 58, 61, or 122 modulo 155.
These numbers come from the minimum solutions of
w
31A - 5B = 2 + w + 1
with w = 0, 1, 2, 3, and 4. The minimum solutions in these cases
are (A,B) = (1,2), (2,10), (2,11), (2,12), and (4,24). Note that the
right hand side of the above equation is of the form 2^(j-1) + j.
Return to MathPages Main Menu
Сайт управляется системой
uCoz