IMO 1974 SL 6

Problem

I 6 (ROM 4)IMO3 Does there exist a natural number n for which the number n  k=0 2n + 1 2k + 1  23k is divisible by 5?

Solution

We set x = n  k=0 2n + 1 2k + 1  23k = \sqrt n  k=0 2n + 1 2k + 1 \sqrt 2k+1, y = n  k=0 2n + 1 2k  23k = n  k=0 2n + 1 2k \sqrt 2k. Both x and y are positive integers. Also, from the binomial formula we obtain y + x \sqrt 8 = 2n+1  i=0 2n + 1 i \sqrt i = (1 + \sqrt 8)2n+1, and similarly y −x \sqrt 8 = (1 − \sqrt 8)2n+1. Multiplying these equalities, we get y2−8x2 = (1+ \sqrt 8)2n+1(1− \sqrt 8)2n+1 = −72n+1. Reducing modulo 5 gives us 3x2 −y2 \equiv22n+1 \equiv2 \cdot (−1)n.

Now we see that if x is divisible by 5, then y2 \equiv\pm2 (mod 5), which is impossible. Therefore x is never divisible by 5. Second solution. Another standard way is considering recurrent formulas. If we set xm =  k  m 2k + 1  8k, ym =  k m 2k  8k, then since
a b 

a−1 b  +
a−1 b−1  , it follows that xm+1 = xm + ym and ym+1 = 8xm +ym; therefore xm+1 = 2xm + 7xm−1. We need to show that none of x2n+1 are divisible by 5. Considering the sequence {xm} modulo 5, we get that xm = 0, 1, 2, 1, 1, 4, 0, 3, 1, 3, 3, 2, 0, 4, 3, 4, 4, 1, . . . . Zeros occur in the initial position of blocks of length 6, where each subsequent block is obtained by multiplying the previous one by 3 (modulo 5). Consequently, xm is divisible by 5 if and only if m is a multiple of 6, which cannot happen if m = 2n + 1.