5 votos

¿Qué módulo se debe elegir al demostrar la imposibilidad de $|2^m-3^n|=N$?

En esta pregunta se preguntaba si existen soluciones enteras para la ecuación

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

y respondí diciendo que, módulo $85$, no existen soluciones enteras para

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

por lo que no hay soluciones para la ecuación en sí. Originalmente vi un problema en un concurso que pedía a los concursantes encontrar el primo más pequeño que no es un valor de $$|2^m-3^n|,$

y se resolvió encontrando valores para los primos $2,3,5,7,11,13,17,19,23,29,31,$ y $37$, y demostrando (vía mod-bashing) que no existe una solución en $41$.

Mi pregunta es: Para cada entero $k$, ¿existen enteros $m,n$ tal que

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

o un entero $M$ tal que

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

y de ser así, ¿existe una manera simple de encontrar $M$ (asumiendo que no existen $m,n$)?

He adjuntado una tabla que muestra, para cada $k\leq 100$, si existe una solución, y si no, cuál es el módulo más pequeño que se puede utilizar, en caso de que sea útil para alguien. La secuencia no parece existir en OEIS.

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

0 votos

Por favor, vea un comentario demasiado largo para este campo en un "cuadro de respuesta"

2voto

Jorrit Reedijk Puntos 129

Esta es ahora una respuesta parcial - ver la última actualización al final


Tercero ¿Han observado en su tabla las progresiones aritméticas para los casos $k$ que puede resolverse mediante un módulo $M$ ? por ejemplo $k=4+8j$ son todos denegables mirando por el módulo $M=8$ , $k=6+12j$ por módulo $M=12$ , $k=9+j*15$ por módulo $M=15$ y también aparentemente $k=21+j*30$ por $M=15$ . En las progresiones del $k$ en el mismo $M$ encontramos agujeros en su mesa. Podrían ser explicables porque se producen con menor $M$ - sería bueno ver, si esa progresión $k=a_m+M$ con algún primer elemento $a_M$ son todos negables por ese módulo $M$ - entonces su tabla sólo necesita mostrar las relaciones entre $a_M$ y $M$ donde a veces tenemos múltiples $a_{M,t}$ para el mismo $M$ He ordenado tu tabla de esta manera:

 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   !                                                      

¿Su procedimiento, cuando se actualice, cubrirá las lagunas evidentes? ¿Podemos entonces tener una tabla compactada?

4) : Una lista de $k$ que son refutables por $M$ (en parte trivial, por ejemplo para las diferencias $k$ divisible por $2$ o $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]

Vemos, especialmente en $M=91$ un montón de entradas triviales. Aquí hay una lista que omite las entradas triviales (excepto el $0$ para recordar los casos no explicados $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]

Una lista combinada de todos los $k$ que podría ser denegada por $M \equiv \pm1 \pmod 6)$ debajo de $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]

actualización : 5: Esto se convierte ahora en una respuesta al menos parcial (todavía no tengo una fórmula generadora para el módulo óptimo $M$ que sería una respuesta completa).

Esta es una lista para $k$ y el $M<500$ que detectan que $k$ no se puede obtener por $|2^m-3^n|=k$ por los residuos que faltan $\pmod M$ . Tenga en cuenta que $k\not \equiv \pm1 \pmod6$ ¡no son trivialmente posibles diferencias!
Una lista más larga muestra que $M=511$ es un módulo de alguna manera óptimo para refutar pequeñas diferencias no triviales. Hasta k=109 : si hay $M$ refuta esa diferencia, entonces $M=511$ también refuta esta diferencia. El siguiente detector potente parece ser $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    .    .    .    .    .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X