From tonyforbes@ltkz.demon.co.ukMon Apr 29 21:07:43 1996 Date: Mon, 29 Apr 1996 09:12:05 EDT From: Tony Forbes To: Multiple recipients of list NMBRTHRY Subject: 2^5630 - 3 is prime 2^5630 - 3 is prime ------------------- Tony Forbes Motivated only by idle curiosity, I decided to collect together all known primes of the form (1) 2^n + m, with large n and small m, say 2^n > 10^999 and |m| <= 17. I started at the obvious place, Chris Caldwell's list of titanic primes. And when I searched the list I was quite surprised to discover that, apart from the Mersenne primes, there are no entries at all. This led me to believe that either there are no known primes (1) of 1000 digits or more (and |m| > 1), or nobody has got around to sending them in. It is easy enough to generate a list of probable primes, and this I have done for m = -3 and m = 3 with the help of a Dubner Cruncher: m = -3: n = 3954, 5630, 6756, 8770, 10572 (limit: 12000) m = 3: n = 4002, 4060, 4062, 4552, 5547, 8739 (limit: 12000) In the particular case N = 2^5630 - 3 I have been successful in factorizing sufficient of N - 1 = 4*(2^5628 - 1) to apply the Lehmer- Pocklington theorem [1, page 34] together with Ferrier's argument [2, page 123]. Just as Francois Morain [3] did, we make use of information provided by the Cunningham Project. Let Td = Phi_d(2) denote the d'th cyclotomic polynomial evaluated at 2. Then we have 2^k - 1 = prod_d|k Td. In our case k = 4*1407 = 4*3*7*67, and the factorizations we obtain are as follows. 2^1407 - 1 = T1 * T3 * T7 * T21 * T67 * T201 * T469 * T1407 T1 = 1 T3 = 7 T7 = 127 T21 = 7 * 337 T67 = 193707721 * 761838257287 T201 = 1609 * 22111 * 87449423397425857942678833145441 T469 = 70321958644800017 * 1839633098314450447 * P84 T1407 = 11257 * 14071 * 1005128735010289 * C216 2^1407 + 1 = T2 * T6 * T14 * T42 * T134 * T402 * T938 * T2814 T2 = 3 T6 = 3 T14 = 43 T42 = 5419 T134 = 7327657 * 6713103182899 T402 = 2011 * 9649 * 6324667 * 59151549118532676874448563 T938 = 408335956841 * 362312427317443674457 * 76207764956885795275897986139 * P59a T2814 = C239 2^2814 + 1 = T4 * T12 * T28 * T84 * T268 * T804 * T1876 * T5628 T4 = 5 T12 = 13 T28 = 113 * 29 T84 = 1429 * 14449 T268 = 269 * 42875177 * 2559066073 * 15152453 * 9739278030221 T804 = 3217 * 192961 * 214473433 * 71848008781 * 175132692529 * 10453 * 132661 * 15704900959651293774270521395753 T1876 = 8158354429 * 297829119706021674037 * 20507066557421100083923450 75817 * P59b * 1877 * P116 T5628 = 33769 * C473 P59a = 21305401445202124537563847733843096783112730151372946821753 P59b = 71480402861675621827588464800435686040398437348131862678029 P84 = 628683935022908831926019116410056880219316806841500141982334538 232031397827230330241 P116 = 486984951091469656263453076530789096390027788655916173747752025 59293242639821112066517085850802399245624362755906637 Except for the third factor of T1407, all the non-trivial prime factors are listed in the Cunningham tables. Writing F for the product of the known factors of N - 1, we have log_2(N) = 5630.000000000000, log_2(N)/2 = 2815.000000000000, log_2(F) = 2554.025928435933, log_2(N + 1 (mod F^2)) = 5107.309654281002, log_2(sqrt(N) + N/F) = 3075.974071564066, approximately. Since F > N^(1/3) and 5107 > 3076, the primality of N can be established. References ---------- [1] P. Ribenboim, *The Little Book of Big Primes*, Springer-Verlag, 1991 [2] H. Riesel, *Prime Numbers and Computer Methods for Factorization*, Birkhauser, Boston, 1994 [3] F. Morain, "(2^10501+1)/3 is prime", NMBRTHRY, April 1996 -- Tony Forbes