7
$\begingroup$

Today my friend asked a question for help:

Find all solutions of $2^x=5^y+3$ for non-negative integers $x,y$.

It is obvious that the solutions are $(x,y)=(2,0),(3,1),(7,3)$, and I think there is no more solution. However, we can't prove that these are the only solutions. We have already tried to mod many numbers and still get "may" possible solutions other than the $3$ solutions I have written. I have surfed the Net and still can't find solutions. I hope you guys can help my friend solve. Thank you very much!

$\endgroup$
10
  • $\begingroup$ How are you sure these are the only solutions? Reduce the equation modulo $2$ and see what happens. $\endgroup$
    – Allawonder
    Jan 1, 2020 at 7:12
  • $\begingroup$ @Allawonder this problem is a contest math problem. It would not consist of big number solution. Also modulo 2 is no used dude XD $\endgroup$
    – MafPrivate
    Jan 1, 2020 at 7:36
  • 1
    $\begingroup$ The next likely candidate $$2^{20087}\approx5^{8651}+2^{20087}(\ln2)(5.11\times10^{-5})$$ isn't really very close... the numbers are growing exponentially as $2^x$ but the relative errors tend to only decrease as $1/x$. $\endgroup$ Jan 1, 2020 at 8:20
  • 3
    $\begingroup$ Found in various AoPS forum topics according to Approach0 $\endgroup$
    – Sil
    Jan 1, 2020 at 8:45
  • 1
    $\begingroup$ @IsaacYIUMathStudio Well, that sounds reasonable enough. True, modding out by $2$ helps nothing. For what it may be worth, note that RHS is always of the form $1000k+628$ when $y>4.$ Also, we must have $x>y$ necessarily. $\endgroup$
    – Allawonder
    Jan 1, 2020 at 9:21

3 Answers 3

5
$\begingroup$

We start by changing the letters, plugging in your maximal exponents, and arriving at $$ 128 (2^x - 1) = 125 (5^y-1) \; . \; $$ We ASSUME that both $x,y \geq 1$ and get a contradiction. The main tasks are factoring $p^n - 1$ and finding the order of a prime for some target $n,$ the minimal $k$ such that $p^k \equiv 1 \pmod k$

So, order_2 of 125 is 100, where we have simply $\varphi(125) = 100.$ Thus $100|x.$

Next $$ 2^{100} - 1 = 3 \cdot 5^3 \cdot 11 \cdot 31 \cdot 41 \cdot 101 \cdot 251 \cdot 601 \cdot 1801 \cdot 4051 \cdot 8101 \cdot 268501 $$ We need $5^y \equiv 1 \pmod {268501}$ Therefore $125 | y.$ $$ 5^{125} - 1 = 2^2 \cdot 11 \cdot 71 \cdot 101 \cdot 251 \cdot 401 \cdot 3597751 \cdot 9384251 \cdot \mbox{BIG} $$ We need $2^x \equiv 1 \pmod { 9384251}$ Therefore $125 | x.$ From the beginning, we have had $100 | x.$ Put them together, Chinese Remainder Theorem, and we arrive at $$ 500 | x $$

And $$ 2^{500}-1 = (2^{100}-1)(2^{400}+2^{300}+2^{200}+2^{100}+1)$$ where $2^{100}-1$ is a multiple of $5^3$ (above) and the second factor is a multiple of $5$ because $2^{100}=16^{25}\equiv 1\bmod 5$. Thus $2^{500} - 1$ is a multiple of $5^4.$ We have gotten what we wanted, as
$ 128 (2^x - 1) = 125 (5^y-1) \; \; $ tells us that $ 125 (5^y-1)$ is divisible by $625.$ In turn, this says that $ (5^y-1)$ is divisible by $5.$ This is impossible with $y \geq 1,$ so that $y = 0,$ contradicting our hypothesis.


factor with gp-pari 

parisize = 4000000, primelimit = 500000
? factor( 2^100 -1)
%1 = 
[     3 1]

[     5 3]

[    11 1]

[    31 1]

[    41 1]

[   101 1]

[   251 1]

[   601 1]

[  1801 1]

[  4051 1]

[  8101 1]

[268501 1]

? factor( 5^125 -1)
%2 = 
[                            2 2]

[                           11 1]

[                           71 1]

[                          101 1]

[                          251 1]

[                          401 1]

[                      3597751 1]

[                      9384251 1]

[                     28707251 1]

[                4032808198751 1]

[              767186663625251 1]

[24687045214139234043375683501 1]

? factor( 2^500 -1)
%3 = 
[                     3 1]

[                     5 4]

[                    11 1]

[                    31 1]

[                    41 1]

[                   101 1]

[                   251 1]

[                   601 1]

[                  1801 1]

[                  4051 1]

[                  7001 1]

[                  8101 1]

[                 28001 1]

[                 96001 1]

[                268501 1]

[               3775501 1]

[             229668251 1]

[          269089806001 1]

[   4710883168879506001 1]

[  47970133603445383501 1][+++]
? 

$\endgroup$
5
  • $\begingroup$ We do not need to factor $2^{500}-1$ completely. Simply render $a^5-1=(a-1)(a^4+a^3+a^2+a+1)$ where $a=2^{100}$. We already have $a\equiv 1\bmod 5$ for this $a$, forcing the quartic factor to impart the additional factor of $5$ that tumbles the edifice. $\endgroup$ Jan 1, 2020 at 19:58
  • 1
    $\begingroup$ @OscarLanzi that sounds good; consider posting that as an answer, I cant say I have ever looked carefully about what simplifications might be available, better explanations,... $\endgroup$
    – Will Jagy
    Jan 1, 2020 at 20:14
  • 1
    $\begingroup$ Instead I edit your answer. $\endgroup$ Jan 1, 2020 at 20:14
  • $\begingroup$ I like your answer with computation, but is there any way to solve this problem without computation? As it used to calculate factorization of big numbers $\endgroup$
    – MafPrivate
    Jan 2, 2020 at 9:20
  • $\begingroup$ @IsaacYIUMathStudio You are welcome to find other approaches. As to your complaint, suggest you carefully read the answer by Gyumin Roh at math.stackexchange.com/questions/1551324/… After that, some of the early ones (links in the second answer) use small numbers. $\endgroup$
    – Will Jagy
    Jan 2, 2020 at 15:39
3
$\begingroup$

In case anyone wants to learn what is going on in the solution, here are my earlier examples and the person who discovered the method (answer at the first link):

http://math.stackexchange.com/questions/1551324/exponential-diophantine-equation-7y-2-3x

http://math.stackexchange.com/questions/1941354/elementary-solution-of-exponential-diophantine-equation-2x-3y-7

http://math.stackexchange.com/questions/1941354/elementary-solution-of-exponential-diophantine-equation-2x-3y-7/1942409#1942409

http://math.stackexchange.com/questions/1946621/finding-solutions-to-the-diophantine-equation-7a-3b100/1946810#1946810

http://math.stackexchange.com/questions/2100780/is-2m-1-ever-a-power-of-3-for-m-3/2100847#2100847

The diophantine equation $5\times 2^{x-4}=3^y-1$

Equation in integers $7^x-3^y=4$

Solve in $\mathbb N^{2}$ the following equation : $5^{2x}-3\cdot2^{2y}+5^{x}2^{y-1}-2^{y-1}-2\cdot5^{x}+1=0$

Solve Diophantine equation: $2^x=5^y+3$ for non-negative integers $x,y$.

$\endgroup$
3
  • $\begingroup$ Hi Will, have a nice new year! This would be a good (initializing) list for a tag exponential-diophantine-equations which I'd liked to exist since long. But the community doesn't like to have bounces to frontpage by editing tags, doesn't it? $\endgroup$ Jan 2, 2020 at 6:31
  • $\begingroup$ @GottfriedHelms I suppose they would not like putting a tag on 25 questions in ten minutes. Should be alright if spread out a bit. Also, a tag needs some explanatory text, indicating some things it is about and some things it is not about. Either one of us can do that. $\endgroup$
    – Will Jagy
    Jan 2, 2020 at 15:33
  • $\begingroup$ Will - just introduced the tag. Tagged 3 questions (the OP and first two of your list)- enough for one day... $\endgroup$ Jan 3, 2020 at 7:52
0
$\begingroup$

From WolframAlpha here we get

$$x = \frac{\log{5^y + 3}}{\log{2}}\quad\text{for}\quad 5^y\in\mathbb{Z}\quad\land\quad5^y >=-2$$ The restrictions are overkill but simply indicate $y\in\mathbb{Z}$

Applying this in a spreadsheet for $-15000\le y \le 15000$ we get only $3$ pairs.

$$(2,0)\quad (3,1)\quad (7,3)\quad$$

$\endgroup$

You must log in to answer this question.

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