17
$\begingroup$

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

$\endgroup$
2

6 Answers 6

12
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Nice. Definitely not a hand job. What is the "order" program you used? $\endgroup$ Commented Oct 1, 2016 at 16:50
  • $\begingroup$ @marty, my little program, C++. It takes a prime $p$ and a target $t$ which may be composite, returns the minimum $n$ such that $p^n \equiv 1 \pmod t.$ Another program is to factor some large integer of type $p^k - 1,$ but using trial division with factors only up to a prescribed bound; as you can see, it is the small to medium size prime factors that can be used for this problem. This second program ( and a third) use large integers from GMP. $\endgroup$
    – Will Jagy
    Commented Oct 1, 2016 at 16:57
  • $\begingroup$ Nice,Thank you very much,I want see one methods by hand $\endgroup$
    – math110
    Commented Oct 4, 2016 at 9:39
3
$\begingroup$

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)

$\endgroup$
6
  • $\begingroup$ Hi, Gottfried. I'm not entirely sure, but it seems you wind up with the same $3889$ and finding the order of $7,$ but you do not get that by the same sequence of initial steps I have. $\endgroup$
    – Will Jagy
    Commented Oct 6, 2016 at 2:52
  • $\begingroup$ Hi @Will - it is likely, that my sequence of steps is different; so far I do no "intelligent" selection of primefactors to shorten the procedure/ to extract only primefactors essential for the contradiction, perhaps I can do that in a next approach, this seems to be similar to find the shortest/optimal route between two points in a map (I've put the description how I proceed at the moment into my answer, see there) $\endgroup$ Commented Oct 6, 2016 at 6:50
  • $\begingroup$ @Will - would you like to try $17^3 - 23^2=17^a-23^b$ ? It seems it is more difficult; I need an initial list of the first $7500$ primes and need 3 iterations to arrive at a contradictory primefactor $p=12697$ and would like to know, whether your algorithm would even find a smarter decision-tree? $\endgroup$ Commented Oct 6, 2016 at 10:44
  • 1
    $\begingroup$ Took a while. $4913(17^x - 1) = 529(23^y - 1.) $ So $4624 | y$ ( and $16|y$). $23^{4624} - 1$ is divisible by prime $20231.$ $17^x \equiv 1 \pmod {20231}$ means $10115|x.$ $17^{10115} - 1$ is divisible by prime $1719551.$ $23^y \equiv 1 \pmod {1719551}$ means $(2 \cdot 5^2 \cdot 7 \cdot 17^3) | y.$ So $2^4 \cdot 17^3 | y.$ Therefore $23^y-1$ is divisible by $17^4 = 83521,$ contradicting $4913(17^x - 1) = 529(23^y - 1) $ with $x,y \geq 1.$ $\endgroup$
    – Will Jagy
    Commented Oct 6, 2016 at 18:26
  • 1
    $\begingroup$ placed confirmation as an answer. A long time to find, but confirming that it works is a half dozen computations of "order." I did need to increase the bounds in my programs, as they would not consider any primes over 1,000,000. $\endgroup$
    – Will Jagy
    Commented Oct 6, 2016 at 18:58
3
+25
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ please help to understand why "$\Rightarrow$" in $\Rightarrow 7^{a-3}=244 \text{ and } 3^{b-5}=344$. TY $\endgroup$
    – user354674
    Commented Oct 5, 2016 at 22:43
  • 1
    $\begingroup$ With pleasure. $$(7^3,3^5)=1\Rightarrow 7^3=3^{b-5}-1\iff 3^{b-5}=7^3+1=343+1=344=2^3\cdot 43$$. It is an absurde equality with the primes $3, 2$ and $43$. Similarly with $3^5=7^{a-3}-1\iff 7^{a-3}=244=2^2\cdot 61$ $\endgroup$
    – Piquito
    Commented Oct 5, 2016 at 23:03
  • $\begingroup$ Thank you very much, it's clear now :) $\endgroup$
    – user354674
    Commented Oct 6, 2016 at 0:05
  • $\begingroup$ From $(7^3,3^5)=1$ follows only that $ m \cdot 7^3 = 3^{b-5}-1 $ and $ m \cdot 3^5 = 7^{a-3}-1 $ where $m$ need not equal $1$ as assumed in your answer (at least I don't see, why $m=1$ should be required?) After that, if $m$ can assume other values, we might still have possible alternative solutions... $\endgroup$ Commented Oct 6, 2016 at 0:45
  • 1
    $\begingroup$ @igael: I have a mistake, see the comment by Gottfried Helms. $\endgroup$
    – Piquito
    Commented Oct 6, 2016 at 9:40
2
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ Mordell is ("is", not was) a major league player: his celebrated conjecture about finiteness of rational points on nonsingular curves of genus greater than $1$ was finally demonstrated by Faltings but his equation remains challenging for k large enough. $\endgroup$
    – Piquito
    Commented Oct 6, 2016 at 9:33
1
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Superb! In the afternoon I was trying to implement a refinement of my "brute force" algo in the same way: searching for multiplicative orders (or $\lambda$'s in my notation), but was so far having difficulties to implement the recursive mutual searches with the two bases. Nice to see it working here :-) $\endgroup$ Commented Oct 6, 2016 at 19:08
  • $\begingroup$ Hmm, that long time needed surprises me. I had with my three iterations init : ( adapt check ) ( adapt check) ( adapt check) $\to$ contradiction about $\small 20+\epsilon$ seconds using Pari/GP. The most of the time (20 secs) was used for the init which computes the orders for the first $\small 7500 $ primes to both bases $\small 23$ and $\small 17$ ... $\endgroup$ Commented Oct 7, 2016 at 7:43
  • $\begingroup$ @Gottfried everything is in C++ with only the most naive steps. I've never figured out how to program in Pari/GP. In fact, I was continuing this one, hoping for smaller prime pair, when I ran into trouble just because $p^k - 1$ was so large that the computer just sat there; I wanted the small prime factors, up to 10^7 say. $\endgroup$
    – Will Jagy
    Commented Oct 7, 2016 at 16:19
  • 1
    $\begingroup$ @GottfriedHelms I put in an elementary improvement on the slow step, now it takes one second instead of one hour. There could be other improvements, I don't usually do much with this multiplicative order. $\endgroup$
    – Will Jagy
    Commented Oct 10, 2016 at 15:11
  • 1
    $\begingroup$ congratulations with three stars from my side! :-) I've a similar good message too, I could reduce the computation of the primes-list with orders from quadratic to near linear time consumption, so could start to look at arrays of solutions where $a,b$ range, for instance, from $2$ to $10$ and find how many iterations are required (always 2(?)). It's looking as if not completely meaningless more general questions/hypotheses can be done... $\endgroup$ Commented Oct 10, 2016 at 15:22
0
$\begingroup$

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)$.

$\endgroup$
3
  • $\begingroup$ This sounds interesting. Is there a document, where I can read more about this method using 27 bivariate polynomials? $\endgroup$ Commented May 6, 2023 at 4:02
  • $\begingroup$ @GottfriedHelms There is a link in the footnote: degruyter.com/document/doi/10.1515/crll.2004.043/pdf $\endgroup$
    – Servaes
    Commented May 6, 2023 at 5:44
  • $\begingroup$ Thank you very much! Just a completely different ansatz - much interesting idea! I'll see whether I can get access to the text some way (perhaps via open part of univ. bib. since I'm retired some years ago) $\endgroup$ Commented May 6, 2023 at 8:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .