HMMT 二月 2012 · 代数 · 第 8 题

HMMT February 2012 — Algebra — Problem 8

Let x = y = x = y = 1, then for n ≥ 3 let x = x y + x y and y = y y − 1 1 2 2 n n − 1 n − 2 n − 2 n − 1 n n − 1 n − 2 x x . What are the last two digits of | x | ? n − 1 n − 2 2012 4 3 2

解析

Let x = y = x = y = 1, then for n ≥ 3 let x = x y + x y and y = y y − 1 1 2 2 n n − 1 n − 2 n − 2 n − 1 n n − 1 n − 2 x x . What are the last two digits of | x | ? n − 1 n − 2 2012 Answer: 84 Let z = y + x i . Then the recursion implies that: n n n z = z = 1 + i, 1 2 z = z z . n n − 1 n − 2 This implies that F n z = ( z ) , n 1 th F 2012 where F is the n Fibonacci number ( F = F = 1). So, z = (1 + i ) . Notice that n 1 2 2012 2 (1 + i ) = 2 i. Also notice that every third Fibonnaci number is even, and the rest are odd. So: F − 1 2012 2 z = (2 i ) (1 + i ) 2012 Algebra Test F − 1 2012 Let m = . Since both real and imaginary parts of 1 + i are 1, it follows that the last two digits 2 F − 1 2012 m 2 of | x | are simply the last two digits of 2 = 2 . 2012 m m By the Chinese Remainder Theorem, it suffices to evaluate 2 modulo 4 and 25. Clearly, 2 is divisible by 4. To evaluate it modulo 25, it suffices by Euler’s Totient theorem to evaluate m modulo 20. To determine ( F − 1) / 2 modulo 4 it suffices to determine F modulo 8. The Fibonacci sequence 2012 2012 has period 12 modulo 8, and we find F ≡ 5 (mod 8) , 2012 m ≡ 2 (mod 4) . 2 ∗ 3 ≡ 1 (mod 5), so m ≡ 3 F − 3 (mod 5) . 2012 The Fibonacci sequence has period 20 modulo 5, and we find m ≡ 4 (mod 5) . Combining, m ≡ 14 (mod 20) m 14 2 ≡ 2 = 4096 ≡ 21 (mod 25) | x | ≡ 4 · 21 = 84 (mod 100) . 2012 4 3 2