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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.