Finding solutions to the diophantine equation $7^a=3^b+100$

Question

Find the positive integer solutions of the diophantine equation $$7^a-3^b=100.$$

So far, I only found this group $7^3-3^5=100$.

Answer 1

Fair to say that creating this proof (especially predicting that the ordered pair of primes $811$ and $3889$ would work) is out of the reach of hand computations, although everything used can be confirmed by hand. We have $7^a = 3^b + 100,$ and suspect that the largest solution is $343 = 243 + 100.$ Well, take $7^a - 343 = 3^b - 243.$ This becomes $$ 343 ( 7^x - 1) = 243 ( 3^y - 1). $$ We are going to prove that we cannot accomplish this with $x,y \geq 1.$

Assuming $x,y \geq 1:$ Since $$ 7^x \equiv 1 \pmod {243}, $$ we find $$ 81 | x \Longrightarrow 27 | x. $$

$$ 7^{27} - 1 = 2 \cdot 3^4 \cdot 19 \cdot 37 \cdot 109 \cdot 811 \cdot 1063 \cdot 2377 \cdot 2583253 $$ This divides $7^x - 1.$ In particular, $811 | (7^x - 1),$ and so $811 | (3^y - 1.)$

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

$$ 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} $$ In particular, $3^{81} - 1$ is divisible by $3889,$ so $3^y - 1$ is divisible by $3889.$ In turn, this means that $7^x - 1$ is divisible by $3889.$

$$ 7^x \equiv 1 \pmod {3889} \Longrightarrow 1944 | x \Longrightarrow 243 | x. $$

jagy@phobeusjunior:~$ ./order 7 3889
3889  1944 = 2^3 * 3^5

We have shown $243 | x.$ However, $$ 7^{243} -1 = 2 \cdot 3^6 \cdot 19 \cdot 37 \cdot \mbox{Many More}$$ This means that $$ 729 | (7^x - 1) $$ This contradicts $$ 343 ( 7^x - 1) = 243 ( 3^y - 1) $$ with $x,y \geq 1.$

I learned this technique from Exponential Diophantine equation $7^y + 2 = 3^x$ I also placed three different examples as answers at Elementary solution of exponential Diophantine equation $2^x - 3^y = 7$.

Answer 2

We start with $$ 7^a - 3^b = 100 = 7^3 - 3^5 \tag 1$$ rewrite $$ 7^a - 7^3 = 3^b - 3^5 \\ 7^{3+x} - 7^3 = 3^{5+y} - 3^5 $$ and work from the final ansatz,searching positive $x$ and $y$ in $$ { 7^x -1 \over 3^5} = { 3^y-1\over 7^3 } \tag 2$$ "By hand" we can know already, that $3 \mid 7^1-1 $ and thus that $3^5 \mid 7^{1 \cdot 3^4} -1 $ and other way round, that $7 \mid 3^6-1 $ and thus that $7^3 \mid 3^{6 \cdot 7^2} -1 $ so we know, that for any solution we must have $x=3^4 \cdot x_1 = 81 x_1 $ and $y=6 \cdot 7^2 \cdot y_1= 294 y_1$ and our equation on step 1 looks like $$ { 7^{3^4 x_1} -1 \over 3^5} = { 3^{6 \cdot 7^2 \cdot y_1}-1\over 7^3 } \tag 3$$ where $x_1$ and $y_1$ are some positive integer but with the restriction that $ 3 \not\mid x_1$ and $ 7 \not\mid y_1$
Letting $x_1=y_1=1$ first then this defines a set of primefactors in the numerators of each fraction which is too much to do by hand. But we can at least immediately see, that they differ already in the primefactors 2: while $ 3^6 \equiv 1 \pmod {2^8}$ is $ 7^1 \equiv 1 \pmod {2^1}$ so the primefactorization of the lhs begins with $2^1 \cdot ...$ and that of the rhs with $2^8 \cdot ... $ Still by hand it is possible to introduce the missing primefactors $2^7$ into the lhs by increasing the exponent, such that $x_1 = 2^5 \cdot x_2 $ and we get $$ { 7^{3^4 2^5 x_2} -1 \over 3^5} = { 3^{6 \cdot 7^2 \cdot y_1}-1\over 7^3 } \tag 4$$ What the last procedure does: adapt the primefactorizations of both sides by expanding the exponents must now be iterated until in the lhs a primefactor $p$ must be inserted which has order $3^5$ with base $7$ such that the numerator is divisible by $3^6$ instead by $3^5$ and after cancelling against the denominator one primefactor $3$ remains: then the lhs and rhs cannot be equal, because the rhs can never assume a primefactor $3$.
Of course, this cannot be done by hand in short time, however in principle it can be done and a relative primitive computer-procedure finds $p=3889$ with order $2^3 \cdot 3^5$ with base $7$ in two iterations (using the list of ca 550 first primes...).

So this answer does not fit the condition for the bounty but gives a general recipe - and possibly a shortcut solution by hand, perhaps by some slick factoring, and perhaps using parts of this ansatz can still be found.

---

Just to characterize my ansatz a bit more:

• a.1) initialize PLIST a list of first primes (say 600, must be long enough to contain the final contradictory primefactor, but does not contain huge primefactors) with their multiplicative orders for each of the two bases, here $b_l=7, b_r=3$
• a.2) initialize to find the $n_1=3^4$ and $m_1=6\cdot 7^2$ values first.
  (I denote the equation by $(7^{n_k}-1)/3^5 \overset{?}= (3^{m_k}-1)/7^3$ where $k$ indicates the iteration-index)

---

• b.1) Then from PLIST and $n_k$ and $m_k$ I find two sets LPF and RPF of primefactors which are in the according numerators.
• b.2) Then I join LPF and RPF to get CPF with all primefactors and their maximal exponents that occur
• b.3) and compute $n_{k+1}$ and $m_{k+1}$ accordingly such that $b_l^{n_{k+1}}-1$ as well as $b_r^{m_{k+1}}-1$ can include all primefactors from CPF.
  At each prime from CPF in this process check whether $b_l^{n_{k+1}}-1$ contains $3^6$ as factor (of course by only checking whether $n_{k+1}$ contains $3^5$ due to Euler's theorem), do the same with $b_r^{m_{k+1}}-1$ and $7^4$ as factor analoguously. If such a thing occurs, stop and print the current primefactor as "contradictory" prime.

Repeat b.1) to b.3) until contradiction.

This procedure finds $p=3889$ after two iterations using PLIST with $550$ smallest primes.

I'm sure this simple automatic and sequential search can be refined by some intelligent shortcuts, like some better decision-tree, perhaps in the sense how a navigation-computer finds the shortest/the optimal route from location A to location B . My current simple implementation might give, for instance, a different "contradictory prime" from that which Will Jagy's procedure would give (however in this case they are the same)

Answer 3

note: this answer has been found to be -at least- incomplete, see comments of Gottfried Helms and piquito

$100$ has no primitive root therefore $7^m$ and $3^n$ are congruent with $1$ modulo $100$ for some integers $m,n$ smaller than $100$ and these numbers should divide $100$. We have $7^4\equiv 3^{20}\equiv 1\pmod{100}\Rightarrow 7^{4m}\equiv 3^{20n}\equiv 1\pmod {100}$ which could be a starting point to calculate possible solutions. However we notice in this search that (in the ring $\Bbb Z/100\Bbb Z$ for short) the solution $7^3=3^5+100$ so we have $$\begin{cases}7^a=3^b+100\\7^3=3^5+100\end{cases}\Rightarrow 7^a-7^3=3^b-3^5$$ For the values $a=1,2,3$ and $b=1,2,3,4,5$ it is not verified except for $(a,b)=(3,5)$ which does not provide another solution. Hence $a\gt 3$ and $b\gt 5$. It follows $$7^3(7^{a-3}-1)=3^5(3^{b-5}-1)\Rightarrow 7^{a-3}=244=2^2\cdot61\text{ and } 3^{b-5}=344=2^3\cdot43$$ which is absurde. Consequently $(a,b)=(3,5)$ is the only solution.

Answer 4

You're solving $7^a - 3^b = 100$ in positive integers.

This full solution uses the recent (found in 1998) results by J. Gebel, A. Pethö, G. H. Zimmer, Mordell, etc. (see this paper).

See this paper for some information about Mordell's equations.

mod $7$ gives $b=6k+5$, $k\ge 0$, $k\in\mathbb Z$.

mod $9$ gives $a=3m$, $m\ge 0$, $m\in\mathbb Z$.

$$\left(3\cdot 7^m\right)^3 = 2700 + \left(3^{3k+4}\right)^2$$

http://tnt.math.se.tmu.ac.jp/simath/MORDELL/

shows that $3\cdot 7^m=21$, $3^{3k+4}=\pm 81$, i.e. $(m,k)=(1,0)$, i.e. $(a,b)=(3,5)$.

Answer 5

This is for Gottfried's example, $$ 17^3 (17^x - 1) = 23^2 (23^y - 1), $$ showing that we cannot have $x,y \geq 1. $ Oh, $$ 17^3 = 4913, $$ $$ 17^4 = 83521. $$

jagy@phobeusjunior:~$ ./order 23 4913
4913  4624 = 2^4 * 17^2
jagy@phobeusjunior:~$ ./order 23 20231
20231   289 = 17^2
jagy@phobeusjunior:~$ ./order 17 20231
20231 10115 = 5 * 7 * 17^2
jagy@phobeusjunior:~$ ./order 17 1719551
1719551 10115 = 5 * 7 * 17^2
jagy@phobeusjunior:~$ ./order 23 1719551
1719551 1719550 = 2 * 5^2 * 7 * 17^3
jagy@phobeusjunior:~$ ./order 23 83521
83521 78608 = 2^4 * 17^3
jagy@phobeusjunior:~$ 

Monday, 10 October: I just realized that, to find primes $q$ such that the multiplicative order of $23$ is divisible by $4913,$ the first thing is to examine only primes $q \equiv 1 \pmod {4913}.$ So much faster!!

jagy@phobeusjunior:~$ ./order_mult 23 4913
Mon Oct 10 08:20:35 PDT 2016
Prime      Order of: 23
127739     63869 = 13 * 17^3     count   1
147391     73695 = 3 * 5 * 17^3     count   2
157217     39304 = 2^3 * 17^3     count   3
216173    216172 = 2^2 * 11 * 17^3     count   4
275129     19652 = 2^2 * 17^3     count   5
294781     24565 = 5 * 17^3     count   6
353737     39304 = 2^3 * 17^3     count   7
363563    363562 = 2 * 17^3 * 37     count   8
442171     44217 = 3^2 * 17^3     count   9
471649    471648 = 2^5 * 3 * 17^3     count   10
599387    299693 = 17^3 * 61     count   11
736951    245650 = 2 * 5^2 * 17^3     count   12
746777    373388 = 2^2 * 17^3 * 19     count   13
884341    176868 = 2^2 * 3^2 * 17^3     count   14
894167    447083 = 7 * 13 * 17^3     count   15
1012079    506039 = 17^3 * 103     count   16
1031731    103173 = 3 * 7 * 17^3     count   17
1100513     19652 = 2^2 * 17^3     count   18
1129991     49130 = 2 * 5 * 17^3     count   19
1188947   1188946 = 2 * 11^2 * 17^3     count   20
1326511    265302 = 2 * 3^3 * 17^3     count   21
1336337   1336336 = 2^4 * 17^4     count   22
1355989    677994 = 2 * 3 * 17^3 * 23     count   23
1395293   1395292 = 2^2 * 17^3 * 71     count   24
1424771   1424770 = 2 * 5 * 17^3 * 29     count   25
1454249   1454248 = 2^3 * 17^3 * 37     count   26
1591813    397953 = 3^4 * 17^3     count   27
1631117    815558 = 2 * 17^3 * 83     count   28
1680247    840123 = 3^2 * 17^3 * 19     count   29
1719551   1719550 = 2 * 5^2 * 7 * 17^3     count   30 +++++++
1749029   1749028 = 2^2 * 17^3 * 89     count   31
Prime      Order of: 23
Mon Oct 10 08:20:35 PDT 2016

---

Answer 6

Let $a$ and $b$ be two positive integers such that $$7^a-3^b=100.$$ Reducing mod $7$ shows that $b\equiv5\pmod{6}$, and then reducing mod $13$ shows that $a\equiv3\pmod{12}$. Then reducing mod $181$ shows that $b\equiv5\pmod{45}$, and so we have a primitive integral solution to $$X^3+Y^5=Z^2.$$ All primitive solutions are parametrized by a collection of $27$ bivariate polynomials with integer coefficients${}^1$. It is then a routine check to verify that all solutions of the form $$(X,Y,Z)=(7^m,-3^n,\pm10),$$ have $m=n=1$. This implies the unique solution to the original equation is $(a,b)=(3,5)$.