IMO 1991 SL 18

Origin: BUL

Problem

Find the highest degree k of 1991 for which 1991k divides the number 199019911992 + 199219911990.

Solution

For integers a > 0, n > 0 and \alpha \geq0, we shall write a\alpha \paralleln when a\alpha | n and a\alpha+1 ∤n. Lemma. For every odd number a \geq3 and an integer n \geq0 it holds that an+1 \parallel(a + 1)an −1 and an+1 \parallel(a −1)an + 1. Proof. We shall prove the first relation by induction (the second is anal- ogous). For n = 0 the statement is obvious. Suppose that it holds for some n, i.e. that (1 + a)an = 1 + Nan+1, a ∤N. Then (1+a)an+1 = (1+Nan+1)a = 1+a\cdotNan+1+ a  N 2a2n+2 +Ma3n+3 for some integer M. Since
a  is divisible by a for a odd, we deduce that the part of the above sum behind 1 + a \cdot Nan+1 is divisible by an+3. Hence (1 + a)an+1 = 1 + N ′an+2, where a ∤N ′. It follows immediately from Lemma that 19911993 \parallel199019911992 + 1 and 19911991 \parallel199219911990 −1. Adding these two relations we obtain immediately that k = 1991 is the desired value.