IMO 1997 SL 15

Origin: RUS

Problem

An infinite arithmetic progression whose terms are positive in- tegers contains the square of an integer and the cube of an integer. Show that it contains the sixth power of an integer.

Solution

Let a + bt, t = 0, 1, 2, . . ., be a given arithmetic progression that contains a square and a cube (a, b > 0). We use induction on the progression step b to prove that the progression contains a sixth power. (i) b = 1: this case is trivial. (ii) b = pm for some prime p and m > 0. The case pm | a trivially reduces to the previous case, so let us have pm ∤a. Suppose that gcd(a, p) = 1. If x, y are integers such that x2 \equivy3 \equiva (here all the congruences will be mod pm), then x6 \equiva3 and y6 \equiva2. Consider an integer y1 such that yy1 \equiv1. It satisfies a2(xy1)6 \equiv

x6y6y6 1 \equivx6 \equiva3, and consequently (xy1)6 \equiva. Hence a sixth power exists in the progression. If gcd(a, p) > 1, we can write a = pkc, where k < m and p ∤c. Since the arithmetic progression xt = a + bt = pk(c + pm−kt) contains a square, k must be even; similarly, it contains a cube, so 3 | k. It follows that 6 | k. The progression c + pm−kt thus also contains a square and a cube; hence by the previous case it contains a sixth power and thus xt does also. (iii) b is not a power of a prime, and thus can be expressed as b = b1b2, where b1, b2 > 1 and gcd(b1, b2) = 1. It is given that progressions a + b1t and a + b2t both contain a square and a cube, and therefore by the inductive hypothesis they both contain sixth powers: say z6 and z6 2, respectively. By the Chinese remainder theorem, there exists z \inN such that z \equivz1 (mod b1) and z \equivz2 (mod b2). But then z6 belongs to both of the progressions a + b1t and a + b2t. Hence z6 is a member of the progression a + bt.