HMMT 二月 2012 · 代数 · 第 8 题

英文解析

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
   Answer: 84 Let z = y + x i . Then the recursion implies that:
   n n nz = z = 1 + i,
   1 2
   z = z z .
   n n − 1 n − 2
   This implies thatz = ( z ) ,n fn 1
   th F
   2012
   where F is the n Fibonacci number ( F = F = 1). So, z = (1 + i ) . Notice thatn 1 2 2012
   (1 + i ) = 2 i.2
   Also notice that every third Fibonnaci number is even, and the rest are odd. So:
   F − 1
   2012
   z = (2 i ) (1 + i )2
   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
   F − 12
   2012
   2 mof | 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 divisibleby 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), som ≡ 3 F − 3 (mod 5) .
   2012
   The Fibonacci sequence has period 20 modulo 5, and we findm ≡ 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