### 29th IMO 1988 shortlist

Problem 7

c is the largest positive root of x3 - 3x2 + 1. Show that [c1788] and [c1988] are multiples of 17.

Solution

Put f(x) = x3 - 3x2 + 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|n < |b|n. But b > 0, so an + bn > 0. Finally, a2 + b2 = (a + b)2 - 2ab = (3 - c)2 + 2/c = 9 - 6c + c2 + 2/c. But c3 - 3c + 1 = 0, so -6c + c2 + 2/c = -c2. Hence a2 + b2 = 9 - c2 < 1. Hence an + bn < 1 for all n > 1.

Put un = an + bn + cn. Then u0 = 3, u1 = 3, u2 = (a + b + c)2 - 2(ab + bc + ca) = 9 and un+3 = 3un+2 - un. Hence un is an integer for all n. Hence [cn] = un - 1.

Working mod 17, we have u0 = 3, u1 = 3, u2 = 9. Hence u3 = 3·9 - 3 = 7, u4 = 3·7 - 3 = 1, u5 = 3·1 - 9 = 11, u6 = 3·11 - 7 = 9, u7 = 3·9 - 1 = 9, u8 = 3·9 - 11 = -1, u9 = -3·1 - 9 = 5, u10 =3·5 - 9 = 6, u11 = 3·6 + 1 = 2, u12 = 3·2 - 5 = 1, u13 = 3·1 - 6 = -3, u14 = -3·3 - 2 = 6, u15 = 3·6 - 1 = 0, u16 = 3·0 + 3 = 3, u17 = 3·3 - 6 = 3, u18 = 3·3 - 0 = 9. Hence un = un+16 mod 17 for n = 0, 1, 2. So the recurrence relation implies that un = un+16 mod 17 for all n, and hence that un = um mod 17 if n = m mod 16. Hence, in particular, u1788 = u12 = 1 mod 17, and u1988 = u4 = 1 mod 17. Hence [c1788] and [c1988] are divisible by 17.