Maths Olympiad Prep

Library / /153 of 397

Number theory Difficulty 5.6 AIME, harder Prove it Taiwan

Find all pairs of non-negative integers (m,n)(m, n) satisfying the following equation:
m2+23n=m(2n+11). m^2 + 2 \cdot 3^n = m(2^{n+1} - 1).

Solution

(6, 3), (9, 3), (9, 5) and (54, 5).

Note that when nn is fixed, this is a quadratic equation in mm; the condition for mm to have an integer solution is that the discriminant is a perfect square. Solving the quadratic equations for n=0,1,2,3,4,5n = 0, 1, 2, 3, 4, 5 shows that for n5n \le 5 there are exactly the four solutions described above. Below we prove that there are no solutions for n6n \ge 6.

Suppose (m,n)(m, n) satisfies the equation of this problem and n6n \ge 6, then m23n=m(2n+1m1)m|2 \cdot 3^n = m(2^{n+1}-m-1),
so mm can be written as m=3pm = 3^p or m=23qm = 2 \cdot 3^q.

In the first case, let q=npq = n - p, we have
2n+11=m+23nm=3p+23q. 2^{n+1} - 1 = m + \frac{2 \cdot 3^n}{m} = 3^p + 2 \cdot 3^q.
In the second case, let p=nqp = n - q, we have
2n+11=m+23nm=23q+3p. 2^{n+1} - 1 = m + \frac{2 \cdot 3^n}{m} = 2 \cdot 3^q + 3^p.
Thus in either case we have 2n+11=3p+23q2^{n+1} - 1 = 3^p + 2 \cdot 3^q, with 0p,qn,p+q=n0 \le p, q \le n, p + q = n.

Now we estimate the range of p,qp, q, consider
3p<2n+1=8n+13<9n+13=32(n+1)3 3^p < 2^{n+1} = 8^{\frac{n+1}{3}} < 9^{\frac{n+1}{3}} = 3^{\frac{2(n+1)}{3}}
Similarly we have 23q<32(n+1)32 \cdot 3^q < 3^{\frac{2(n+1)}{3}}, so p,q<2(n+1)3p, q < \frac{2(n+1)}{3}. From p+q=np+q = n we also obtain p,q>n23p, q > \frac{n-2}{3}.

Let h=min(p,q)h = \min(p, q), we have 3h3p+23q=2n+113^h|3^p+2 \cdot 3^q = 2^{n+1}-1. Then since h>n23>1h > \frac{n-2}{3} > 1,
2n+112^{n+1}-1 is a multiple of 9. It is easy to deduce that in this case 6n+16|n+1.

Therefore we may write n+1=6rn + 1 = 6r. Then we have
2n+11=43r1=(42r+4r+1)(2r+1)(2r1). 2^{n+1} - 1 = 4^{3r} - 1 = (4^{2r} + 4^r + 1)(2^r + 1)(2^r - 1).
Note that 42r+4r+1=(4r1)2+34r4^{2r} + 4^r + 1 = (4^r - 1)^2 + 3 \cdot 4^r is certainly a multiple of 3 but certainly not a multiple of 9. Also 2r+12^r + 1 and 2r12^r - 1 differ by 2, so only one of them can be a multiple of 3. Whichever one it is, it must be divisible by 3h13^{h-1}. In either case, we have
3h12r+13r 3^{h-1} \le 2^r + 1 \le 3^r
hence h1rh - 1 \le r. But earlier we had h>n23h > \frac{n-2}{3}, and r=n+16r = \frac{n+1}{6}, from which it clearly follows that n<11n < 11. This contradicts 6n+16|n+1 and n6n \ge 6, so there are no solutions for n6n \ge 6.

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 translated into English from the original; metadata (topic, difficulty) added by this project.