IMO 1994 SL N6

Origin: LAT | Category: Number Theory

Problem

Let x1 and x2 be relatively prime positive integers. For n \geq2, define xn+1 = xnxn−1 + 1. (a) Prove that for every i > 1, there exists j > i such that xi i divides xj j. (b) Is it true that x1 must divide xj j for some j > 1?

Solution

(a) Let p be a prime divisor of xi, i > 1, and let xj \equivuj (mod p) where 0 \lequj \leqp −1 (particularly ui \equiv0). Then uj+1 \equivujuj−1 + 1 (mod p). The number of possible pairs (uj, uj+1) is finite, so uj is eventually periodic. We claim that for some dp > 0, ui+dp = 0. Indeed, suppose the contrary and let (um, um+1, . . . , um+d−1) be the first period for m \geqi. Then m ̸= i. By the assumption um−1 ̸\equiv um+d−1, but um−1um \equivum+1 −1 \equivum+d+1 −1 \equivum+d−1um+d \equiv um+d−1um (mod p), which is impossible if p ∤um. Hence there is a dp with ui = ui+dp = 0 and moreover ui+1 = ui+dp+1 = 1, so the sequence uj is periodic with period dp starting from ui. Let m be the least common multiple of all dp’s, where p goes through all prime divisors of xi. Then the same primes divide every xi+km, k = 1, 2, . . . , so for large enough k and j = i + km, xi i | xj j. (b) If i = 1, we cannot deduce that xi+1 \equiv1 (mod p). The following ex- ample shows that the statement from (a) need not be true in this case. Take x1 = 22 and x2 = 9. Then xn is even if and only if n \equiv1 (mod 3), but modulo 11 the sequence {xn} is 0, 9, 1, 10, 0, 1, 1, 2, 3, 7, 0, . . ., so 11 | xn (n > 1) if and only if n \equiv5 (mod 6). Thus for no n > 1 can we have 22 | xn.