What modulus should be chosen when proving impossibility of $|2^m-3^n|=N$?

Question

In this question it was asked whether there exist integer solutions to the equation

$$|2^m-3^n|=35,$$

and I responded by saying that, modulo $85$, there do not exist any integer solutions to

$$2^m - 3^n \equiv \pm 35,$$

so there are no solutions to the equation itself. I'd originally seen a problem on a contest asking contestants to find the smallest prime that is not a value of $$|2^m-3^n|,$$

and it was solved by finding values for the primes $2,3,5,7,11,13,17,19,23,29,31,$ and $37$, and proving (via mod-bashing) that there does not exist a solution at $41$.

My question is: For every integer $k$, does there either exist integers $m,n$ such that

$$|2^m-3^n|=k,$$

or an integer $M$ such that

$$2^m-3^n \equiv \pm k \bmod M,$$

and if so, is there a simple way to find $M$ (assuming there don't exist $m,n$)?

I've attached a table that shows, for each $k\leq 100$, whether there exists a solution, and if not, what the smallest modulus that can be used is, in case it's useful to anyone. The sequence doesn't seem to exist on OEIS.

1 is a value of |2^m-3^n| .         2 is a value of |2^m-3^n| .         3 is a value of |2^m-3^n| .         4 is solved by the modulus 8.       5 is a value of |2^m-3^n| .
6 is solved by the modulus 12.      7 is a value of |2^m-3^n| .         8 is a value of |2^m-3^n| .         9 is solved by the modulus 15.      10 is solved by the modulus 20.
11 is a value of |2^m-3^n| .        12 is solved by the modulus 8.      13 is a value of |2^m-3^n| .        14 is solved by the modulus 18.     15 is a value of |2^m-3^n| .
16 is solved by the modulus 20.     17 is a value of |2^m-3^n| .        18 is solved by the modulus 12.     19 is a value of |2^m-3^n| .        20 is solved by the modulus 8.
21 is solved by the modulus 15.     22 is solved by the modulus 18.     23 is a value of |2^m-3^n| .        24 is solved by the modulus 15.     25 is a value of |2^m-3^n| .
26 is a value of |2^m-3^n| .        27 is solved by the modulus 33.     28 is solved by the modulus 8.      29 is a value of |2^m-3^n| .        30 is solved by the modulus 12.
31 is a value of |2^m-3^n| .        32 is solved by the modulus 18.     33 is solved by the modulus 21.     34 is solved by the modulus 22.     35 is solved by the modulus 85.
36 is solved by the modulus 8.      37 is a value of |2^m-3^n| .        38 is solved by the modulus 22.     39 is solved by the modulus 15.     40 is solved by the modulus 18.
41 is solved by the modulus 91.     42 is solved by the modulus 12.     43 is solved by the modulus 195.    44 is solved by the modulus 8.      45 is solved by the modulus 33.
46 is solved by the modulus 26.     47 is a value of |2^m-3^n| .        48 is solved by the modulus 18.     49 is a value of |2^m-3^n| .        50 is solved by the modulus 18.
51 is solved by the modulus 15.     52 is solved by the modulus 8.      53 is solved by the modulus 80.     54 is solved by the modulus 12.     55 is a value of |2^m-3^n| .
56 is solved by the modulus 20.     57 is solved by the modulus 48.     58 is solved by the modulus 18.     59 is solved by the modulus 240.    60 is solved by the modulus 8.
61 is a value of |2^m-3^n| .        62 is solved by the modulus 24.     63 is a value of |2^m-3^n| .        64 is solved by the modulus 20.     65 is a value of |2^m-3^n| .
66 is solved by the modulus 12.     67 is solved by the modulus 120.    68 is solved by the modulus 8.      69 is solved by the modulus 15.     70 is solved by the modulus 20.
71 is solved by the modulus 80.     72 is solved by the modulus 21.     73 is a value of |2^m-3^n| .        74 is solved by the modulus 26.     75 is solved by the modulus 21.
76 is solved by the modulus 8.      77 is a value of |2^m-3^n| .        78 is solved by the modulus 12.     79 is a value of |2^m-3^n| .        80 is a value of |2^m-3^n| .
81 is solved by the modulus 15.     82 is solved by the modulus 22.     83 is solved by the modulus 117.    84 is solved by the modulus 8.      85 is solved by the modulus 91.
86 is solved by the modulus 18.     87 is solved by the modulus 33.     88 is solved by the modulus 26.     89 is solved by the modulus 80.     90 is solved by the modulus 12.
91 is solved by the modulus 195.    92 is solved by the modulus 8.      93 is solved by the modulus 21.     94 is solved by the modulus 18.     95 is solved by the modulus 85.
96 is solved by the modulus 15.     97 is solved by the modulus 91.     98 is solved by the modulus 22.     99 is solved by the modulus 15.     100 is solved by the modulus 8.

Answer 1

This is now a partial answer - see last update at end

---

Third: did you observe in your table the arithmetic progressions for the cases $k$ which can be solved by a modulus $M$? for instance $k=4+8j$ are all deniably looking by modulus $M=8$ , $k=6+12j$ by modulus $M=12$, $k=9+j*15$ by modulus $M=15$ and as well seemingly $k=21+j*30$ by $M=15$. In the progressions of the $k$ on the same $M$ we find holes in your table. They might be explainable because they occur with smaller $M$ - it would be nice to see, whether that progressions $k=a_m+M$ with some first element $a_M$ are all deniable by that modulus $M$ - then your table needs only display the relations between $a_M$ and $M$ where we sometimes have multiple $a_{M,t}$ for the same $M$ I sorted your table this way:

 diff.k       nonexistence of difference k solved by M
 exists       k   M       k    M       k    M       k    M       k    M       k    M
 ----+--------------------------------------------------------------------------------
 1   !        4   8       6   12       9   15      14   18      10   20      33   21
 2   !       12   8      18   12      24   15      32   18      16   20      72   21
 3   !       20   8      30   12      39   15      40   18      56   20      75   21
 5   !       28   8      42   12                   58   18      64   20      93   21
 7   !       36   8      54   12      69   15                   70   20         
 8   !       44   8      66   12                   94   18                  
11   !       52   8      78   12      99   15                           
13   !       60   8      90   12                                    
15   !       68   8                                             
17   !       76   8                                             
19   !       84   8                   21   15      22   18                  
23   !       92   8                   51   15      50   18                  
25   !      100   8                   81   15      86   18                  
26   !                                96   15                           
29   !                                                      
31   !                                             48   18                  
37   !                                                      

Would your procedure, when updated, fill the obvious holes? Can we then have a compacted table?

4): A list of $k$'s which are disprovable by $M$'s (partly trivial, for instance for differences $k$ divisible by $2$ or $3$):

M   list of k : [nontrivial] [partly trivial]
----------------------------------------------------------
65 []   [0, 26]
73 [49] [0, 14, 20, 21, 22, 27, 30, 39, 42, 44, 49, 60, 70]
85 [17,19,35,49] [0, 4, 10, 17, 18, 19, 21, 33, 35, 46, 49, 50, 51, 56, 64, 75, 81]
91 [17,25,35] [0, 2, 4, 6, 8, 9, 16, 17, 21, 24, 25, 27, 35, 39, 40, 41, 44, 49, 50, 51, 52, 57, 58, 59, 60, 64, 69, 70, 75, 77, 78, 79, 81, 82, 85, 88]

We see, especially at $M=91$ a lot of trivial entries. Here is a list which omits the trivial entries (except the $0$ for reminding of not-explained cases $k$)

   M   [list of  nontrivial k disproved by M]
----------------------------------------------------------
   73 [0, 49]
   85 [0, 17, 19, 35, 49]
   91 [0, 17, 25, 35, 41, 49, 59, 77, 79, 85]
  133 [0, 95]
  143 [0, 77, 121]
  205 [0, 11, 19, 25, 35, 41, 43, 49, 53, 71, 77, 79, 85, 91, 97, 109, 113, 115, 121, 131, 133, 137, 139, 143, 149, 157, 161, 167, 173, 181, 185, 187, 191]
  217 [0, 151]
  247 [0, 19, 131, 133, 157, 173, 179, 181, 191, 209]
  259 [0, 79, 185, 193, 203, 217, 239]
  265 [0, 53]
  275 [0, 19, 25, 35, 49, 73, 95, 109, 157, 173, 179, 197, 205, 217, 221, 223, 227, 239, 241, 251]
  325 [0, 91, 221]
  341 [0, 19, 41, 43, 49, 53, 59, 65, 71, 73, 77, 79, 85, 107, 113, 121, 131, 137, 139, 145, 149, 155, 161, 163, 167, 169, 173, 185, 187, 191, 193, 199, 211, 217, 227, 233, 251, 271, 281, 283, 299, 313, 329, 331, 337]
  365 [0, 49, 95, 103, 107, 109, 115, 133, 143, 167, 173, 185, 191, 197, 217, 221, 223, 233, 239, 241, 263, 289, 313, 319, 331, 341]
  403 [0, 155]
  425 [0, 17, 19, 35, 49, 89, 95, 103, 131, 149, 187, 191, 203, 205, 221, 245, 251, 259, 265, 301, 305, 311, 319, 359, 361, 373, 389, 391, 415, 421]
  427 [0, 95]
  433 [0, 35, 79, 401]
  445 [0, 89]
  451 [0, 25, 43, 59, 79, 109, 131, 155, 161, 167, 185, 197, 203, 275, 277, 307, 395, 419, 433]
  455 [0, 11, 17, 19, 25, 35, 41, 43, 49, 53, 59, 67, 71, 73, 77, 79, 83, 85, 91, 95, 97, 107, 115, 121, 131, 137, 139, 143, 149, 151, 155, 157, 161, 163, 167, 169, 173, 179, 181, 187, 191, 193, 199, 203, 205, 209, 211, 217, 221, 223, 233, 235, 239, 241, 251, 257, 259, 263, 271, 275, 277, 281, 283, 287, 289, 293, 299, 301, 313, 317, 323, 325, 331, 337, 343, 347, 349, 355, 359, 361, 365, 371, 373, 377, 379, 383, 385, 389, 391, 395, 397, 403, 407, 413, 415, 419, 421, 425, 427, 433, 439, 443, 445, 449]
  481 [0, 11, 19, 25, 41, 67, 71, 73, 77, 85, 89, 107, 131, 137, 139, 151, 163, 179, 185, 197, 199, 209, 211, 227, 251, 257, 259, 275, 299, 307, 313, 319, 323, 325, 329, 331, 337, 365, 367, 371, 377, 379, 383, 397, 403, 407, 419, 427, 437, 445, 461]
  485 [0, 97]
  493 [0, 145]

A combined list of all nontrivial $k$ which could be denied by $M \equiv \pm1 \pmod 6)$ below $999$:

  [11, 17, 19, 25, 35, 49, 53, 71, 77, 79, 89, 91, 95, 97,
   103, 107, 137, 139, 145, 149, 151, 155, 173, 181, 197,
   203, 209, 259,
   335, 377, 395, 
   413, 487,
   689]

update: 5: This becomes now at least a partial answer (I still do not have a generating formula for the optimal modulus $M$ which would be a full answer).

Here is a list for $k$ and the $M<500$ which detect that $k$ cannot be obtained by $|2^m-3^n|=k$ by missing residuals $\pmod M$. Note that $k\not \equiv \pm1 \pmod6$ are trivially no possible differences!
A longer list shows, that $M=511$ is a somehow optimal modulus to disproof small nontrivial differences. Up to k=109 : if any $M$ disproofs that difference, then $M=511$ disproofs this difference as well. The next powerful detector seems to be $M=341$.

   k   : list of detecting M<500
  -----+------------------------------
   11  :   91  205    .    .    .    .
   17  :   85   91    .    .    .    .
   19  :   85  205  247  275  341    .
   25  :   91  205  275    .    .    .
   31  :   91  205  247    .    .    .
   35  :   85   91  205  275    .    .
   41  :   91  205  341    .    .    .
   43  :  205  341    .    .    .    .
   49  :   73   85   91  205  275  341
   53  :  205  265  341    .    .    .
   59  :   85   91  341    .    .    .
   65  :  341    .    .    .    .    .
   67  :   85    .    .    .    .    .
   71  :   73  205  259  341    .    .
   73  :   91  275  341    .    .    .
   77  :   91  143  205  341    .    .
   79  :   91  205  259  341    .    .
   83  :   85   91    .    .    .    .
   85  :   91  205  275  341    .    .
   89  :   91    .    .    .    .    .
   91  :  205  325    .    .    .    .
   95  :  133  275    .    .    .    .
   97  :  205  275    .    .    .    .
  107  :  341    .    .    .    .    .
  109  :  205  275    .    .    .    .
  113  :  205  275  341    .    .    .
  115  :  205    .    .    .    .    .
  121  :  143  205  341    .    .    .
  127  :  217  275    .    .    .    .
  131  :  205  247  341    .    .    .
  133  :  205  247    .    .    .    .
  137  :  205  341    .    .    .    .
  139  :  205  341    .    .    .    .
  143  :  205    .    .    .    .    .
  145  :  341    .    .    .    .    .
  149  :  205  341    .    .    .    .
  151  :  217    .    .    .    .    .
  155  :  341    .    .    .    .    .
  157  :  205  247  275    .    .    .
  161  :  205  341    .    .    .    .
  163  :  341    .    .    .    .    .
  167  :  205  341    .    .    .    .
  169  :  341    .    .    .    .    .
  173  :  205  247  275  341    .    .
  179  :  205  247  275  341    .    .
  181  :  205  247    .    .    .    .
  185  :  205  259  341    .    .    .
  187  :  205  341    .    .    .    .
  191  :  205  247  341    .    .    .
  193  :  259  341    .    .    .    .
  197  :  205  275    .    .    .    .
  199  :  341    .    .    .    .    .
  203  :  205  259    .    .    .    .
  205  :  275    .    .    .    .    .
  209  :  247    .    .    .    .    .
  211  :  341    .    .    .    .    .
  217  :  259  275  341    .    .    .
  221  :  275  325    .    .    .    .
  223  :  275    .    .    .    .    .
  227  :  275  341    .    .    .    .
  233  :  341    .    .    .    .    .
  239  :  259  275    .    .    .    .
  241  :  275    .    .    .    .    .
  251  :  275  341    .    .    .    .
  271  :  341    .    .    .    .    .
  281  :  341    .    .    .    .    .
  283  :  341    .    .    .    .    .
  295  :  341    .    .    .    .    .
  299  :  341    .    .    .    .    .
  313  :  341    .    .    .    .    .
  329  :  341    .    .    .    .    .
  331  :  341    .    .    .    .    .
  337  :  341    .    .    .    .    .