Solución elemental de la ecuación Diofántica exponencial $2^x - 3^y = 7$.

Question

El título lo dice todo. Me gustaría tener una solución, preferiblemente una que sea lo más elemental posible, de la ecuación diofántica exponencial $$ 2^x - 3^y = 7 $$ donde $x, y$ son enteros no negativos. Tenga en cuenta que algunas soluciones pequeñas son $(x, y) = (3, 0)$ y $(x, y) = (4, 2)$. Si realmente tuviera que resolverlo a toda costa, traduciría esto al problema de encontrar puntos enteros en un montón de curvas de género $1$. Sin embargo, me gustaría saber si hay algún método más simple por ahí.

Por lo que puedo ver, trucos de congruencia simples no funcionarán: $2^x = 7$ es soluble $3$-ádicamente y $-3^y = 7$ es soluble $2$-ádicamente, así que no veo cómo podríamos obtener algo buscando $p$-ádicamente para $p = 2$ o $p = 3$, y creo que el hecho de que el conjunto de soluciones al problema original no esté vacío significa que las consideraciones $p$-ádicas para $p \neq 2,3$ tampoco tienen posibilidades de funcionar. (Pero tal vez estoy equivocado.)

Answer 1

Al observar la ecuación módulo $3$, tenemos que $2^x \equiv 1 \pmod{3}$ a menos que $y = 0$, por lo tanto, $x$ es par. Por otro lado, módulo $7$ tenemos $2^x \equiv 3^y \pmod{7}$, y como $2 \equiv 3^2 \pmod{7}$ y $3$ es una raíz primitiva módulo $7$, esto implica que $2x - y$ es divisible por $6$, por lo tanto, $y$ también es par. Escribiendo $x = 2m$ y $y = 2n$, encontramos

$$2^{2m} - 3^{2n} = (2^m - 3^n)(2^m + 3^n) = 7$$

Ahora, utilizamos la primalidad de $7$, y se ve fácilmente que la única solución es $m = 2, n = 1$. Si $y = 0$, entonces obviamente $x = 3$, por lo tanto, las únicas soluciones son $(4, 2)$ y $(3, 0)$.

Answer 2

Comparar Ecuación diofántica exponencial $7^y + 2 = 3^x$ respondida por @Gyumin Roh

Inventé un problema variante en los comentarios. Parece que este método, publicado por un estudiante de secundaria coreano, permite tales variaciones. $$ 2^u - 3^v = 5 $$ Vemos que $8-3=5$ y $32-27 = 5.$ No avancé mucho trabajando alrededor de la solución $8-3,$ pero $32 - 27$ fue productivo. Tuve que usar un número primo grande, donde encontrar los órdenes de $2,3 \pmod p$ sería prohibitivo hacerlo a mano. Sin embargo, estos se pueden verificar. Tal vez pueda encontrar una cadena de primos más pequeña. En esta primera versión, usé $41, 31, 4561, 17.

\=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

PRIMERA VERSIÓN:

$$ 2^u = 3^v+5 $$ $$ 2^u - 32 = 3^v - 27 $$ Aparentemente lo cambié de dirección. $$ 3^v - 27 = 2^u - 32. $$ Con $v \geq 4$ y $u \geq 6,$ $$ 27 ( 3^x - 1) = 32 ( 2^y - 1)$$ con $x,y \geq 1,$ para que $3^x - 1 > 0$ y $2^y - 1 > 0.$ Lo que queremos hacer es mostrar que $3^x - 1$ es divisible por $64,$ porque eso contradecirá la factorización dada $32 \cdot \mbox{IMPAR}.$ A su vez, esto contradirá la existencia de tal solución adicional más allá de las que conocíamos.

Allá vamos, $$ 3^x \equiv 1 \pmod{32}. $$ Esto significa que $8 | x.$ Factorizamos, con la esperanza de encontrar nuevos primos útiles. $$ 3^8 - 1 = 32 \cdot 5 \cdot 41. $$ Usamos $41.$ Nota que $8|x,$ así que $(3^8 - 1)| (3^x - 1)$ y entonces $41 | (3^x - 1).$ Por lo tanto $41 |(2^y - 1).

$$ 2^y \equiv 1 \pmod{41}. $$ Esto significa que $20 | y.$$ Factorizamos, con la esperanza de encontrar nuevos primos útiles. $$ 2^{20} - 1 = 3 \cdot 5^2 \cdot 11 \cdot 31 \cdot 41. $$ Usamos $31$ ahora, con $31 |(3^x - 1).

$$ 3^x \equiv 1 \pmod{31}. $$ Esto significa que $30 | x.$ Factorizamos, con la esperanza de encontrar nuevos primos útiles. $$ 3^{30} - 1 = 8 \cdot 7 \cdot 11^2 \cdot 13 \cdot 31 \cdot 61 \cdot 271 \cdot 4561. $$ Usamos $4561.$$ Obtenemos $4561 |(2^y - 1).$ Lo siento por eso. Buscaré una cadena de primos más pequeña más tarde.

$$ 2^y \equiv 1 \pmod{4561}. $$ Esto significa que $2280 | y,$ en particular $8|y.$ $$ 2^{8} - 1 = 3 \cdot 5 \cdot 17 . $$ Usamos $17$ ahora. Por lo tanto $17 |(3^x - 1).

$$ 3^x \equiv 1 \pmod{17}. $$ Esto significa que $16 | x.$ $$ 3^{16} - 1 = 64 \cdot 5 \cdot 17 \cdot 41 \cdot 193 . $$

Como dije, $64 | (3^{16} - 1)| (3^x-1)$ contradice $ 27 ( 3^x - 1) = 32 ( 2^y - 1)$ con $3^x - 1 > 0$ y $2^y - 1 > 0.

\=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

SEGUNDA VERSIÓN: Usé $41, 31, 241, 17.

$$ 27 ( 3^x - 1) = 32 ( 2^y - 1)$$ con $x,y \geq 1,$ para que $3^x - 1 > 0$ y $2^y - 1 > 0.$ Lo que queremos hacer es mostrar que $3^x - 1$ es divisible por $64,$ porque eso contradecirá la factorización dada $32 \cdot \mbox{IMPAR}.$ A su vez, esto contradirá la existencia de tal solución adicional más allá de las que conocíamos.

Allá vamos, $$ 3^x \equiv 1 \pmod{32}. $$ Esto significa que $8 | x.$ Factorizamos, con la esperanza de encontrar nuevos primos útiles. $$ 3^8 - 1 = 32 \cdot 5 \cdot 41. $$ Usamos $41.$ Nota que $8|x,$ así que $(3^8 - 1)| (3^x - 1)$ y entonces $41 | (3^x - 1).$ Por lo tanto $41 |(2^y - 1).

$$ 2^y \equiv 1 \pmod{41}. $$ Esto significa que $20 | y.$$ Factorizamos, con la esperanza de encontrar nuevos primos útiles. $$ 2^{20} - 1 = 3 \cdot 5^2 \cdot 11 \cdot 31 \cdot 41. $$ Usamos $31$ ahora, con $31 |(3^x - 1).

$$ 3^x \equiv 1 \pmod{31}. $$ Esto significa que $30 | x.$ Sin embargo, ya sabíamos que $8 | x,$ así que $120|x.$ Factorizamos, con la esperanza de encontrar nuevos primos útiles. $$ 3^{120} - 1 = 32 \cdot 5^2 \cdot 7 \cdot 11^2 \cdot 13 \cdot 31 \cdot 41 \cdot 61 \cdot 241 \cdot 271 \cdot 1181 \cdot 4561 \cdot 6481 \cdot \mbox{CUATRO GRANDES}. $$ Usamos $241.$ Obtenemos $241 |(2^y - 1).$ Verifiqué dónde ocurre, 241 es el menor factor primo de $3^{40} - 3^{20} + 1.$ Nota que $( t^{40} - t^{20} + 1) =(t^8 - t^4 + 1)(t^{32} + t^{28} - t^{20} - t^{16} - t^{12} + t^4 + 1)$ era predecible basado en las raíces cúbicas complejas del $-1,$ sin embargo $241$ divide al factor polinómico menos agradable, en contexto $3^{32} + 3^{28} - 3^{20} - 3^{16} - 3^{12} + 3^4 + 1= 241 \cdot 298801 \cdot 26050081.$ Conclusión.

$$ 2^y \equiv 1 \pmod{241}. $$ Esto significa que $24 | y,$ en particular $8|y.$$ $$ 2^{8} - 1 = 3 \cdot 5 \cdot 17 . $$ Usamos $17$ ahora. Por lo tanto $17 |(3^x - 1).

$$ 3^x \equiv 1 \pmod{17}. $$ Esto significa que $16 | x.$ $$ 3^{16} - 1 = 64 \cdot 5 \cdot 17 \cdot 41 \cdot 193 . $$

Como dije, $64 | (3^{16} - 1)| (3^x-1)$ contradice $ 27 ( 3^x - 1) = 32 ( 2^y - 1)$ con $3^x - 1 > 0$ y $2^y - 1 > 0.

Answer 3

Martes, 27 de septiembre

Mejorando en esto. Descubrí que gp-pari estaba tardando demasiado. Escribí tres programas sencillos en C++. Uno encuentra rápidamente el orden de un número primo módulo otro número, que puede ser compuesto. El segundo da los factores primos de un número grande $p^n - 1$ hasta un límite. El tercer programa está ilustrado, con resultado, en la respuesta de $\small 2^u - 3^v = 13$.

Resolviendo $$ 3^u - 5^v = 2. $$ Sabemos la solución $27 - 25 = 2$ y sospechamos que esta es la más grande. $$ 3^u - 27 = 5^v - 25. $$ $$ 27 ( 3^x - 1) = 25 ( 5^y - 1). $$ En caso de que $x,y \geq 1:$

Dado por 3: $$ 3^x \equiv 1 \pmod {25} \Longrightarrow 20 | x $$ $$ 3^{20} - 1 = 2^4 \cdot 5^2 \cdot 11^2 \cdot 61 \cdot 1181 $$

Dado por 5: $$ 5^y \equiv 1 \pmod {27} \Longrightarrow 18 | y \Longrightarrow 3 | y $$ $$ 5^{18} - 1 = 2^3 \cdot 3^3 \cdot 7 \cdot 19 \cdot 31 \cdot 829 \cdot 5167 $$ Ignoramos estos.

Usando $1181$. $$ 5^y \equiv 1 \pmod {1181} \Longrightarrow 590 | y \Longrightarrow 10 | y $$ $$ 5^{10} - 1 = 2^3 \cdot 3 \cdot 11 \cdot 71 \cdot 521 $$

Usando $521$. $$ 3^x \equiv 1 \pmod {521} \Longrightarrow 520 | x \Longrightarrow 8 | x $$ $$ 3^{8} - 1 = 2^5 \cdot 5 \cdot 41 $$

Usando $41$. $$ 5^y \equiv 1 \pmod {41} \Longrightarrow 20 | y \Longrightarrow 4 | y \Longrightarrow 12 | y $$ $$ 5^{12} - 1 = 2^4 \cdot 3^2 \cdot 7 \cdot 13 \cdot 31 \cdot 601 $$

Usando $601$. $$ 3^x \equiv 1 \pmod {601} \Longrightarrow 75 | x \Longrightarrow 25 | x \Longrightarrow 100 | x $$ $$ 3^{100} - 1 = 2^4 \cdot 5^3 \cdot 11^2 \cdot 61 \cdot 101 \cdot 151 \cdot 1181 \cdot \mbox{MÁS} $$ Es decir, $$ 125 | (3^x - 1). $$ Esto contradice $$ 27 ( 3^x - 1) = 25 ( 5^y - 1) $$ con $x,y \geq 1.$

Answer 4

Martes, 27 de septiembre, más tarde; adquiriendo cierta confianza en que esto funciona en general, quizás solo con primos grandes.

PRIMERA VERSIÓN

Resulta que, si estamos dispuestos a usar primos demasiado grandes para ser tratados a mano, es posible que podamos obtener una cadena más corta, esta vez con dos primos utilizados en lugar de cuatro.

Resolviendo $$ 2^u - 3^v = 13. $$ Conocemos las soluciones $16 - 3 = 13$ y $256 - 243 = 13$ y sospechamos que esta es la más grande. $$ 2^u - 256 = 3^v - 243. $$ $$ 256 (2^x - 1) = 243 (3^y - 1). $$ En caso de que $x, y \geq 1:$

Dado por 2: $$ 2^x \equiv 1 \pmod {243} \Longrightarrow 162 | x $$ $$ 2^{162} - 1 = 243 \cdot 7 \cdot 19 \cdot 73 \cdot 163 \cdot 2593 \cdot \mbox{Más} $$

Dado por 3: $$ 3^y \equiv 1 \pmod {256} \Longrightarrow 64 | y $$ $$ 3^{64} - 1 = 256 \cdot 5 \cdot 17 \cdot 41 \cdot 193 \cdot \mbox{GRANDE} $$ Ignoramos estos.

Usando $163.$ $$ 3^y \equiv 1 \pmod {163} \Longrightarrow 162 | y $$ $$ 3^{162} - 1 = 2^3 \cdot 7 \cdot 13 \cdot 19 \cdot 37 \cdot 109 \cdot 163 \cdot 433 \cdot 757 \cdot 1297 \cdot 3889 \cdot 8209 \cdot 19441 \cdot 19927 \cdot 208657 \cdot 224209 \cdot \mbox{GRANDE} $$

Usando $ 19441.$ $$ 2^x \equiv 1 \pmod { 19441} \Longrightarrow 4860 | x \Longrightarrow 486 | x $$ $$ 2^{486} - 1 = 3^6 \cdot 7 \cdot 19 \cdot 73 \cdot 163 \cdot 487 \cdot 1459 \cdot 2593 \cdot 71119 \cdot 87211 \cdot 135433 \cdot 139483 \cdot 262657 \cdot \mbox{GRANDE} $$

Es decir, $$ 729 | (2^x - 1). $$ Esto contradice $$ 256 (2^x - 1) = 243 (3^y - 1). $$ con $x, y \geq 1.

\=============================================================

Creo que debería agregar la razón por la cual supe que debía elegir el primo 19441 cuando apareció (la elección de 163 fue un poco aleatoria, solo un factor primo de $2^{162} -1$). Fue porque las primeras cosas que calculé fueron las siguientes. Pregunté por qué primos $p$ el orden de $2$ sería divisible por $243.$ El noveno de esos primos fue $19441.$

jagy@phobeusjunior:~$ ./order 2 243
243   162 = 2 * 3^4
jagy@phobeusjunior:~$ ./order 3 256
256    64 = 2^6

jagy@phobeusjunior:~$ ./order 2 729
729   486 = 2 * 3^5
jagy@phobeusjunior:~$ ./order 3 512
512   128 = 2^7

jagy@phobeusjunior:~$ ./order_mult 2 243
487   243 = 3^5
1459   486 = 2 * 3^5
2917   972 = 2^2 * 3^5
4861   972 = 2^2 * 3^5
8263  4131 = 3^5 * 17
12637 12636 = 2^2 * 3^5 * 13
17011 17010 = 2 * 3^5 * 5 * 7
17497  4374 = 2 * 3^7
19441  4860 = 2^2 * 3^5 * 5    ******
19927  9963 = 3^5 * 41
20899 20898 = 2 * 3^5 * 43
21871 10935 = 3^7 * 5
32077 32076 = 2^2 * 3^6 * 11
32563 32562 = 2 * 3^5 * 67
36451  7290 = 2 * 3^6 * 5
39367  2187 = 3^7
42283 42282 = 2 * 3^6 * 29
47143 23571 = 3^5 * 97
jagy@phobeusjunior:

jagy@phobeusjunior:~$ ./order_mult 3 128
257   256 = 2^8
641   640 = 2^7 * 5
1409  1408 = 2^7 * 11
3329  3328 = 2^8 * 13
4481  4480 = 2^7 * 5 * 7
7681   640 = 2^7 * 5
7937  7936 = 2^8 * 31
9473  9472 = 2^8 * 37
9857   896 = 2^7 * 7
10753  2688 = 2^7 * 3 * 7

\=======================================

Miércoles por la tarde, 28 de septiembre de 2016. SEGUNDA VERSIÓN

Esta se puede hacer con dos primos modestos: $193, 257$ $$ 256 (2^x - 1) = 243 (3^y - 1) $$ $$ 3^y \equiv 1 \pmod {256} \Longrightarrow 64 | y. $$ $$ 3^{64} - 1 = 256 \cdot 5 \cdot 17 \cdot 41 \cdot 193 \cdot \mbox{GRANDE} $$ Usamos $193.$

$$ 2^x \equiv 1 \pmod {193} \Longrightarrow 96 | x. $$ $$ 2^{96} - 1 = 9 \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 97 \cdot 193 \cdot 241 \cdot 257 \cdot 673 \cdot 65537 \cdot 22253377 $$ Usamos $257.$ $$ 3^y \equiv 1 \pmod {257} \Longrightarrow 256 | y. $$

Confirmamos $$ 3^{256} - 1 = 1024 \cdot 5 \cdot 17 \cdot 41 \cdot 193 \cdot \mbox{más} $$ $$ 1024 | (3^y - 1) $$ Esto contradice $$ 256 (2^x - 1) = 243 (3^y - 1) $$ con $x, y \geq 1.

\==================================================

2^s  = 3^t + 13   

256 * ( 2^x - 1 ) = 243 * ( 3^y - 1)

jagy@phobeusjunior:~$ ./order 2  243
243   162 = 2 * 3^4
jagy@phobeusjunior:~$ ./order 3 256
256    64 = 2^6
jagy@phobeusjunior:~$ 
jagy@phobeusjunior:~$
jagy@phobeusjunior:~$ ./order 2  729
729   486 = 2 * 3^5
jagy@phobeusjunior:~$ ./order 3 512
512   128 = 2^7
jagy@phobeusjunior:~$ 

========================================================
Dado: 162 | x ,      64 | y
DESEO   243 | x     O   128 | y
========================================================
256 * ( 2^x - 1 ) = 243 * ( 3^y - 1)

jagy@phobeusjunior:~$ ./prime_power_minus_one 2 162
    2^162 - 1    = 3^5 7 19 73 163 2593 71119 87211 135433 262657  cdot mbox{BIG}

jagy@phobeusjunior:~$ ./prime_power_minus_one 3 64
    3^64 - 1    = 2^8 5 17 41 193  cdot mbox{BIG} 

Usamos 193:  2^x == 1 mod 193   ==> 96 | x
jagy@phobeusjunior:~$ ./order 2 193
193    96 = 2^5 * 3
jagy@phobeusjunior:~$ ./prime_power_minus_one 2 96
    2^96 - 1    = 3^2 5 7 13 17 97 193 241 257 673 65537  22253377

Usamos 257: 3^y == 1 mod 257 ==> 256 | y
jagy@phobeusjunior:~$ ./order 3 257
257   256 = 2^8
jagy@phobeusjunior:~$ ./prime_power_minus_one 3 256
    3^256 - 1    = 2^10 5 17 41 193 257 275201  cdot mbox{BIG}

1024 | ( 3^y - 1) contradice
256 * ( 2^x - 1 ) = 243 * ( 3^y - 1)
con x, y >= 1.

jagy@phobeusjunior:~$ ./order_mult 2 243
487   243 = 3^5
1459   486 = 2 * 3^5
2917   972 = 2^2 * 3^5
4861   972 = 2^2 * 3^5
8263  4131 = 3^5 * 17
12637 12636 = 2^2 * 3^5 * 13
17011 17010 = 2 * 3^5 * 5 * 7

jagy@phobeusjunior:~$ ./order_mult 3 128
257   256 = 2^8
641   640 = 2^7 * 5
1409  1408 = 2^7 * 11
3329  3328 = 2^8 * 13
4481  4480 = 2^7 * 5 * 7
7681   640 = 2^7 * 5
7937  7936 = 2^8 * 31
9473  9472 = 2^8 * 37
9857   896 = 2^7 * 7
10753  2688 = 2^7 * 3 * 7

\===================================================

Answer 5

Miércoles por la mañana, 28 de septiembre de 2016.

Se encontró una cadena de dos primos que demuestra $$ 3^s + 5 = 2^t. $$ Parte de la mejora fue verificar los órdenes de los posibles primos en el primer paso, siendo estos $7,19,73.$ Otra mejora fue simplemente mantener los exponentes tal como están, sin extraer factores primos. $6481$ divide a $3^{72} - 1$ pero no divide a $3^{36} - 1.$ Divide a $3^{24} - 1$ pero no a $3^{12} - 1$ o $3^{8} - 1.$

Primos utilizados: $$ 19, 6481 $$

\========================================

3^s + 5 = 2^t   

27 * ( 3^x - 1 ) = 32 * ( 2^y - 1)

jagy@phobeusjunior:~$ ./order 3 32
32     8 = 2^3
jagy@phobeusjunior:~$ ./order 2 27
27    18 = 2 * 3^2
jagy@phobeusjunior:~$ 
jagy@phobeusjunior:~$ ./order 3 64
64    16 = 2^4
jagy@phobeusjunior:~$ ./order 2 81
81    54 = 2 * 3^3
jagy@phobeusjunior:~$
========================================================
Dado: 8 | x ,      18 | y
DESEADO    16 | x     O   54 | y
========================================================
jagy@phobeusjunior:~$ ./prime_power_minus_one 2 18
    2^18 - 1    = 3^3 7 19  73

jagy@phobeusjunior:~$ ./order 3 7
7     6 = 2 * 3
jagy@phobeusjunior:~$ ./order 3 19
19    18 = 2 * 3^2    NOTAR cómo este da un factor 3 extra!
jagy@phobeusjunior:~$ ./order 3 73
73    12 = 2^2 * 3

usar 19:   9 | x ==>  72 | x

    3^72 - 1    = 2^5 5 7 13 19 37 41 73 757 6481 530713  282429005041

jagy@phobeusjunior:~$ 
jagy@phobeusjunior:~$  ./order_mult 2 81
163   162 = 2 * 3^4
487   243 = 3^5
1297   648 = 2^3 * 3^4
1459   486 = 2 * 3^5
1621  1620 = 2^2 * 3^4 * 5
1783   891 = 3^4 * 11
2269  2268 = 2^2 * 3^4 * 7
2593    81 = 3^4
2917   972 = 2^2 * 3^5
3079  1539 = 3^4 * 19
3727  1863 = 3^4 * 23
3889   648 = 2^3 * 3^4
4861   972 = 2^2 * 3^5
5023  2511 = 3^4 * 31
6481   810 = 2 * 3^4 * 5   *************** ¡VIVA! ***** 
7129  1782 = 2 * 3^4 * 11
8263  4131 = 3^5 * 17
9397  9396 = 2^2 * 3^4 * 29
9721   810 = 2 * 3^4 * 5

6481   810 = 2 * 3^4 * 5

usar 6481:

jagy@phobeusjunior:~$ ./order 2 6481
6481   810 = 2 * 3^4 * 5

   810 | y  ==>  54 | y

\=========================================