IMO 1999 SL N3

Origin: RUS | Category: Number Theory

Problem

Prove that there exist two strictly increasing sequences (an) and (bn) such that an(an + 1) divides b2 n + 1 for every natural number n.

Solution

We first prove the following lemma. Lemma. For d, c \inN and d2 | c2 + 1 there exists b \inN such that d2(d2 + 1) | b2 + 1. Proof. It is enough to set b = c + d2c −d3 = c + d2(c −d).

Using the lemma it suffices to find increasing sequences dn and cn such that cn−dn is an increasing sequence and d2 n | c2 n+1. We then obtain the desired sequences an and bn from an = d2 n and bn = cn + d2 n(cn −dn). It is easy to check that dn = 22n + 1 and cn = 2ndn satisfy the required conditions. Hence we have demonstrated the existence of increasing sequences an and bn such that an(an + 1) | b2 n + 1. Remark. There are many solutions to this problem. For example, it is sufficient to prove that the Pell-type equation 5an(an + 1) = b2 n + 1 has an infinity of solutions in positive integers. Alternatively, one can show that an(an + 1) can be represented as a sum of two coprime squares for infinitely many an, which implies the existence of bn.