Maths Olympiad Prep

Library / /85 of 106

, 2022

Number theory Difficulty 8.4 Shortlist Prove it China

Find all prime numbers pp and positive integers a,b,ca, b, c such that
2apb=(p+2)c+1. 2^a p^b = (p + 2)^c + 1.

Solution

Obviously, pp is odd, so p3p \ge 3. If c=1c = 1, then
p+3=2apb2pp+3, p + 3 = 2^a p^b \ge 2p \ge p + 3,
This can only happen when p=3p = 3, a=b=1a = b = 1, giving one solution (p,a,b,c)=(3,1,1,1)(p, a, b, c) = (3, 1, 1, 1). In what follows, we assume that c2c \ge 2.

Case 1: cc is odd. Assume that qq is a prime factor of cc. Since (p+2)q+1(p+2)c+1(p+2)^q+1 \mid (p+2)^c+1,
(p+2)q+1=2αpβ.(1) (p + 2)^q + 1 = 2^\alpha p^\beta. \qquad (1)
Obviously, α>0\alpha > 0. Note that (p+2)q+1=(p+3)A(p+2)^q + 1 = (p+3)A, where
A=(p+2)q1(p+2)q2++1>(p+2)q1(p+2)q2=(p+2)q2(p+1)>pq1, A = (p+2)^{q-1} - (p+2)^{q-2} + \cdots + 1 > (p+2)^{q-1} - (p+2)^{q-2} = (p+2)^{q-2}(p+1) > p^{q-1},
and AA is odd, so AA is a power of pp. So ApqA \ge p^q and βq\beta \ge q. Taking both sides of (1) modulo pp gives 2q1(modp)2^q \equiv -1 \pmod p, so the order of 2(modp)2 \pmod p is 2 or 2q2q.

If the order of 2(modp)2 \pmod p is 2, then p=3p = 3. In this case, (1)(1) is 5q+1=2α3β5^q + 1 = 2^\alpha 3^\beta. Since 5q+12(mod4)5^q + 1 \equiv 2 \pmod 4, we have α=1\alpha = 1. By Lifting-the-exponent Lemma, v3(5q+1)=v3(5+1)+v3(q)2v_3(5^q + 1) = v_3(5+1) + v_3(q) \le 2, so β2\beta \le 2. One checks that β=1,2\beta = 1, 2 does not satisfy the equation.

If the order of 2(modp)2 \pmod p is 2q2q, then 2qp12q \mid p-1. So qp12<p2q \le \frac{p-1}{2} < \frac{p}{2}. Dividing both sides of (1) by pqp^q and using (1+1x)x<e(1+\frac{1}{x})^x < e, x1x \ge 1, we have
2αpβq=(1+2p)q+pq<(1+2p)p2+pq<e+33<3. 2^\alpha p^{\beta-q} = \left(1 + \frac{2}{p}\right)^q + p^{-q} < \left(1 + \frac{2}{p}\right)^{\frac{p}{2}} + p^{-q} < e + 3^{-3} < 3.
So β=q\beta = q and α=1\alpha = 1. Using 2pq=(p+2)q+1=(p+3)A2 \cdot p^q = (p+2)^q + 1 = (p+3)A, we get A=pqA = p^q and p+3=2p+3=2. This is a contradiction.

Case 2: cc is even. Assume that 2dc2^d \nmid c with d1d \ge 1. Then (p+2)2d+1(p+2)c+1(p+2)^{2d} + 1 \mid (p+2)^c + 1. So
(p+2)2d+1=2αpβ. (p + 2)^{2d} + 1 = 2^\alpha p^\beta.
Since (p+2)2d+12(mod4)(p+2)^{2d} + 1 \equiv 2 \pmod 4, α=1\alpha = 1.
(p+2)2d+1=2pβ.(2) (p + 2)^{2d} + 1 = 2 \cdot p^{\beta}. \qquad (2)
Taking both sides of (2) modulo pp gives 22d1(modp)2^{2d} \equiv -1 \pmod p. So the order of 2(modp)2 \pmod p is 2d+12^{d+1}. Thus, 2d<p22^d < \frac{p}{2}. Since
pβ+1>2pβ=(p+2)2d+1>p2d, p^{\beta+1} > 2 \cdot p^{\beta} = (p+2)^{2d} + 1 > p^{2d},
we have β2d\beta \ge 2^d. Dividing both sides of (2) by p2dp^{2^d}, we have
2pβ2d=(1+2p)2d+p2d<(1+2p)p2+p2d<e+32<3, 2 \cdot p^{\beta-2^d} = \left(1 + \frac{2}{p}\right)^{2^d} + p^{-2^d} < \left(1 + \frac{2}{p}\right)^{\frac{p}{2}} + p^{-2^d} < e + 3^{-2} < 3,
so β=2d\beta = 2^d.

If d2d \ge 2, then 2d+1p12^{d+1} \mid p-1 implies that p1(mod8)p \equiv 1 \pmod 8. Using (2), we have p2d1=(p+2)2dp2dp^{2^d} - 1 = (p+2)^{2^d} - p^{2^d}. Analyzing the number of factors 2 on both sides of the equality, we deduce that
v2(p2d1)=v2(p21)+d1d+3. v_2(p^{2^d} - 1) = v_2(p^2 - 1) + d - 1 \ge d + 3.
Yet,
v2((p+2)2dp2d)=v2((p+2)2p2)+d1=v2(2)+v2(2p+2)+d1=d+2, v_2((p+2)^{2^d} - p^{2^d}) = v_2((p+2)^2 - p^2) + d - 1 = v_2(2) + v_2(2p+2) + d - 1 = d + 2,
giving a contradiction. So d=1d=1 and 2p2=(p+2)2+12p^2 = (p+2)^2 + 1, which implies that p=5p=5. Going back to the original equation, we have c=2kc = 2k, with kk odd. But a=1a=1, so we have
25b=72k+1. 2 \cdot 5^b = 7^{2k} + 1.
Using Lifting-the-exponent Lemma again, we have b=v5(72k+1)=v5(72+1)+v5(k)2+k5b = v_5(7^{2k} + 1) = v_5(7^2 + 1) + v_5(k) \le 2 + \frac{k}{5}. If k3k \ge 3, then
25b252+k5=(72+1)5k5<72k+1, 2 \cdot 5^b \le 2 \cdot 5^{2+\frac{k}{5}} = (7^2 + 1) \cdot 5^{\frac{k}{5}} < 7^{2k} + 1,
giving a contradiction. So k=1k=1, and thus c=2c=2 and b=2b=2. This gives another solution (p,a,b,c)=(5,1,2,2)(p, a, b, c) = (5, 1, 2, 2).

To sum up, there are two solutions of (p,a,b,c)(p, a, b, c): (3,1,1,1)(3, 1, 1, 1) and (5,1,2,2)(5, 1, 2, 2).

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 reproduced verbatim; metadata (topic, difficulty) added by this project.