1.Introduction


In 1960  Sierpinski proved the following theorem. 


Theorem  

There exist infinitely many odd integers k such that k*2^n + 1 is composite for every n >= 1.



Above k is called a Sierpinski number.

In 1962 Selfridge discovered the k = 78557 which is believed to be the smallest.

We can prove that 78557 is the smallest if we find a prime k*2^n + 1 for each k < 78557.

Many people have searched for k < 78557 which k*2^n + 1 is prime number.


Recent search results.

The prime 4847 * 2^3321063 + 1 is discovered.(2005) (999744 digits!)

The prime 19249 * 2^13018586 + 1 is discovered.(2007) (3918990 digits!)

The prime 33661 * 2^7031232+1 is discovered.(2007) (2116617 digits!)


The searching values k are 10223, 21181, 22699, 24737, 33661, 55459 and 67607.


Search project: http://www.seventeenorbust.com/


2.Method

       How to solve k*2^n+1=0 mod p?

       Condition

         p:prime
         b:positive integer
         a:positive integer
         n:positive integer

         (1). 2^b=1 mod p
         (2). n=a mod p
       
       From (1), then k=-2^(b-a) mod p

       From (2), k*2^n=-2^(b-a)*2^(a+b*m)=-1 mod p

       So,k*2^n+1 is composite for every n under the condition (1),(2).


       Example.

       We show the Selfridge's case.

       Covering set: k*2^n+1 is divisible by at least one member of the set.
       We use covering set:(3,5,7,13,19,37,73).

               p   b   a 

               3    2   0  
               5    4   1
               7    6   1
              13   12  11
              19   18  15
              37   36  27
              73    9   3

              Each of b*m+a set is

              2*m+0={0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34}
              4*m+1={1,5,9,13,17,21,25,29,33}
              6*m+1={1,7,13,19,25,31}
              12*m+11={11,23,35}
              18*m+15={15,33}
              36*m+27={27}
              9*m+3={3,12,21,30}

       Above all  set ={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
                        23,24,25,26,27,28,29,30,31,32,33,34,35}

       Next,we determine the value k.

              k=-2^(2-0)    mod 3
              k=-2^(4-1)    mod 5
              k=-2^(6-1)    mod 7
              k=-2^(12-11) mod 13
              k=-2^(18-15) mod 19
              k=-2^(36-27) mod 37
              k=-2^(9-3)   mod 73

       By Chinese Remainder Theorem,we get k=78557!

 
       78557*2^n+1 is divisible by at least one of the prime (3,5,7,13,19,37,73).

            n    78557*2^n+1 

             1  (5)*(7)*(67)^2
             2  (3)*(104743)
             3  (73)*(8609)
             4  (3)^2*(7)*(71)*(281)
             5  (5)^2*(193)*(521)
             6  (3)*(11)*(131)*(1163)
             7  (7)*(1436471)
             8  (3)*(541)*(12391)
             9  (5)*(59)*(136343)
            10  (3)^3*(7)^2*(41)*(1483)


3.Search results

        I searched some k under the following condition.
        We got the same k as Selfridge.

        Condition

        covering set=(3,5,7,13,19,37,73)
        b=(2,4,6,12,18,36,9)
        k< 10000000



                a                k

        (0,1,1,3,11,8,23)       8184977
        (0,1,1,11,15,3,27)     78557
        (0,1,3,7,11,8,23)       1256912
        (0,1,5,3,1,7,31)        4383062
        (0,1,5,7,15,0,3)        2510177
        (0,3,1,5,9,6,21)        5027648
        (0,3,1,9,11,5,17)       5152178
        (0,3,3,5,1,4,25)        7134623
        (0,3,5,9,13,1,25)        314228