Let x1=y1=x2=y2=1, then for n≥3 let xn=xn−1yn−2+xn−2yn−1 and yn=yn−1yn−2−xn−1xn−2. What are the last two digits of ∣x2012∣ ?
A number or a short expression. Spacing and $ signs are ignored.
Solution
Let zn=yn+xni. Then the recursion implies that: z1=z2=1+izn=zn−1zn−2 This implies that zn=(z1)Fn where Fn is the nth Fibonacci number (F1=F2=1). So, z2012=(1+i)F2012. Notice that (1+i)2=2i Also notice that every third Fibonnaci number is even, and the rest are odd. So: z2012=(2i)2F2012−1(1+i) Let m=2F2012−1. Since both real and imaginary parts of 1+i are 1 , it follows that the last two digits of ∣x2012∣ are simply the last two digits of 2m=22F2012−1. By the Chinese Remainder Theorem, it suffices to evaluate 2m modulo 4 and 25 . Clearly, 2m is divisible by 4 . To evaluate it modulo 25, it suffices by Euler's Totient theorem to evaluate m modulo 20. To determine (F2012−1)/2 modulo 4 it suffices to determine F2012 modulo 8. The Fibonacci sequence has period 12 modulo 8 , and we find F2012m≡5(mod8)≡2(mod4)2∗3≡1(mod5), so m≡3F2012−3(mod5) The Fibonacci sequence has period 20 modulo 5 , and we find m≡4(mod5) Combining, m2m∣x2012∣≡14(mod20)≡214=4096≡21(mod25)≡4⋅21=84(mod100)
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: Omni-MATH,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.