IMO 1989 SL 27

Origin: ROM

Problem

Let m be a positive odd integer, m \geq2. Find the smallest positive integer n such that 21989 divides mn −1.

Solution

Let n be the required exponent, and suppose n = 2kq, where q is an odd integer. Then we have mn −1 = (m2k −1)[(m2k(q−1) + \cdot \cdot \cdot + m2k + 1] = (m2k −1)A, where A is odd. Therefore mn −1 and m2k −1 are divisible by the same power of 2, and so n = 2k. Next, we observe that m2k −1 = (m2k−1 −1)(m2k−1 + 1) = . . . = (m2 −1)(m2 + 1)(m4 + 1) \cdot \cdot \cdot (m2k−1 + 1). Let s be the maximal positive integer for which m \equiv\pm1 (mod 2s). Then m2 −1 is divisible by 2s+1 and not divisible by 2s+2. All the numbers m2 + 1, m4 + 1, . . . , m2k−1 + 1 are divisible by 2 and not by 4. Hence m2k −1 is divisible by 2s+k and not by 2s+k+1. It follows from the above consideration that the smallest exponent n equals 21989−s if s \leq1989, and n = 1 if s > 1989.