# Does the equation $241+2^{2s+1}=m^2$ have a solution?

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}\ \ \ ?$$

• 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$. – Noam D. Elkies Sep 27 '15 at 23:09
• 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. – Mike Bennett Sep 27 '15 at 23:36
• If anyone is wondering, the argument Mike Bennett refers to is worked out in math.dartmouth.edu/~carlp/2tokmmminus1v8.pdf . See Theorem 1. – so-called friend Don Sep 28 '15 at 3:12
• @MikeBennett : Thanks, indeed, Ridout's theorem (together with the PNT for primes in an arithmetic progression) makes the job for Q2. – few_reps Sep 28 '15 at 7:27

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.

• Thanks ! How did you think to 63 ? Will's answer below seems to indicate that obstructions are to be found mod $2^{2t}-1$ ... – few_reps Sep 28 '15 at 7:12
• 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. – RP_ Sep 28 '15 at 19:32

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

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

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

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.$

• 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 ... – few_reps Sep 28 '15 at 7:19
• @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. – Will Jagy Sep 28 '15 at 18:31
• @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.$ – Will Jagy Sep 29 '15 at 20:13
• 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 ... – few_reps Sep 30 '15 at 14:57