7
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ Playing around, $x=3$ and $y=7$ also work... $\endgroup$
    – imranfat
    Nov 18, 2016 at 16:42
  • 1
    $\begingroup$ See the generalization of Catalan's conjecture; for $n=10$. $\endgroup$
    – Dietrich Burde
    Nov 18, 2016 at 16:42
  • $\begingroup$ OK, and prove no other exist. $\endgroup$
    – Stoyan Apostolov
    Nov 18, 2016 at 17:08
  • 1
    $\begingroup$ 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...) $\endgroup$
    – Gottfried Helms
    Nov 19, 2016 at 4:17
  • 1
    $\begingroup$ @Xamm - please see my answer. $\endgroup$
    – Gottfried Helms
    Nov 28, 2016 at 0:11

2 Answers 2

Reset to default
5
$\begingroup$

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

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

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

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

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
=============================================================
$\endgroup$
5
$\begingroup$

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
no contradiction found

-

\\ 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

contradiction in next iteration:
     {13^n -1,3}=8 shall occur in next iteration 
                   by required primefactor 17497 = 1+ 2^3*3^7

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)

$\endgroup$
1
  • $\begingroup$ Thank you so much for your answer. $\endgroup$
    – Xam
    Nov 28, 2016 at 2:21

You must log in to answer this question.

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