IMO shortlist 1997/15 solution

38th IMO 1997 shortlist

Problem 15

If an infinite arithmetic progression of positive integers contains a square and a cube, show that it must contain a sixth power.

Solution

Let the progression be a, a+h, a+2h, ... . We use induction on h. If h=1 the result is obvious. So assume it is true for progressions with difference < h.

Let d = gcd(a,h). Put h = de. Suppose first that gcd(d,e) > 1. Let p be a prime dividing d and e. Let p^α be the highest power of p dividing a, and p^β be the highest power of p dividing h. Then we have β > α > 0. Hence the highest power of p dividing each term a+nh is p^α. But the sequence includes a square and a cube, so α must be a multiple of 6. Hence the progression a/p⁶, (a+h)/p⁶, ... also has integer terms and includes a square and a cube. But it has a smaller difference, so by induction it has a sixth power. Then the corresponding term of the original sequence is also a sixth power.

Now suppose gcd(d,e) = 1. Then e is coprime to a, and hence to y, so for some t we have ty = x mod e. Hence t⁶y⁶ = x⁶ mod e. But y³ = a mod h and hence y³ = a mod e, so y⁶ = a² mod e. Similarly, x⁶ = a³ mod e. So t⁶a² = a³ mod e. But a is coprime to e, so we can divide by a² to get t⁶ = a mod e. Hence by the binomial theorem, (t + ke)⁶ = a mod e for any integer k.

But gcd(d,e) = 1, so t + ke = 0 mod d for some integer k. Hence (t + ke)⁶ = 0 mod d. But a = 0 mod d, so (t + ke)⁶ = a mod d. Since d and e are coprime and h = de, we conclude that (t + ke)⁶ = a mod h. In other words, the progression includes a sixth power.

38th IMO shortlist 1997