IMO 1988 SL 7

Origin: FRA

Problem

Let a be the greatest positive root of the equation x3−3x2+1 = 0. Show that [a1788] and [a1988] are both divisible by 17. ([x] denotes the integer part of x.)

Solution

The algebraic equation x3 −3x2 + 1 = 0 admits three real roots \beta, \gamma, a, with −0.6 < \beta < −0.5, 0.6 < \gamma < 0.7, \sqrt 8 < a < 3. Define, for all integers n, un = \betan + \gamman + an. It holds that un+3 = 3un+2 −un. Obviously, 0 < \betan +\gamman < 1 for all n \geq2, and we see that un −1 = [an] for n \geq2. It is now a question whether u1788 −1 and u1988 −1 are divisible by 17. Working modulo 17, we get u0 \equiv3, u1 \equiv3, u2 \equiv9, u3 \equiv7, u4 \equiv 1, . . . , u16 = 3, u17 = 3, u18 = 9. Thus, un is periodic modulo 17, with period 16. Since 1788 = 16 \cdot 111 + 12, 1988 = 16 \cdot 124 + 4, it follows that u1788 \equivu12 \equiv1 and u1988 \equivu4 = 1. So, [a1788] and [a1988] are divisible by 17. Second solution. The polynomial x3 −3x2 + 1 allows the factorization modulo 17 as (x −4)(x −5)(x + 6). Hence it is easily seen that un \equiv 4n + 5n + (−6)n. Fermat’s theorem gives us 4n \equiv5n \equiv(−6)n \equiv1 for 16 | n, and the rest follows easily. Remark. In fact, the roots of x3 −3x2 + 1 = 0 are 2 sin 10◦, 2 sin 50◦, and − 2 sin 70◦.