Olympiad Maths Prep

Library / /26 of 29

Number theory Difficulty 5.6 AIME, harder Prove it Ukraine

Find all prime numbers pp, qq, rr, such that:
p(p+1)+q(q+1)=r(r+1). p(p+1) + q(q+1) = r(r+1).

Solution

WLOG, pqp \le q, clearly r>pr > p. We can write:
p(p+1)=(rq)(r+q+1).(1) p(p+1) = (r-q)(r+q+1). \quad (1)
Since pp is prime, then either rqr-q or r+q+1r+q+1 is divisible by pp. If pp divides rqr-q, then rqpr-q \ge p,
p(p+1)(rq)(rq+1)<(rq)(r+q+1), p(p+1) \le (r-q)(r-q+1) < (r-q)(r+q+1),
which contradicts to (1).

Let suppose that r+q+1r+q+1 is divisible by pp. If p=2p=2, then r+q+1r+q+1 has to be even, which implies that rr is odd, hence qq is even, thus q=2q=2 and r=3r=3.

If p>2p > 2, let r+q+1=kpr+q+1 = kp. Then rr and qq are odd and kk is odd, k>1k > 1. Then p+1=k(rq)p+1 = k(r-q) and we get k2(rq)=kp+kk^2(r-q) = kp+k or r+q+1+k=k2rk2qr+q+1+k = k^2r-k^2q which is equivalent to
(k2+1)q=(k21)r(k+1). (k^2+1)q = (k^2-1)r - (k+1).
RHS is divisible by (k+1)(k+1), thus LHS is divisible by the same number, since kk is odd, then k2+12\frac{k^2+1}{2} is divisible by k+12\frac{k+1}{2}. Observe, that
(k2+12,k+12)=(k2+12(k1)(k+1)2,k+12)=(1,k+12)=1. \left(\frac{k^2+1}{2}, \frac{k+1}{2}\right) = \left(\frac{k^2+1}{2} - \frac{(k-1)(k+1)}{2}, \frac{k+1}{2}\right) = \left(1, \frac{k+1}{2}\right) = 1.
k2+12\frac{k^2+1}{2} and k+12\frac{k+1}{2} are coprime, so k+12\frac{k+1}{2} is divisible by qq and since k>1k > 1, then k+12>1\frac{k+1}{2} > 1 and q=k+12q = \frac{k+1}{2}.

We get r=kpq1r = kp - q - 1 and q=k+12q = \frac{k+1}{2}. Plugging in this into p+1=k(rq)p+1 = k(r-q) we get p+1=(kpk2)kp+1 = (kp - k - 2)k. But the last equality is impossible because k3k \ge 3, p3p \ge 3 implies
(kpk2)k>kpk2=k(p1)23(p1)2=p+(2p5)p+1. (kp - k - 2)k > kp - k - 2 = k(p-1) - 2 \ge 3(p-1) - 2 = p + (2p-5) \ge p+1.
This completes the proof.

Looking for a route rather than 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.