Maths Olympiad Prep

Library / /757 of 860

Algebra Difficulty 5.5 AIME, harder Find the answer

Let x1=y1=x2=y2=1x_{1}=y_{1}=x_{2}=y_{2}=1, then for n3n \geq 3 let xn=xn1yn2+xn2yn1x_{n}=x_{n-1} y_{n-2}+x_{n-2} y_{n-1} and yn=yn1yn2xn1xn2y_{n}=y_{n-1} y_{n-2}- x_{n-1} x_{n-2}. What are the last two digits of x2012\left|x_{2012}\right| ?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let zn=yn+xniz_{n}=y_{n}+x_{n} i. Then the recursion implies that: z1=z2=1+izn=zn1zn2\begin{aligned} & z_{1}=z_{2}=1+i \\ & z_{n}=z_{n-1} z_{n-2} \end{aligned} This implies that zn=(z1)Fnz_{n}=\left(z_{1}\right)^{F_{n}} where FnF_{n} is the nth n^{\text {th }} Fibonacci number (F1=F2=1)\left(F_{1}=F_{2}=1\right). So, z2012=(1+i)F2012z_{2012}=(1+i)^{F_{2012}}. Notice that (1+i)2=2i(1+i)^{2}=2 i Also notice that every third Fibonnaci number is even, and the rest are odd. So: z2012=(2i)F201212(1+i)z_{2012}=(2 i)^{\frac{F_{2012}-1}{2}}(1+i) Let m=F201212m=\frac{F_{2012}-1}{2}. Since both real and imaginary parts of 1+i1+i are 1 , it follows that the last two digits of x2012\left|x_{2012}\right| are simply the last two digits of 2m=2F2012122^{m}=2^{\frac{F_{2012}-1}{2}}. By the Chinese Remainder Theorem, it suffices to evaluate 2m2^{m} modulo 4 and 25 . Clearly, 2m2^{m} is divisible by 4 . To evaluate it modulo 25, it suffices by Euler's Totient theorem to evaluate mm modulo 20. To determine (F20121)/2\left(F_{2012}-1\right) / 2 modulo 4 it suffices to determine F2012F_{2012} modulo 8. The Fibonacci sequence has period 12 modulo 8 , and we find F20125(mod8)m2(mod4)\begin{aligned} F_{2012} & \equiv 5 \quad(\bmod 8) \\ m & \equiv 2 \quad(\bmod 4) \end{aligned} 231(mod5)2 * 3 \equiv 1(\bmod 5), so m3F20123(mod5)m \equiv 3 F_{2012}-3 \quad(\bmod 5) The Fibonacci sequence has period 20 modulo 5 , and we find m4(mod5)m \equiv 4 \quad(\bmod 5) Combining, m14(mod20)2m214=409621(mod25)x2012421=84(mod100)\begin{aligned} m & \equiv 14 \quad(\bmod 20) \\ 2^{m} & \equiv 2^{14}=4096 \equiv 21 \quad(\bmod 25) \\ \left|x_{2012}\right| & \equiv 4 \cdot 21=84 \quad(\bmod 100) \end{aligned}

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.