Maths Olympiad Prep

Library / /14 of 35

Number theory Difficulty 5.3 AIME, harder Prove it Belarus

Find all positive integers nn such that
n=q(q2q1)=r(2r+1) n = q(q^2 - q - 1) = r(2r + 1)
for some primes qq and rr.

Solution

(Solution by V. Vityaz.) First, qrq \neq r otherwise from
q(q2q1)=r(2r+3)(1) q(q^2 - q - 1) = r(2r + 3) \quad (1)
we would have r2r1=2r+3r^2 - r - 1 = 2r + 3 which gives r=4r = 4, which is not prime.

Hence (1) implies q2q1=krq^2 - q - 1 = kr, so q2q1=krq^2 - q - 1 = kr, 2r+3=kq2r + 3 = kq. Eliminating rr we obtain
2q2(2+k2)q+3k2=0.(2) 2q^2 - (2 + k^2)q + 3k - 2 = 0. \quad (2)
The discriminant of this equation is equal to D=k4+4k224k+20D = k^4 + 4k^2 - 24k + 20 and DD must be a perfect square. Note that (k2)2<D<(k2+2)2(k^2)^2 < D < (k^2 + 2)^2 for k>5k > 5. Hence
D=(k2+1)22k224k+19=0. D = (k^2 + 1)^2 \Longleftrightarrow 2k^2 - 24k + 19 = 0.
But the last equation has no integer roots.

If k=1k = 1, then (2) becomes 2k23q+1=02k^2 - 3q + 1 = 0, q=1q = 1 which is not prime. Note that kk is odd since kr=q2q1kr = q^2 - q - 1 is odd. If k=3k = 3, then (2) has no integer solutions. If k=5k = 5, then (2) becomes 2q227q+13=02q^2 - 27q + 13 = 0, then q=13q = 13, r=31r = 31, and n=r(2r+3)=2015n = r(2r + 3) = 2015.

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.