IMO shortlist 1994/N6 solution

35th IMO 1994 shortlist

Problem N6

Define the sequence a₁, a₂, a₃, ... as follows. a₁ and a₂ are coprime positive integers and a_n+2 = a_n+1a_n + 1. Show that for every m > 1 there is an n > m such that a_m^m divides a_nⁿ. Is it true that a₁ must divide a_nⁿ for some n > 1?

Solution

Answer: no.

Let p be any prime divisor of a_i. Let u_n be the residue of a_n mod p. So u_n+2 = u_n+1u_n mod p. Since there are only finitely many pairs (u_n+1, u_n), the sequence u_n must be eventually periodic. We claim that it is periodic from n = i. Suppose not, so that the first two periods are u_s, u_s+1, ... , u_s+t-1 (first complete period), u_s+t, ... , u_s+2t-1 (second complete period) with s > i as small as possible and all terms in the periods not equal to u_i and hence non-zero. Then u_su_s-1 = u_s+1 - 1 = u_s+1+t - 1 = u_s+tu_s+t-1. But since u_s = u_s+t is non-zero, we may divide to get u_s-1 = u_s-1+t. So it is periodic from s-1, contradicting the minimality of s. So for some integer k(p) we have u_{i+n k(p)} = 0 for all n.

Now take all the primes p that divide a_i and let m be the lcm of the corresponding k(p). Then u_i+nm = 0 for all n and p, so every prime dividing a_i divides a_i+nm for n = 1, 2, 3, ... . Let the highest exponent of any prime p that divides a_i be r. Take n sufficiently large so that i + nm > ri. Then a_iⁱ divides a_i+nm^i+nm.

Take a₁ = 22, a₂ = 9. We find that the sequence u_n for the prime 2 is 0, 1, 1, 0, 1, 1, ... so a_n is even iff n = 1 mod 3. For the prime 11 the sequence is 0, 9, 1, 10, 0, 1, 1, 2, 3, 7, 0, ... so for n > 1, a_n is divisible by 11 iff n = 5 mod 6. But we cannot have n = 1 mod 3 and 5 mod 6, so there is no j > 1 with a₁ dividing a_j^j.

35th IMO shortlist 1994