17
$\begingroup$

Let $p$ be a prime congruent to $1$ mod. 8.

If $p= 17$ one has : $p+ 8 = 5 ^2$.

If $p= 41$ one has : $p+ 8 = 7 ^2$.

If $p= 73$ one has : $p+ 8 = 9 ^2$.

If $p= 89$ one has : $p+ 32 = 11 ^2$.

If $p= 97$ one has : $p+ 128 = 15 ^2$.

If $p= 113$ one has : $p+ 8 = 11 ^2$.

If $p= 137$ one has : $p+ 32 = 13 ^2$.

If $p= 193$ one has : $p+ 32 = 15 ^2$.

If $p= 233$ one has : $p+ 128 = 19 ^2$.

For $p=241$, there is no value $s\leq 4000$ for which $p+2^{2s+1}$ is a square.

Question 1 : Is there a simple way to prove that no such $s$ can exist ?

Question 2 : Can one estimate the density of those primes $p\equiv 1$ mod. 8 that can be written under the form $$p=m^2-2^{2s+1}\ \ \ ?$$

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Q2: the density is surely zero; I guess that a proof is within reach but possibly not easy. Stefan Kohl's argument (together with Dirichlet's theorem) shows that at any rate the upper density is less than $1$. $\endgroup$
    – Noam D. Elkies
    Commented Sep 27, 2015 at 23:09
  • 10
    $\begingroup$ By Ridout's theorem ( a $p$-adic version of Roth's theorem), the number of integers (prime or otherwise) of the shape $|m^2-2^{2s+1}|$ up to $x$ is $\ll x^{1/2+\epsilon}$, so one gets zero density among the primes. $\endgroup$
    – Mike Bennett
    Commented Sep 27, 2015 at 23:36
  • 3
    $\begingroup$ If anyone is wondering, the argument Mike Bennett refers to is worked out in math.dartmouth.edu/~carlp/2tokmmminus1v8.pdf . See Theorem 1. $\endgroup$
    – so-called friend Don
    Commented Sep 28, 2015 at 3:12
  • $\begingroup$ @MikeBennett : Thanks, indeed, Ridout's theorem (together with the PNT for primes in an arithmetic progression) makes the job for Q2. $\endgroup$
    – few_reps
    Commented Sep 28, 2015 at 7:27

2 Answers 2

Reset to default
38
$\begingroup$

To answer your first question: there is indeed no $s$ such that $241+2^{2s+1}$ is a perfect square. -- Proof: $2^{2s+1}$ is always congruent to either $2$, $8$ or $32$ modulo $63$, which makes $241+2^{2s+1}$ congruent to either $21$, $54$ or $60$ modulo $63$. However none of these values is a quadratic residue modulo $63$, and thus $241+2^{2s+1}$ cannot be a perfect square, as claimed.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks ! How did you think to 63 ? Will's answer below seems to indicate that obstructions are to be found mod $2^{2t}-1$ ... $\endgroup$
    – few_reps
    Commented Sep 28, 2015 at 7:12
  • 3
    $\begingroup$ If you're looking for a congruence argument, then numbers of the form $M=2^{2n}-1$ are a smart choice of modulus, because we expect $241+2^{2s+1}$ to take only about $n$ distinct residue classes modulo $M$. So with that idea in hand, I guess you could do a computer search that runs through some small $n$ and checks which one gives an $M$ that does the job. $\endgroup$
    – R.P.
    Commented Sep 28, 2015 at 19:32
5
$\begingroup$

I was able to allow the power of $2$ to go up to $2^{29} = 536870912,$ no higher....

Stefan's argument works word for word for $p=337.$

For $p=569,$ we need to expand to numbers $\pmod{255},$ where odd powers of $2$ are $2,8,32,128,$ $569 \equiv 59 \pmod {255},$ and $569 + 2^{\mbox{odd}} \equiv 61,67,91,187 \pmod {255},$ while the quadratic residues are

   0       1       4       9      15      16      19      21      25      30
  34      36      49      51      55      60      64      66      69      70
  76      81      84      85      94     100     106     111     115     120
 121     135     136     144     145     151     154     166     169     171
 174     186     189     195     196     204     205     219     220     225
 229     234     240     246




      17          8         25      5
      41          8         49      7
      73          8         81      9
      89         32        121     11
      97        128        225     15
     113          8        121     11
     137         32        169     13
     193         32        225     15
     233        128        361     19
     241     FAIL  
     257         32        289     17
     281          8        289     17
     313        128        441     21
     337     FAIL  
     353          8        361     19
     401        128        529     23
     409         32        441     21
     433          8        441     21
     449        512        961     31
     457       8192       8649     93
     521          8        529     23
     569     FAIL  
     577        512       1089     33
     593         32        625     25
     601        128        729     27
     617          8        625     25
     641     FAIL  
     673     FAIL  
     761       2048       2809     53
     769     FAIL  
     809         32        841     29
     857        512       1369     37
     881     FAIL  
     929         32        961     31
     937     FAIL  
     953          8        961     31
     977       2048       3025     55
    1009        512       1521     39
    1033     FAIL  
    1049     FAIL  
    1097        128       1225     35
    1129     FAIL  
    1153     FAIL  
    1193         32       1225     35
    1201       2048       3249     57
    1217          8       1225     35
    1249     FAIL  
    1289     FAIL  
    1297     FAIL  
    1321     FAIL  
    1361          8       1369     37
    1409     FAIL  
    1433       2048       3481     59
    1481     FAIL  
    1489         32       1521     39
    1553        128       1681     41
    1601     FAIL  
    1609       8192       9801     99
    1657     FAIL  
    1697        512       2209     47
    1721        128       1849     43
    1753     FAIL  
    1777     FAIL  
    1801     FAIL  
    1873     FAIL  
    1889        512       2401     49
    1913     FAIL  
    1993         32       2025     45
    2017          8       2025     45
    2081        128       2209     47
    2089        512       2601     51
    2113     FAIL  
    2129     FAIL  
    2137     FAIL  
    2153     131072     133225    365
    2161     FAIL  
    2273        128       2401     49
    2281     FAIL  
    2297        512       2809     53
    2377     FAIL  
    2393          8       2401     49
    2417       8192      10609    103
    2441       2048       4489     67
    2473        128       2601     51
    2521     FAIL  
    2593          8       2601     51
    2609     FAIL  
    2617     FAIL  
    2633     FAIL  
    2657     FAIL  
    2689     FAIL  
    2713       2048       4761     69
    2729     FAIL  
    2753     FAIL  
    2777         32       2809     53
    2801          8       2809     53
    2833       8192      11025    105
    2857     FAIL  
    2897        128       3025     55
    2953      32768      35721    189
    2969        512       3481     59
    3001     FAIL  
    3041     FAIL  
    3049     FAIL  
    3089     FAIL  
    3121        128       3249     57
    3137     FAIL  
    3169     FAIL  
    3209        512       3721     61
    3217         32       3249     57
    3257       8192      11449    107
    3313     FAIL  
    3329     FAIL  
    3361     FAIL  
    3433     FAIL  
    3449         32       3481     59
    3457        512       3969     63
    3529     FAIL  
    3593        128       3721     61
    3617     131072     134689    367
    3673     FAIL  
    3697     FAIL  
    3761     FAIL  
    3769     FAIL  
    3793     FAIL  
    3833     FAIL  
    3881       2048       5929     77
    3889     FAIL  
    3929     FAIL  
    4001    8388608    8392609   2897
    4049     FAIL  
    4057     FAIL  
    4073     FAIL  
    4129       8192      12321    111
    4153     FAIL  
    4177     FAIL  
    4201     FAIL  
    4217          8       4225     65
    4241     524288     528529    727
    4273     FAIL  
    4289     FAIL  
    4297     FAIL  
    4337     FAIL  
    4409     FAIL  
    4441     FAIL  
    4457         32       4489     67
    4481          8       4489     67
    4513       2048       6561     81
    4561     FAIL  
    4649     FAIL  
    4657     FAIL  
    4673     FAIL  
    4721     FAIL  
    4729         32       4761     69
    4793     FAIL  
    4801     FAIL  
    4817        512       5329     73
    4889     FAIL  
    4937     FAIL  
    4969     FAIL  
    4993     FAIL  
    5009         32       5041     71
    5081     FAIL  
    5113        512       5625     75
    5153     FAIL  
    5209     FAIL  
    5233     FAIL  
    5273     FAIL  
    5281     FAIL  
    5297         32       5329     73
    5393     FAIL  
    5417        512       5929     77
    5441     FAIL  
    5449     FAIL  
    5521       2048       7569     87
    5569     FAIL  
    5641     FAIL  
    5657     FAIL  
    5689     FAIL  
    5737     FAIL  
    5801        128       5929     77
    5849     FAIL  
    5857     FAIL  
    5881     FAIL  
    5897         32       5929     77
    5953     FAIL  
    6073     FAIL  
    6089     FAIL  
    6113        128       6241     79
    6121     FAIL  
    6217     FAIL  
    6257     FAIL  
    6329     FAIL  
    6337     FAIL  
    6353     FAIL  
    6361     FAIL  
    6449       8192      14641    121
    6473     FAIL  
    6481     FAIL  
    6521     FAIL  
    6529         32       6561     81
    6553          8       6561     81
    6569     131072     137641    371
    6577     FAIL  
    6673     FAIL  
    6689     FAIL  
    6737     FAIL  
    6761        128       6889     83
    6793     FAIL  
    6833      32768      39601    199
    6841     FAIL  
    6857         32       6889     83
    6961     FAIL  
    6977       2048       9025     95
    7001     FAIL  
    7057        512       7569     87
    7121     FAIL  
    7129     FAIL  
    7177     FAIL  
    7193         32       7225     85
    7297     FAIL  
    7321     FAIL  
    7369     FAIL  
    7393     FAIL  
    7417     FAIL  
    7433       8192      15625    125
    7457     FAIL  
    7481     FAIL  
    7489     FAIL  
    7529     FAIL  
    7537         32       7569     87
    7561          8       7569     87
    7577     FAIL  
    7649     FAIL  
    7673     FAIL  
    7681     FAIL  
    7753       2048       9801     99
    7793        128       7921     89
    7817     FAIL  
    7841     FAIL  
    7873     FAIL  
    7937       8192      16129    127
    7993     FAIL  
    8009     FAIL  
    8017     FAIL  
    8081     FAIL  
    8089     FAIL  
    8161     FAIL  
    8209     FAIL  
    8233     FAIL  
    8273          8       8281     91
    8297     FAIL  
    8329     FAIL  
    8353     FAIL  
    8369     FAIL  
    8377     FAIL  
    8513        512       9025     95
    8521        128       8649     93
    8537     FAIL  
    8609     FAIL  
    8641          8       8649     93
    8681     FAIL  
    8689     FAIL  
    8713     FAIL  
    8737     FAIL  
    8753     FAIL  
    8761     FAIL  
    8849     FAIL  
    8929     FAIL  
    8969       8192      17161    131
    9001     FAIL  
    9041     FAIL  
    9049     FAIL  
    9137     FAIL  
    9161     FAIL  
    9209     FAIL  
    9241     FAIL  
    9257      32768      42025    205
    9281        128       9409     97
    9337     FAIL  
    9377         32       9409     97
    9433     FAIL  
    9473     FAIL  
    9497       8192      17689    133
    9521     FAIL  
    9601     FAIL  
    9649     FAIL  
    9689        512      10201    101
    9697     FAIL  
    9721     FAIL  
    9769         32       9801     99
    9817     FAIL  
    9833       2048      11881    109
    9857     FAIL  
    9929     FAIL  
   10009     FAIL  
   10169         32      10201    101
   10177     FAIL  
   10193          8      10201    101
   10273       2048      12321    111
   10289     FAIL  
   10313     FAIL  
   10321     FAIL  
   10337     FAIL  
   10369     FAIL  
   10433     FAIL  
   10457     FAIL

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

I told it to just print the values $\pmod {4^t - 1}$ that could not be expressed in the prescribed manner. The first few primes that say "FAIL" can be proved to fail in Stefan's manner, as $241 \equiv 52 \pmod {63},$ $337 \equiv 22 \pmod {63},$ $569 \equiv 59 \pmod {255},$ $641 \equiv 641 \pmod {1023},$ $673 \equiv 43 \pmod {63}.$

Bad mod 15
       0       3       5       6       9      10      12


 Bad mod 63
       0       3       6       9      12      13      15      18      19      21
      22      24      25      27      30      33      36      37      39      42
      43      45      46      48      51      52      54      57      58      60


 Bad mod 255
       0       3       5       6       9      10      12      15      18      20
      21      24      25      27      29      30      31      33      35      36
      39      40      42      45      48      50      51      54      55      57
      59      60      63      65      66      69      70      71      72      75
      78      80      81      84      85      87      90      93      94      95
      96      99     100     102     105     108     110     111     114     115
     116     117     120     121     123     124     125     126     129     130
     132     135     138     140     141     144     145     147     150     151
     153     155     156     159     160     162     165     168     170     171
     174     175     177     179     180     183     185     186     189     190
     192     195     198     199     200     201     204     205     206     207
     209     210     213     215     216     219     220     222     225     228
     229     230     231     234     235     236     237     240     241     243
     245     246     249     250     252



 Bad mod 1023
       0       3       6       9      10      11      12      15      18      21
      22      24      26      27      30      33      36      39      40      42
      44      45      48      51      54      55      57      60      63      66
      69      72      75      77      78      81      83      84      87      88
      90      93      96      99     102     104     105     106     108     110
     111     114     117     120     121     123     126     129     132     135
     138     141     143     144     147     150     153     154     156     159
     160     162     165     168     171     173     174     176     177     180
     181     183     186     187     189     192     195     197     198     201
     204     205     207     209     210     211     213     216     219     220
     222     225     228     231     234     237     240     242     243     246
     249     252     253     255     258     261     264     267     270     273
     275     276     279     282     285     286     288     291     294     297
     299     300     301     303     305     306     307     308     309     312
     315     318     319     321     324     327     330     331     332     333
     336     339     341     342     345     348     351     352     354     357
     360     362     363     366     367     369     372     374     375     378
     381     383     384     385     387     390     393     396     399     402
     405     407     408     411     414     416     417     418     420     423
     424     425     426     429     432     435     438     440     441     444
     445     447     450     451     453     456     459     462     465     468
     471     473     474     477     479     480     483     484     486     489
     492     495     498     501     503     504     506     507     509     510
     513     514     516     517     518     519     522     525     528     531
     534     537     538     539     540     543     546     549     550     552
     555     558     561     564     567     570     572     573     576     579
     582     583     585     588     591     594     597     600     602     603
     605     606     609     612     615     616     618     621     624     627
     630     633     636     638     639     640     641     642     645     646
     648     649     651     654     657     660     662     663     666     669
     671     672     673     675     677     678     681     682     684     687
     690     692     693     696     699     702     703     704     705     708
     711     714     715     717     720     722     723     724     726     729
     732     735     737     738     741     744     747     748     750     753
     756     757     759     762     765     766     768     770     771     774
     777     780     781     783     786     788     789     792     795     798
     801     803     804     807     810     813     814     816     819     820
     822     825     828     831     834     836     837     840     842     843
     844     846     847     849     850     852     855     858     859     861
     863     864     867     869     870     873     876     879     880     882
     885     887     888     891     893     894     897     900     902     903
     906     909     912     913     915     918     921     924     927     930
     933     935     936     939     942     943     945     946     948     951
     954     957     960     963     966     968     969     972     975     978
     979     981     982     983     984     987     989     990     993     996
     999    1001    1002    1003    1005    1008    1011    1012    1013    1014
    1017    1018    1020

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

I could have saved some of the printing just above. The original question was about primes in any case, so any of the numbers such as $3,5 \pmod {15}$ are not useful for the original problem. At the same time, expanding to all integer values, we are asking when $n = m^2 - 2 \cdot 4^k = m^2 - 2 w^2$ where $w$ is a power of $2.$ That is, such $w$ is not divisible by any odd prime. By a simple argument involving Legendre symbol $(2 |q),$ we find that such $n$ cannot be divisible by $3,5,11,13, $ or by any prime $q$ with $(2 |q)= -1.$ That is, such $n$ cannot be divisible by $3,5,11,13, $ or by any prime $q$ with $ q \equiv 3,5 \pmod 8.$

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thank you ... Magma didn't seem to have any objection to compute with higher powers of 2, but probably for small enough primes the non-existence of a solution with $2s+1\leq 29$ is already a enough evidence to begin to search for a local obstruction ... $\endgroup$
    – few_reps
    Commented Sep 28, 2015 at 7:19
  • 2
    $\begingroup$ @few_reps, right. I added in a final section, for each $4^t - 1 \leq 1023$ the numbers that are bad modulo that, therefore giving some instant proofs using Stefan's idea. $\endgroup$
    – Will Jagy
    Commented Sep 28, 2015 at 18:31
  • $\begingroup$ @few_reps, minor note at the end, if you expanded your target numbers from primes to all (odd) integers $n,$ these can not be divisible by any prime $q \equiv 3,5 \pmod 8.$ $\endgroup$
    – Will Jagy
    Commented Sep 29, 2015 at 20:13
  • $\begingroup$ Indeed ! Now I'm wondering ... does there exist infinitely many primes $p$ of the form $(2m+1)^2-2^{2s+1}$ ... ? Well there is this conjecture saying that already with $s=1$ it should be true, but maybe allowing $s$ to take other values makes things easier ... $\endgroup$
    – few_reps
    Commented Sep 30, 2015 at 14:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .