29th IMO shortlist 1988/7 solution

29th IMO 1988 shortlist

Problem 7

c is the largest positive root of x³ - 3x² + 1. Show that [c¹⁷⁸⁸] and [c¹⁹⁸⁸] are multiples of 17.

Solution

Put f(x) = x³ - 3x² + 1. Let the roots be a < b < c. We have f(-1) = -3, f(-½) = 1/8, f(½) = 3/8, f(1) = -1, f(2√2) = 16√2 - 23 < 0, f(3) = 1. Hence -1 < a < -½, ½ < b < 1, 2√2 < c < 3. Hence |a|, |b| < 1. Also a + b + c = 3, so a + b = 3 - c > 0, so |a| < |b|. Hence |a|ⁿ < |b|ⁿ. But b > 0, so aⁿ + bⁿ > 0. Finally, a² + b² = (a + b)² - 2ab = (3 - c)² + 2/c = 9 - 6c + c² + 2/c. But c³ - 3c + 1 = 0, so -6c + c² + 2/c = -c². Hence a² + b² = 9 - c² < 1. Hence aⁿ + bⁿ < 1 for all n > 1.

Put u_n = aⁿ + bⁿ + cⁿ. Then u₀ = 3, u₁ = 3, u₂ = (a + b + c)² - 2(ab + bc + ca) = 9 and u_n+3 = 3u_n+2 - u_n. Hence u_n is an integer for all n. Hence [cⁿ] = u_n - 1.

Working mod 17, we have u₀ = 3, u₁ = 3, u₂ = 9. Hence u₃ = 3·9 - 3 = 7, u₄ = 3·7 - 3 = 1, u₅ = 3·1 - 9 = 11, u₆ = 3·11 - 7 = 9, u₇ = 3·9 - 1 = 9, u₈ = 3·9 - 11 = -1, u₉ = -3·1 - 9 = 5, u₁₀ =3·5 - 9 = 6, u₁₁ = 3·6 + 1 = 2, u₁₂ = 3·2 - 5 = 1, u₁₃ = 3·1 - 6 = -3, u₁₄ = -3·3 - 2 = 6, u₁₅ = 3·6 - 1 = 0, u₁₆ = 3·0 + 3 = 3, u₁₇ = 3·3 - 6 = 3, u₁₈ = 3·3 - 0 = 9. Hence u_n = u_n+16 mod 17 for n = 0, 1, 2. So the recurrence relation implies that u_n = u_n+16 mod 17 for all n, and hence that u_n = u_m mod 17 if n = m mod 16. Hence, in particular, u₁₇₈₈ = u₁₂ = 1 mod 17, and u₁₉₈₈ = u₄ = 1 mod 17. Hence [c¹⁷⁸⁸] and [c¹⁹⁸⁸] are divisible by 17.

29th IMO shortlist 1988