# Solve $13^x-3^y=10$ in positive integers

As it is "well-known" fact $13-3=10$. Is this true for some other powers of $13$ and $3$, i.e. find all natural numbers $x$ and $y$, such that $13^x-3^y=10$ (there are other, find them all).

• Playing around, $x=3$ and $y=7$ also work... Nov 18, 2016 at 16:42
• See the generalization of Catalan's conjecture; for $n=10$. Nov 18, 2016 at 16:42
• OK, and prove no other exist. Nov 18, 2016 at 17:08
• Another proof, applying brute force as explained in math.stackexchange.com/a/1955911/1714 gives in two iterations, that the primefactor $p=17497$ is involved, which produces a contradiction. The procedure crosschecks iteratively primefactorizations of $f(n_k)={13^{n_k}-1\over 3^7}$ versus $g(m_k)={3^{m_k}-1\over 13^3}$ where $g(m_2)$ involves the primefactor $p$ and then $f(n_3)$ would contain one primefactor $3$ where $g(m)$ cannot contain $3$ as primefactor. (unfortunately the protocol of primefactors involved is too long to fit in the margin...) Nov 19, 2016 at 4:17
• @Xamm - please see my answer. Nov 28, 2016 at 0:11

Long for a comment. I will construct this method for the given problem. At least an hour.

This format, $p^x - q^y = C$ for primes $p,q$ turns out to have a successful elementary procedure. I found it in an answer by a student, the first question linked below; in some cases, the numbers involved are a bit large for hand calculations. I wrote simple computer programs to deal with the larger numbers sometimes needed.

Exponential Diophantine equation $7^y + 2 = 3^x$

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

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

Well, this one would require huge numbers:

2197 ( 13^x - 1)  = 2187 ( 3^y - 1)

jagy@phobeusjunior:~$./order 13 2187 2187 729 = 3^6 jagy@phobeusjunior:~$ ./order 13 6561
6561  2187 = 3^7
jagy@phobeusjunior:~$jagy@phobeusjunior:~$ ./order 3 2197
2197   507 = 3 * 13^2
jagy@phobeusjunior:~$./order 3 28561 28561 6591 = 3 * 13^3 jagy@phobeusjunior:~$

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

jagy@phobeusjunior:~$./order_mult 13 6561 Fri Nov 18 09:44:13 PST 2016 Prime Order of: 13 39367 19683 = 3^9 count 1 52489 52488 = 2^3 * 3^8 count 2 196831 196830 = 2 * 3^9 * 5 count 3 328051 164025 = 3^8 * 5^2 count 4 472393 236196 = 2^2 * 3^10 count 5 629857 629856 = 2^5 * 3^9 count 6 695467 695466 = 2 * 3^8 * 53 count 7 774199 387099 = 3^8 * 59 count 8 866053 78732 = 2^2 * 3^9 count 9 971029 971028 = 2^2 * 3^8 * 37 count 10 997273 124659 = 3^8 * 19 count 11 1102249 367416 = 2^3 * 3^8 * 7 count 12 1154737 72171 = 3^8 * 11 count 13 1194103 597051 = 3^8 * 7 * 13 count 14 1220347 1220346 = 2 * 3^9 * 31 count 15 1299079 433026 = 2 * 3^9 * 11 count 16 1377811 1377810 = 2 * 3^9 * 5 * 7 count 17 1509031 150903 = 3^8 * 23 count 18 1614007 1614006 = 2 * 3^9 * 41 count 19 1705861 852930 = 2 * 3^8 * 5 * 13 count 20 1915813 957906 = 2 * 3^8 * 73 count 21 1968301 984150 = 2 * 3^9 * 5^2 count 22 2020789 505197 = 3^8 * 7 * 11 count 23 2073277 2073276 = 2^2 * 3^8 * 79 count 24 2099521 2099520 = 2^6 * 3^8 * 5 count 25 2165131 2165130 = 2 * 3^9 * 5 * 11 count 26 2296351 328050 = 2 * 3^8 * 5^2 count 27 2427571 1213785 = 3^8 * 5 * 37 count 28 2440693 2440692 = 2^2 * 3^9 * 31 count 29 2598157 1299078 = 2 * 3^10 * 11 count 30 3031183 505197 = 3^8 * 7 * 11 count 31 Prime Order of: 13 Fri Nov 18 09:44:14 PST 2016 ================================================= jagy@phobeusjunior:~$ ./order_mult 3 28561
Fri Nov 18 09:45:32 PST 2016
Prime      Order of: 3
285611    142805 = 5 * 13^4     count   1
342733     85683 = 3 * 13^4     count   2
856831    856830 = 2 * 3 * 5 * 13^4     count   3
2342003   1171001 = 13^4 * 41     count   4
2913223   2913222 = 2 * 3 * 13^4 * 17     count   5
4912493   4912492 = 2^2 * 13^4 * 43     count   6
5483713   1370928 = 2^4 * 3 * 13^4     count   7
6454787   3227393 = 13^4 * 113     count   8
6511909     57122 = 2 * 13^4     count   9
7026007   7026006 = 2 * 3 * 13^4 * 41     count   10
7140251   3570125 = 5^3 * 13^4     count   11
7482983   3741491 = 13^4 * 131     count   12
7654349   7654348 = 2^2 * 13^4 * 67     count   13
7711471   1542294 = 2 * 3^3 * 13^4     count   14
7882837   1970709 = 3 * 13^4 * 23     count   15
9939229   1656538 = 2 * 13^4 * 29     count   16
Prime      Order of: 3
Fri Nov 18 09:45:33 PST 2016
=============================================================


On request by the comment of @Xammm

I show the protocol of my procedure. It works looking at $f(13,n)=13^n-1$ and $f(3,m)=3^m-1$
The problem is to find $n,m \gt 0$ such that $(10 =) 13^3-3^7 = 13^{3+n}-3^{7+m}$ and thus $${13^n-1 \over 3^7} = {3^m-1 \over 13^3}$$ Of course, for $13^n-1$ to be divisible by $3^7$ puts some restriction on $n$, as well as for $3^m-1$ to be divisible by $13^2$ puts some restrictions on $m$.
Eulers totient theorem, and more precisely the "orders" of the involved primefactors, give us minimal $n_0$ and $m_0$.
After finding that we see, that $f(13,n_0)$ has not only the primefactor $3^7$ but other primefactors $q_{0,1..k}$ , as well as $f(3,m_0)$ has other primefactors $r_{0,1..j}$
Now iteration starts: because $f(13,n)$ shall equal $f(3,m)$ they must have the same primefactors. So we compute a combined list of common primefactors that (at least) must be involved in each expression, and again by the Euler-theorem/the "order" of the primefactors, we find new minimal $n_1$ and $m_1$ which allow $f(13,n_1)$ and $f(3,m_1)$ to have, at least, the same small primefactors.
Again, each shall now have additional primefactors, $q_{1,1..k}$ and $r_{1,1..j}$ and the process iterates.

A contradiction occurs, when in iteration $i$ either in the primefactorization of$f(13,n_i)$ occurs the primefactor $3$ with exponent $\gt 7$ or in the primefactorization of $f(3,m_i)$ the primefactor $13$ with exponent $\gt 3$ because that cannot be compensated by the proper additional primefactors in the mutually other expression.
This occurs here in iteration $i=3$. In my procedure I do not really the last combination of primefactors and recomputing new $n_{i},m_{i}$ but it suffices to see, that one of that conditions would occur in the next iteration, so I actually need only two iterations.

Here is the protocol:

 \\ initialization
required n=729   =  3^6    \\ makes sure, 3^7 is primefactor of f(13,n)
required m=507   =  3.13^2 \\ makes sure, 13^3 is primefactor of f(3,m)


-

\\ iteration 1
given n=729   =  3^6
given m=507   =  3.13^2
primefactorizations by n=729 and m=507:
13^n-1=  3^7.  2^2.61.1459...<big>
3^m-1= 13^3.  2.313.2029.6553.7333...<big>
... merging (small) primefactors
... recompute new minimal n and m by orders of primefactors
... show required n and m
new n=162132516   =  2^2.3^6.7.13^2.47
new m=1232010     =  2.3^6.5.13^2


-

\\ iteration 2
given n=162132516   =  2^2.3^6.7.13^2.47
given m=1232010     =  2.3^6.5.13^2
primefactorizations by n=162132516 and m=1232010
13^n-1=  3^7.  2^4.5.7^2.17.19.29.37.43.53.61.79.109.127
.157.163.271.283.313.337.379.463.487.547.659.673.677.757
.937.1093.1223.1459.1693.1873.2029.2269.2539.2857.2917
.4057.4603.4621.4733.4889.5077.5923.6301.6553
.6581.7333.8191.8461.9127.9829.10141.10193.10531.12637.
.13417.14197.15373.15887.17011.18253.20333.21061
.21841.21997.22079.23689.24337.28393.29611.30133.30269
.33049.34217.34763.35533.36097.42589.47659.53299.59879
.73387.75389.79301.81649.95317.101089...<big>
3^m-1=  13^3. 2^3.7.11^2.19.31.37.61.79.109.131.157.163.181
.271.313.433.487.541.757.811.937.1171.1297.1459.1621.2029
.2341.2887.2917.3511.3889.4051.4057.4561.4591.4861.6553
.7333.8101.8209.9127.10141.10531.12637.16381.17497.18253
.19441.19927.21061.21871.28081.35491.37441.45631.48673
.52391.53353.58321.59779.70957.94771...<big>
... merging (small) primefactors
... recompute new minimal n and m by orders of primefactors
... show required n and m
new n=593275916851089872400
=  2^4.3^7.5^2.7.11.13^2.17.19.31.37.41.47.73
new m=341685043014756474995420841782400
=  2^7.3^6.5^2.7^2.11.13^2.17.19.23.31.43.47.59.61.83.151.191.401


Remark: here the notation $\{13^n-1,3\}=8$ means, that the exponent, to which primefactor $3$ occurs in $13^n-1$, is $8$
Technical remark: of course I do not work with the evaluated numbers $x=13^n-1$ where $n$ is greater than, say, $100$ or even million or that $n$ which occur in the process of iterations. Such evaluated numbers $x$ could not be factorized in lifetime. For the "small" primefactors it suffices, to maintain a list of the, say, first 10 000 or 100 000 primes, determine their "orders" for the expression $13^n-1$ and $3^m-1$ respectively, and then, for a given large $n$ check for each prime in the list, whether its order is a divisor of $n$, and thus that prime would occur as primefactor in the expression. The determination of the orders of the primes for some expression $f(b,n)$ and their (repeated) occurence $p^e$ there is not trivial, especially of the primefactor $p=2$ when $b$ is odd. I have introduced for myself the notation $\{b^n-1,p\} = e$ and described that "valuation" operator in a small essay, see here (some subchapters still in draft status)