IMO 2003 SL N7

Origin: BRA | Category: Number Theory

Problem

The sequence a0, a1, a2, . . . is defined as follows: a0 = 2, ak+1 = 2a2 k −1 for k \geq0. Prove that if an odd prime p divides an, then 2n+3 divides p2 −1.

Solution

Define the sequence xk of positive reals by ak = cosh xk (cosh is the hyperbolic cosine defined by cosh t = et+e−t ). Since cosh(2xk) = 2a2 k−1 = cosh xk+1, it follows that xk+1 = 2xk and thus xk = \lambda\cdot2k for some \lambda > 0. From the condition a0 = 2 we obtain \lambda = log(2 + \sqrt 3). Therefore an = (2 + \sqrt 3)2n + (2 − \sqrt 3)2n .

Let p be a prime number such that p | an. We distinguish the following two cases: (i) There exists an m \inZ such that m2 \equiv3 (mod p). Then we have (2 + m)2n + (2 −m)2n \equiv0 (mod p). (1) Since (2 + m)(2 −m) = 4 −m2 \equiv1 (mod p), multiplying both sides of (1) by (2 + m)2n gives (2 + m)2n+1 \equiv−1 (mod p). It follows that the multiplicative order of (2 + m) modulo p is 2n+2, or 2n+2 | p −1, which implies that 2n+3 | (p −1)(p + 1) = p2 −1. (ii) m2 \equiv3 (mod p) has no integer solutions. We will work in the algebraic extension Zp( \sqrt 3) of the field Zp. In this field \sqrt 3 plays the role of m, so as in the previous case we obtain (2 + \sqrt 3)2n+1 = −1; i.e., the order of 2 + \sqrt 3 in the multiplicative group Zp( \sqrt 3)∗is 2n+2. We cannot finish the proof as in the previous case: in fact, we would conclude only that 2n+2 divides the order p2 −1 of the group. However, it will be enough to find a u \inZp( \sqrt 3) such that u2 = 2 + \sqrt 3, since then the order of u is equal to 2n+3. Note that (1 + \sqrt 3)2 = 2(2 + \sqrt 3). Thus it is sufficient to prove that 2 is a perfect square in Zp( \sqrt 3). But we know that in this field an = 0 = 2a2 n−1 −1, and hence 2a2 n−1 = 1 which implies 1 2 = a2 n−1. This completes the proof.