# Elementary solution of exponential Diophantine equation $2^x - 3^y = 7$.

The title says it all. I would like to have a solution, preferably one which is as elementary as possible, of the exponential Diophantine equation $$2^x - 3^y = 7$$ where $x,y$ are non-negative integers. Note that some small solutions are $(x,y)=(3,0)$ and $(x,y)=(4,2)$. If I really had to solve it at all costs, I would translate this to the problem of finding integral points on a bunch of curves of genus $1$. However, I would like to know if there are any simpler methods out there.

As far as I can see, simple congruence tricks won't work: $2^x = 7$ is soluble $3$-adically and $-3^y = 7$ is soluble $2$-adically, so I can't see how we could get anything by looking $p$-adically for $p=2$ or $p=3$, and I think the fact that the solution set to the original problem is non-empty means that $p$-adic considerations for $p \neq 2,3$ have no chance of working either. (But maybe I'm wrong.)

• Erm... $2^4-3^2=7$? – Valborg Sep 25 '16 at 21:21
• Yes, sorry, I meant a complete solution. :) – RP_ Sep 25 '16 at 21:21
• Yea, I just saw your edit. Sorry for cluttering up the comments! – Valborg Sep 25 '16 at 21:22
• I don't suppose you've already considered that this might be very hard, given how hard it was to tackle Catalan's conjecture? – Valborg Sep 25 '16 at 21:26
• @Valborg these might not be amazingly hard when both bases are fixed and it is the exponents that may vary. I have seen $3^x - 2^y = 1$ on this site and I think there was a solution that was not too bad. – Will Jagy Sep 25 '16 at 21:36

Looking at the equation modulo $3$ gives that $2^x \equiv 1 \pmod{3}$ unless $y = 0$, hence $x$ is even. On the other hand, modulo $7$ we have $2^x \equiv 3^y \pmod{7}$, and since $2 \equiv 3^2 \pmod{7}$ and $3$ is a primitive root modulo $7$, this implies that $2x - y$ is divisible by $6$, and hence $y$ is even also. Writing $x = 2m$ and $y = 2n$, we find

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

Now, we use the primality of $7$, and it is easily seen that the only solution is $m = 2, n = 1$. If $y = 0$, then obviously $x = 3$, so the only solutions are $(4, 2)$ and $(3, 0)$.

• works for me.... – Will Jagy Sep 25 '16 at 22:00
• Since $x$ is even, you can also look at $2^{2m} - 3^y = 7$ mod $4$ to obtain $-(-1)^y \equiv -1 \pmod4$ as another way to see that $y$ is even. – arkeet Sep 28 '16 at 20:08

Compare Exponential Diophantine equation $7^y + 2 = 3^x$ answer by @Gyumin Roh

I made up a variant problem in comments. It seems that this method, posted by a Korean high school student, allows for such variations. $$2^u - 3^v = 5$$ We see $8-3=5$ and $32-27 = 5.$ I did not get very far working around the solution $8-3,$ but $32 - 27$ was productive. I had to use one large prime, where finding the orders of $2,3 \pmod p$ would be prohibitive by hand. Nevertheless, these can be checked. Maybe I will be able to find a smaller string of primes. In this first version, I used $41, 31, 4561, 17.$

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

FIRST VERSION:

$$2^u = 3^v + 5$$ $$2^u - 32 = 3^v - 27$$ Apparently I turned it around. $$3^v - 27 = 2^u - 32.$$ With $v \geq 4$ and $u \geq 6,$ $$27 ( 3^x - 1) = 32 ( 2^y - 1)$$ with $x,y \geq 1,$ so that $3^x - 1 > 0$ and $2^y - 1 > 0.$ What we want to do is show that $3^x - 1$ is divisible by $64,$ because that will contradict the given factorization $32 \cdot \mbox{ODD}.$ In turn, this will contradict the existence of such an additional solution beyond those we knew.

Here we go, $$3^x \equiv 1 \pmod{32}.$$ This means that $8 | x.$ We factor, in hopes of finding useful new primes. $$3^8 - 1 = 32 \cdot 5 \cdot 41.$$ We use $41.$ Note that $8|x,$ so that $(3^8 - 1)| (3^x - 1)$ and so $41 | (3^x - 1).$ Therefore $41 |(2^y - 1).$

$$2^y \equiv 1 \pmod{41}.$$ This means that $20 | y.$ We factor, in hopes of finding useful new primes. $$2^{20} - 1 = 3 \cdot 5^2 \cdot 11 \cdot 31 \cdot 41.$$ We use $31$ now, with $31 |(3^x - 1).$

$$3^x \equiv 1 \pmod{31}.$$ This means that $30 | x.$ We factor, in hopes of finding useful new primes. $$3^{30} - 1 = 8 \cdot 7 \cdot 11^2 \cdot 13 \cdot 31 \cdot 61 \cdot 271 \cdot 4561.$$ We use $4561.$ We get $4561 |(2^y - 1).$ Sorry about that. I will look for a smaller string of primes later.

$$2^y \equiv 1 \pmod{4561}.$$ This means that $2280 | y,$ in particular $8|y.$ $$2^{8} - 1 = 3 \cdot 5 \cdot 17 .$$ We use $17$ now. Therefore $17 |(3^x - 1).$

$$3^x \equiv 1 \pmod{17}.$$ This means that $16 | x.$ $$3^{16} - 1 = 64 \cdot 5 \cdot 17 \cdot 41 \cdot 193 .$$

As I said, $64 | (3^{16} - 1)| (3^x-1)$ contradicts $27 ( 3^x - 1) = 32 ( 2^y - 1)$ with $3^x - 1 > 0$ and $2^y - 1 > 0.$

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

SECOND VERSION: I used $41, 31, 241, 17.$

$$27 ( 3^x - 1) = 32 ( 2^y - 1)$$ with $x,y \geq 1,$ so that $3^x - 1 > 0$ and $2^y - 1 > 0.$ What we want to do is show that $3^x - 1$ is divisible by $64,$ because that will contradict the given factorization $32 \cdot \mbox{ODD}.$ In turn, this will contradict the existence of such an additional solution beyond those we knew.

Here we go, $$3^x \equiv 1 \pmod{32}.$$ This means that $8 | x.$ We factor, in hopes of finding useful new primes. $$3^8 - 1 = 32 \cdot 5 \cdot 41.$$ We use $41.$ Note that $8|x,$ so that $(3^8 - 1)| (3^x - 1)$ and so $41 | (3^x - 1).$ Therefore $41 |(2^y - 1).$

$$2^y \equiv 1 \pmod{41}.$$ This means that $20 | y.$ We factor, in hopes of finding useful new primes. $$2^{20} - 1 = 3 \cdot 5^2 \cdot 11 \cdot 31 \cdot 41.$$ We use $31$ now, with $31 |(3^x - 1).$

$$3^x \equiv 1 \pmod{31}.$$ This means that $30 | x.$ However, we already knew that $8 | x,$ so $120|x.$ We factor, in hopes of finding useful new primes. $$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{FOUR BIG}.$$ We use $241.$ We get $241 |(2^y - 1).$ I checked as to where it occurs, $241$ is the smallest prime factor of $3^{40} - 3^{20} + 1.$ Note that $( t^{40} - t^{20} + 1) =(t^8 - t^4 + 1)(t^{32} + t^{28} - t^{20} - t^{16} - t^{12} + t^4 + 1)$ was predictable based on the complex cube roots of $-1,$ however $241$ divides the less pleasant polynomial factor, in context $3^{32} + 3^{28} - 3^{20} - 3^{16} - 3^{12} + 3^4 + 1= 241 \cdot 298801 \cdot 26050081.$ Go Figure.

$$2^y \equiv 1 \pmod{241}.$$ This means that $24 | y,$ in particular $8|y.$ $$2^{8} - 1 = 3 \cdot 5 \cdot 17 .$$ We use $17$ now. Therefore $17 |(3^x - 1).$

$$3^x \equiv 1 \pmod{17}.$$ This means that $16 | x.$ $$3^{16} - 1 = 64 \cdot 5 \cdot 17 \cdot 41 \cdot 193 .$$

As I said, $64 | (3^{16} - 1)| (3^x-1)$ contradicts $27 ( 3^x - 1) = 32 ( 2^y - 1)$ with $3^x - 1 > 0$ and $2^y - 1 > 0.$

• Thank you so much! I had no idea so much could be done by elementary methods. – RP_ Sep 26 '16 at 16:51
• @René found a second, mostly identical proof, with smaller primes. Meaning, I guess, that it is worth checking various relevant computations on computer. Also interesting that the $8-3$ solution seemed to give nothing usable. – Will Jagy Sep 26 '16 at 18:32
• I am still trying to figure out what this method does "conceptually". It is indeed very intriguing that the smaller solution doesn't give anything, but maybe we will be able to understand why that is when we understand the method better... – RP_ Sep 26 '16 at 18:44
• Probably the reason that the smaller solution doesn't give a contradiction is simply the fact that a greater solution exists, so the contradiction you're looking for does not exist. – RP_ Sep 26 '16 at 18:56
• @René : I've made a comment (in an answer box), possibly this gives a better idea for the "conceptually" aspect. – Gottfried Helms Oct 3 '16 at 9:35

Tuesday, 27 September

Getting better at this. I found that gp-pari was taking too long. I wrote three easy C++ programs. One quickly find the order of a prime mod some other number, which is allowed to be composite. The second gives the prime factors of a big number $p^n - 1$ up to a bound. The third program is illustrated, with output, in the $\tiny 2^u - 3^v = 13$ answer.

Solving $$3^u - 5^v = 2.$$ We know the solution $27 - 25 = 2$ and suspect this is the largest. $$3^u - 27 = 5^v - 25.$$ $$27 ( 3^x - 1) = 25 ( 5^y - 1).$$ In case $x,y \geq 1:$

Given from 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$$

Given from 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$$ We ignore these.

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

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

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

Using $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{MORE}$$ That is, $$125 | (3^x - 1).$$ This contradicts $$27 ( 3^x - 1) = 25 ( 5^y - 1)$$ with $x,y \geq 1.$

Wednesday morning B, 28 Sept. 2016

$$3^s = 5^t + 2,$$ two primes $19, 1621$

=================================

3^s  = 5^t + 2

27 * ( 3^x - 1 ) = 25 * ( 5^y - 1)

jagy@phobeusjunior:~$./order 3 25 25 20 = 2^2 * 5 jagy@phobeusjunior:~$ ./order 5 27
27    18 = 2 * 3^2
jagy@phobeusjunior:~$./order 3 125 125 100 = 2^2 * 5^2 jagy@phobeusjunior:~$ ./order 5 81
81    54 = 2 * 3^3

========================================================
Given: 20 | x ,      18 | y
WANT    100 | x     OR   54 | y
========================================================

jagy@phobeusjunior:~$./prime_power_minus_one 3 20 3^20 - 1 = 2^4 5^2 11^2 61 1181 jagy@phobeusjunior:~$ ./prime_power_minus_one 5 18

5^18 - 1    = 2^3 3^3 7 19 31 829  5167
jagy@phobeusjunior:~$./order 3 19 19 18 = 2 * 3^2 jagy@phobeusjunior:~$ ./order 3 829
829   207 = 3^2 * 23
jagy@phobeusjunior:~$./order 3 5167 5167 738 = 2 * 3^2 * 41 use 19: 18 | x ==> 180 | x jagy@phobeusjunior:~$ ./prime_power_minus_one 3 180

3^180 - 1    = 2^4 5^2 7 11^2 13 19 31 37 61 73 181 271 757 1181 1621 4561 176401 387631 530713 755551 927001  cdot mbox{BIG}

jagy@phobeusjunior:~$./order_mult 5 81 | head -20 811 405 = 3^4 * 5 1459 243 = 3^5 1621 405 = 3^4 * 5 ****************** 1783 162 = 2 * 3^4 2269 567 = 3^4 * 7 2917 2916 = 2^2 * 3^6 3889 972 = 2^2 * 3^5 4051 2025 = 3^4 * 5^2 4861 81 = 3^4 5023 162 = 2 * 3^4 5347 5346 = 2 * 3^5 * 11 6481 405 = 3^4 * 5 6967 6966 = 2 * 3^4 * 43 7129 891 = 3^4 * 11 USE 1621: jagy@phobeusjunior:~$  ./order 5 1621
1621   405 = 3^4 * 5

405 | y AND 18 | y ==>  54 | y
jagy@phobeusjunior:~$./prime_power_minus_one 5 54 5^54 - 1 = 2^3 3^4 7 19 31 109 163 271 487 829 4159 5167 31051 16018507 so 81 | 27 * ( 3^x - 1 ), contradicts x >= 1.  ================================== Wednesday morning A, 28 September 2016. Found a two-prime string that proves $$3^s + 5 = 2^t.$$ Part of the improvement was checking the orders of the possible primes in the first step, those being$7,19,73.$Another improvement was simply to keep the exponents as is, not pull out prime factors.$6481$divides$3^{72} - 1$but does not divide$3^{36} - 1.$It does divide$3^{24} - 1$but not$3^{12} - 1$or$3^{8} - 1.$Primes used: $$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:~$======================================================== Given: 8 | x , 18 | y WANT 16 | x OR 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    NOTICE how this one gives an extra 3 factor!
jagy@phobeusjunior:~$./order 3 73 73 12 = 2^2 * 3 use 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 *************** HOORAY ***** 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 use 6481: jagy@phobeusjunior:~$ ./order 2 6481
6481   810 = 2 * 3^4 * 5

810 | y  ==>  54 | y


=========================================

Tuesday, 27 September, later; getting some confidence that this generally works, just perhaps with large primes.

FIRST VERSION

It turns out that, if we are willing to use primes too large to be dealt with by hand, we may be able to get a shorter string, this time two primes used instead of four.

Solving $$2^u - 3^v = 13.$$ We know the solutions $16 - 3 = 13$ and $256 - 243 = 13$ and suspect this is the largest. $$2^u - 256 = 3^v - 243.$$ $$256 ( 2^x - 1) = 243 ( 3^y - 1).$$ In case $x,y \geq 1:$

Given from 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{More}$$

Given from 3: $$3^y \equiv 1 \pmod {256} \Longrightarrow 64 | y$$ $$3^{64} - 1 = 256 \cdot 5 \cdot 17 \cdot 41 \cdot 193 \cdot \mbox{BIG}$$ We ignore these.

Using $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{BIG}$$

Using $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{BIG}$$

That is, $$729 | (2^x - 1).$$ This contradicts $$256 ( 2^x - 1) = 243 ( 3^y - 1).$$ with $x,y \geq 1.$

=============================================================

I think I should add on the reason that I knew to grab the prime 19441 when it appeared ( the choice of 163 was a bit random, just one prime factor of $2^{162} -1$). It was because the first things I computed were those below. I asked for which primes $p$ the order of $2$ would be divisible by $243.$ The ninth of those primes was $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


=======================================

worth an extra note. While, as far as I know, all the primes in the list with $19441$ are $1 \pmod{243},$ some such primes are missed, such as $3889$ and $5347.$ Here is a list of primes $p \equiv 1 \pmod {243}$ with $p < 50000$

487
1459
2917
3889
4861
5347
8263
9721
12637
17011
17497
19441
19927
20899
21871
25759
26731
30133
32077
32563
33049
36451
37423
39367
42283
46171
47143
47629
jagy@phobeusjunior:


=====================================================

Wednesday afternoon, 28 September 2016. SECOND VERSION

This one can be done with two modest primes: $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{BIG}$$ Use $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$$ Use $257.$ $$3^y \equiv 1 \pmod {257} \Longrightarrow 256 | y.$$

Confirm $$3^{256} - 1 = 1024 \cdot 5 \cdot 17 \cdot 41 \cdot 193 \cdot \mbox{more}$$ $$1024 | (3^y - 1)$$ This contradicts $$256 (2^x - 1) = 243 (3^y - 1)$$ with $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:~$======================================================== Given: 162 | x , 64 | y WANT 243 | x OR 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} Use 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 Use 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) contradicts 256 * ( 2^x - 1 ) = 243 * ( 3^y - 1) with 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  =================================================== This is (again) more a comment than an answer - motivated by René's question for more conceptional background A couple of years ago I began to look at the full primefactorization of the cyclotomic polynomials$f_b(n) = b^n-1 $by looking at$f(n)$modulo the primes, creating a little "algebra" on it based on the theorems of Fermat ("little Fermat") and Euler ("Totient"). The following notations seem to be helpful for such an "algebra": We're considering the canonical primefactorization of the expression $$f_b(n) = p_1^{e_1} \cdot p_2^{e_2} \cdots p_m^{e_m} \tag 1$$ Looking at this for each primefactor$p_k$separately ($f_b(n) \pmod {p_k}$) gives reason for two compact notations: •$[n:p]$with the meaning$[n:p]=0$if$p$does not divide$n$and$=1$if it does divide$n$(also known as "Iverson-brackets"; and no special definition for$n=0$as long as not really needed) •$\{ n, p \} = e $with the meaning of giving the exponent$e$, to which the primefactor$p$occurs in$n$, so$ \{f_b(n),p_1 \} = e_1$implies$f_b(n) = p_1^{e_1} \cdot x$where$gcd(x,p)=1$(in Pari/GP this is the function "valuation(n,p)") The idea is to restate the defining equation (1) with the help of this notations/concepts. Of course, Fermat and Euler show us, that we have periodicity in the occurence of any primefactor, when we increase$n$and that on special$n$the primefactors$p_k$occur even with higher exponent. To have expressive formulae for this too we introduce the formula for • the smallest$n$at which the primefactor$p$occurs first in$f_b(n)$(this is often written as$\text{ord}()$denoting the "order of the multiplicative subgroup mod p" but to avoid possible conflicts with common terms we just call this$\lambda_b(p) $, so in$ f_b(\lambda_b(p)) $the primefactor$p$occurs first time when$n$increases from$1$. Here and in the following we can remove the index-parameter$b$at$f$and at$\lambda$for notational convenience, and even remove the argument with the parenthese at the$\lambda$-function when the referred prime$p$is obvious from context. So we write$ [b^{\lambda(p)} -1 :p]=1$(In Pari/GP it is$\lambda_b(p)=$znorder(Mod(b,p)) ) We'll find, that sometimes in$f(\lambda(p))$the primefactor$p$occurs not only to the first, but by some higher power, so we introduce the function •$\alpha_b(p)$by the implicite definition$ \{ f_b(\lambda_b(p)),p \} = \alpha_b(p) $or simplified$ \{ f(\lambda),p \} = \alpha $For the odd primefactors$p$(the primefactor$p=2$needs one extension) and of course when the base$b$is coprime to the selected$p$, we can then state $$\{b^n-1 , p\} = [n:\lambda]\cdot (\alpha + \{n, p\}) \tag 2$$ For the primefactor$2$and odd$b$the$\lambda$-function is always$1$. And because now always$[f(1):2]=1$and also$[f(1)+2:2]=1$the general expression (2) needs some refinement, but which I do not want show here - its indication may suffice for the following. The question whether the same difference$a^x - b^y =d$can also occur with$a^{x+v} - b^{y+w} =d$can be rewritten as $$\begin{array}{rcl} a^{x+v} - b^{y+w} &= &a^x -b^y \\ a^x(a^v-1) &=& b^y(b^w-1) \\ {a^v-1 \over b^y} &=& {b^w-1 \over a^x} \end{array} \tag 3$$ we find that function$f_a(v)=a^v-1$with divisibility condition by$b^y$and similarly on the rhs. The "conceptual" aspect is now, that on the lhs as well as on the rhs we have terms whose canonical primefactorizations are expressible by the above functions and notations and must be equal except for the bases$a$and$b$which in the given examples are usually primenumbers (and thus primefactors of the other expression) themselves, for instance for the problem$3^{3+v}-5^{2+w} \overset{?}= 3^3-5^2=2$and$a=3$and$b=5$here (and other examples as discussed in Will Jagy's answers) and possible values$\gt 0$for$v$and$w$are sought. Using the canonical primefactorizations we can write $$3^v-1 = 2^{e_1} \cdot 3^0 \cdot 5^2 \cdot 7^{e_4} \cdots =\prod p_k^{e_k}\\ 5^w-1 = 2^{h_1} \cdot 3^3 \cdot 5^0 \cdot 7^{h_4} \cdots = \prod q_i^{h_i} \\$$ and for a solution all variable exponents must respectively be equal:$e_k=h_k$to have equality in eq(3) For searching a possible solution one can, a bit more than @WillJagy has done this, write down a sufficient list of primefactors and the compositions of$3^v-1$and$5^w-1$by that primefactors . With Pari/GP one can easily find $$\small \begin{array} {rl|rl} \{3^v-1,2\} &= e_1 = 1+ [v:2] + \{v,2\} & \{5^w-1,2\} &= h_1 = 2+ \{w,2\} \\ \{3^v-1,3\} &= e_2 = 0 & \{5^w-1,3\} &= h_2 = [w:2](1+ \{w,3\}) \\ \{3^v-1,5\} &= e_3 = [v:4](1+ \{v,5\}) & \{5^w-1,5\} & = h_3 = 0 \\ \{3^v-1,7\} &= e_4 = [v:6](1+ \{v,7\}) & \{5^w-1,7\} &= h_4 = [w:6](1+ \{w,7\}) \\ \vdots \end{array}$$ There are now two critical aspects in that list: • ansatz a) we must find some$v$and$w$such that all$e_k=h_k$except$e_3=2$and$h_2=3$. But as we see, the$\lambda$-entries in the$[v:\lambda]$-terms have common divisors and so the inclusion of some primefactor$p_k$means automatically the inclusion of another primefactor$ p_m$due to the fact, that$\lambda(p_k)$might contain$\lambda(p_m)$as a divisor. And that inclusion would also imply the primefactor$q_m$with the same exponent and thus the inclusion of other$q_n$and so on. So this might run into an infinite progress and this would then give a contradiction to the assumption, that some pair of finite$(v,w)$might allow a solution. • ansatz b) we must - in the logic of a)- find a pair$(v,w)$which imply an inclusion of the bases as primefactors to an exponent which is higher than wanted, such that, for this example in the lhs the primefactor 5 is included to the power of 3 or in the rhs the primefactor 3 is included to the power of 4 or higher. The case b) is the simpler one and can occur already when short lists of primefactors of$f_a(v)$and$f_b(w)$are checked after some$v$and$w$are recognized as mandatory to have equal primepowers at all. The actual computation procedure is in principle the same as Will Jagy has done it, only that I provide an initial list of consecutive primes as possible primefactors of$f_a(v)$and of$f_b(w)$, keep their respective$\lambda_a(p_k), \lambda_b(q_k)$and$\alpha_a(p_k),\alpha_b(q_k)$. The from the example inserted in (3) $$\begin{array}{rcl} 3^{3+v} - 5^{2+w} &= &3^3 -5^2 = 2 \\ 3^3(3^v-1) &=& 5^2(5^w-1) \\ {3^v-1 \over 5^2} &=& {5^w-1 \over 3^3} \end{array}$$ we have that$\{3^v-1,5\}=2$is required, so by$\{3^n - 1,5\} = [n:4](1+\{n,5\}) = 2 $we find that$ [n:4]=1 $and also$1+\{n,5\}=2$and thus$n=4\cdot 5 = 20$and thus the initial exponent$v_0$must be set as$v_0=n=20$. Of course$v_0 = 20$implies that other primefactors shall be included (and by hand we can simply create the list of that other primefactors by factorizing$factor(3^20-1)$using Pari/GP) . What I've got including only the first 100 primes is $$\begin{array} {} p_k & \lambda_3(p_k) & \alpha_3(p_k) & y'\\ 2 & 1 & 1 & 1 \\ 5 & 4 & 1 & 1 \\ 11 & 5 & 2 & 2 \\ 61 & 10 & 1 & 1 \end{array}$$ *(the column y' here means, that including the primefactor$p_k$and using the thus required value of$v$we get$5$to the power of y' in$f_3(v)$)* Similarly this can be done using$ \{5^w-1,3\} =3 $following$ \{5^n-1,3\} = [n:2](1+\{n,3\}) = 3 \to n = 2 \cdot 3^2 $and$w_0 = 18$. In the similar way as before we find, that other primefactors$q_k$are now involved,see this: $$\small \begin{array} {} q_k & \lambda_5(q_k) & \alpha_5(q_k) & x' \\ 2 & 1 & 2 & 2 \\ 3 & 2 & 1 & 1 \\ 7 & 6 & 1 & 2 \\ 19 & 9 & 1 & 3 \\ 31 & 3 & 1 & 2 \end{array}$$ Next, because all exponents of the involved primefactors$p_k$and$q_k$must be equal$e_k = h_k$we build the common set$C$of involved primefactors having the maximum exponent$c_k=max(e_k,h_k)$, excluding the primefactors which equal the mutual bases. That means, for instance, we have to increase$v_1$, such that$v_2=v_1 \cdot x$and the prime$p = 31$can occur in the list of$p_k$with exponent$2$. This is a very systematic job, given the above list of$\lambda$'s and$\alpha$'s and can be done using only a finite list of possible primefactors to include, say of length$100$. This allows then a (relatively) simple algorithm which can be applied "blindly" to some problem. • 1) Initialization: given the bases$a$and$b$select an upper bound maxk for primefactors in the primefactorization. Initialize the lists of$\lambda$and$\alpha$for$p_k$and$q_k$up to maxk primes with respect to base1$b_1= 3$and base$b_2 = 5$and the required exponents$x=3$and$y=2$. Compute the initial$v_1$and$w_1$from the condition, that$5^2$shall be factor of$f_3(v)$and$3^3$shall be factor of$f_5(w)$• 2.a) adaption: at iteration-step$i$given$v_i$produce the list of primefactors$p_k$which would occur in$f_3(v_i)$and given$w_i$the list$q_k$which would occur in$f_5(w_i)$. • 2.b) combination: create the combined list$C$of all occuring primefactors with maximal occuring exponent and compute the required$v_{i+1}$and$w_{i+1}$which allow the occurence of all$C_k$in$f_3(v_{i+1})$and in$f_5(w_{i+1})$Iterate the steps 2.a and 2.b until either in$f_3(v_i)$are too many primefactors$p_3 =5$or in$f_5(w_i)$are too many primefactors$p_2=3$. If this does not occur in a meaningful number of iterations, increase the number maxk and start again or break with inconclusive result. With two iterations of the steps 2.a and 2.b I get the following with some simple Pari/GP-procedures:  maxk=100;b1=3,b2=5;x=3;y=2 init (b1,b2, x,y, maxk) \\ result: v=20 w=18 {f_3(v) -1, 5}= 2=y {f_5(w) -1, 3}= 3 =x adapt \\ primeslist p_k = [2, 5, 11, 61] \\ primeslist q_k = [2, 3, 7, 19, 31] \\result : v=360 w=1980 {f_3(v) -1, 5}= 2=y {f_5(w) -1, 3}= 3 =x adapt \\ primeslist p_k = [2, 5, 7, 11, 13, 19, 31, 37, 41, 61, 73, 181, 241, 271] \\ primeslist q_k = [2, 3, 7, 11, 13, 19, 23, 31, 37, 41, 61, 67, 71, 89, 181, 199, 331, 397, 521] \\result : v=720720 w=11880 {f_3(v) -1, 5}= 2=y {f_5(w) -1, 3}= 4 >x !! \\ here we get now the contradiction because f_5(w) has too many factors 3  Other than in Will Jagy's code here is less "guess" - using a defined set of possible primefactors (the first maxk primes) and only the iterated adapt-function seems to provide the contradiction-result without further manual intervention and/or guesses - so this is the reason, that I assume this a better solution reflecting a "conceptual" ansatz. The Pari/GP-code is not difficult and I can append them on request. (errors, typos shall be removed when I detect them) [update]: the essay with more systematic explanations was updated • Hi, Gottfried. I did another one math.stackexchange.com/questions/1946621/… and am now fairly confident about the nature of the guesswork I am doing, and wondering if such guesswork will always succeed in finishing the problem when the largest solution, in that case$7^a = 3^b + 100,$really has been correctly identified. I decided not to include all the extras in that answer, just the final version that works. – Will Jagy Oct 3 '16 at 16:31 • Oh, I also used the minimum size exponents that work. For example,$3$turns out to be a primitive root$\pmod {811},$so I could have typed in$3^{810} -1,$but needed only $$3^y \equiv 1 \pmod {811} \Longrightarrow 810 | y \Longrightarrow 81 | y.$$ $$3^{81} - 1 = 2 \cdot 13 \cdot 109 \cdot 433 \cdot 757 \cdot 3889 \cdot 8209 \cdot \mbox{BIG}$$ – Will Jagy Oct 3 '16 at 16:37 • @Will - unfortunately the method shown above does not obviously point to a specific prime which gives "the contradiction" - be it by the smallest prime in the decision tree, be it some smartly indexed other prime; I've not yet have a good idea to propose a "canonical solution", shortcutting the above full process. I'll also read your answers carefully in the hope to get some inspiration for some more efficient decision-tree and decision-finding... – Gottfried Helms Oct 3 '16 at 17:06 • Gottfried, thanks. – Will Jagy Oct 3 '16 at 17:36 Another slightly simpler try avoiding primitive roots as used by @Starfall: $$\begin{array} {ccl} 2^x &- 3^y &= 7 \\ 2^x &&\equiv 1 &\pmod 3 &\implies x=2x_1 \\ 4^{x_1} &- 3^y &= 7 \\ & - 3^y &= -1 &\pmod 4 &\implies y=2y_1 \\ 4^{x_1} &- 9^{y_1} &= 7 \\ 4^{x_1}& & \equiv 7 &\pmod 9 &\implies x_1=2 + 3x_2 \\ 2^{2(2+3x_2)} &- 3^{2y_1} &= 7 \\\end{array}$$ and then, because the exponents are even, by factoring and using that$7$is prime:$\qquad \qquad \displaystyle\begin{array}{rcc} \underset{a=1}{\underbrace{(4 \cdot 8^{x_2} - 3^{y_1})}}&\cdot& {\underset{b=7}{\underbrace{(4 \cdot 8^{x_2} + 3^{y_1})}}} &= 7 &\qquad \qquad&&&\\ \end{array} $and finally$\displaystyle \qquad \qquad b=7 \implies x_2=0, y_1=1 \\ \qquad \qquad \phantom {b=7}\implies x=4, y=2 \qquad \text{ is the only solution}\$