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

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!

• How are you sure these are the only solutions? Reduce the equation modulo $2$ and see what happens. Jan 1, 2020 at 7:12
• @Allawonder this problem is a contest math problem. It would not consist of big number solution. Also modulo 2 is no used dude XD Jan 1, 2020 at 7:36
• 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$. Jan 1, 2020 at 8:20
• Found in various AoPS forum topics according to Approach0
– Sil
Jan 1, 2020 at 8:45
• @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. Jan 1, 2020 at 9:21

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][+++]
?


• 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. Jan 1, 2020 at 19:58
• @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,... Jan 1, 2020 at 20:14
• 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? Jan 2, 2020 at 6:31
$$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$$