Maths Olympiad Prep

Library / /1 of 10

Number theory Difficulty 8.2 Shortlist Prove it China

Given a positive integer n4n \ge 4, prove that the equation
(2x1)(5x1)=yn (2^x - 1)(5^x - 1) = y^n
has no positive integer solutions (x,y)(x, y).

Solution

We will use the well-known Lifting the Exponent Lemma (LTE), stated as follows:
Lifting the Exponent Lemma: Let pp be a prime and mm a positive integer. Let a,ba, b be integers such that pabp \nmid ab and qp(ab)q_p \mid (a-b), where qp=pq_p = p when pp is odd and q2=4q_2 = 4 when p=2p = 2. Then we have
vp(ambm)=vp(ab)+vp(m). v_p(a^m - b^m) = v_p(a - b) + v_p(m).

Assume there exist positive integers x,yx, y satisfying (2x1)(5x1)=yn(2^x - 1)(5^x - 1) = y^n. We first prove the following lemma:
Lemma: We have 2357x2 \cdot 3 \cdot 5 \cdot 7 \mid x, and for any prime pnp \le n,
vp(x)logpn. v_p(x) \ge \lfloor \log_p n \rfloor.

Proof of Lemma: From 2(5x1)2 \mid (5^x - 1) we get 2y2 \mid y. By LTE:
nnv2(y)=v2((2x1)(5x1))=v2(51)+v2(x). \begin{aligned} n \le nv_2(y) &= v_2((2^x - 1)(5^x - 1)) \\ &= v_2(5 - 1) + v_2(x). \end{aligned}
Thus v2(x)n2log2nv_2(x) \ge n - 2 \ge \lfloor \log_2 n \rfloor. In particular, 4x4 \mid x, so 352x13 \cdot 5 \mid 2^x - 1, hence 35y3 \cdot 5 \mid y. By LTE:
nnv3(y)=v3(((22)x21)((52)x21))=v3(221)+v3(x2)+v3(521)+v3(x2)=2v3(x)+2;nnv5(y)=v5(((24)x41)(5x1))=v5(241)+v5(x4)=v5(x)+1. \begin{aligned} n \le nv_3(y) &= v_3(((2^2)^{\frac{x}{2}} - 1)((5^2)^{\frac{x}{2}} - 1)) \\ &= v_3(2^2 - 1) + v_3(\frac{x}{2}) + v_3(5^2 - 1) + v_3(\frac{x}{2}) = 2v_3(x) + 2; \\ n \le nv_5(y) &= v_5(((2^4)^{\frac{x}{4}} - 1)(5^x - 1)) \\ &= v_5(2^4 - 1) + v_5(\frac{x}{4}) = v_5(x) + 1. \end{aligned}
Thus v3(x)(n2)/2log3nv_3(x) \ge (n - 2)/2 \ge \lfloor \log_3 n \rfloor, and v5(x)n1log5nv_5(x) \ge n - 1 \ge \lfloor \log_5 n \rfloor. In particular, 3x3 \mid x. Combined with 2x2 \mid x, we have 6x6 \mid x, so 7(2x1)7 \mid (2^x - 1), hence 7y7 \mid y. By LTE:
nnv7(y)=v7(((26)x61)((56)x61))=v7(261)+v7(x6)+v7(561)+v7(x6)=2v7(x)+2. \begin{aligned} n \le nv_7(y) &= v_7(((2^6)^{\frac{x}{6}} - 1)((5^6)^{\frac{x}{6}} - 1)) \\ &= v_7(2^6 - 1) + v_7(\frac{x}{6}) + v_7(5^6 - 1) + v_7(\frac{x}{6}) = 2v_7(x) + 2. \end{aligned}
Thus v7(x)(n2)/2log7nv_7(x) \ge (n - 2)/2 \ge \lfloor \log_7 n \rfloor.

If n10n \le 10, the lemma is already proved. Now assume n11n \ge 11. We proceed by induction on pp. Let pp be a prime with 11pn11 \le p \le n, and assume the lemma holds for all primes q<pq < p. By induction hypothesis, for any prime qp1q \le p-1,
vq(x)logqnlogq(p1)vq(p1). v_q(x) \ge \lfloor \log_q n \rfloor \ge \lfloor \log_q (p-1) \rfloor \ge v_q(p-1).
Thus (p1)x(p-1) \mid x. By Fermat's Little Theorem, p(2p11)p \mid (2^{p-1}-1) and p(5p11)p \mid (5^{p-1}-1). Hence p(2x1)p \mid (2^x - 1) and pyp \mid y. By LTE:
nnvp(y)=vp(((2p1)xp11)((5p1)xp11))=vp(2p11)+vp(xp1)+vp(5p11)+vp(xp1)=2vp(x)+vp(2p11)+vp(5p11)<2vp(x)+logp(2p1)+logp(5p1)<2vp(x)+plogp(10). \begin{align*} n \le nv_p(y) &= v_p\left(((2^{p-1})^{\frac{x}{p-1}} - 1)((5^{p-1})^{\frac{x}{p-1}} - 1)\right) \\ &= v_p(2^{p-1} - 1) + v_p\left(\frac{x}{p-1}\right) + v_p(5^{p-1} - 1) + v_p\left(\frac{x}{p-1}\right) \\ &= 2v_p(x) + v_p(2^{p-1} - 1) + v_p(5^{p-1} - 1) \\ &< 2v_p(x) + \log_p(2^{p-1}) + \log_p(5^{p-1}) \\ &< 2v_p(x) + p \log_p(10). \end{align*}
Therefore,
vp(x)>nplogp(10)2. v_p(x) > \frac{n - p \log_p(10)}{2}.
Since 11pn11 \le p \le n, this implies vp(x)>0v_p(x) > 0, so vp(x)1v_p(x) \ge 1. If n<p2n < p^2, then vp(x)1logpnv_p(x) \ge 1 \ge \lfloor \log_p n \rfloor. To complete the induction, we only need to prove for np2112n \ge p^2 \ge 11^2 that
nplogp(10)2>logpn. \frac{n - p \log_p(10)}{2} > \log_p n.
This is equivalent to
pn10p>n2. \frac{p^n}{10^p} > n^2.
Indeed, using np2112n \ge p^2 \ge 11^2, we have
pn10p=pp10ppnp>11nn>9n2>n2. \frac{p^n}{10^p} = \frac{p^p}{10^p} \cdot p^{n-p} > 11^{n-\sqrt{n}} > 9^{\frac{n}{2}} > n^2.
This completes the induction. The lemma is proved.

Proof of the Main Result: By the lemma, for any prime pnp \le n,
vp(x)logpnvp(n). v_p(x) \ge \lfloor \log_p n \rfloor \ge v_p(n).
Thus nxn \mid x. Let x=nx1x = nx_1, then
yn=(2x1)(5x1)<(10x1)n. y^n = (2^x - 1)(5^x - 1) < (10^{x_1})^n.
Hence 10x1y+110^{x_1} \ge y + 1. Therefore,
yn=(10x1)n2x5x+1(y+1)n2x5x+1>yn+nyn125xyn+4y3n425x. \begin{align*} y^n &= (10^{x_1})^n - 2^x - 5^x + 1 \\ &\ge (y+1)^n - 2^x - 5^x + 1 \\ &> y^n + n \cdot y^{n-1} - 2 \cdot 5^x \\ &\ge y^n + 4 \cdot y^{\frac{3n}{4}} - 2 \cdot 5^x. \end{align*}

This implies y3n4<5xy^{\frac{3n}{4}} < 5^x, i.e., yn<54x3y^n < 5^{\frac{4x}{3}}. On the other hand, by the lemma we have x2357x \ge 2 \cdot 3 \cdot 5 \cdot 7, so
yn=(2x1)(5x1)>(0.92x)(0.95x)>0.852x55x>54x3, y^n = (2^x - 1)(5^x - 1) > (0.9 \cdot 2^x) \cdot (0.9 \cdot 5^x) > 0.8 \cdot 5^{\frac{2x}{5}} \cdot 5^x > 5^{\frac{4x}{3}},
a contradiction.
Therefore, the original Diophantine equation has no positive integer solutions. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.