# Finding ($2012$th term of the sequence) $\pmod {2012}$

Let $a_n$ be a sequence given by formula:

$a_1=1\\a_2=2012\\a_{n+2}=a_{n+1}+a_{n}$

find the value: $a_{2012}\pmod{2012}$

So, in fact, we have to find the value of $Fib_{2011}\pmod{2012}$ ($2011$-th term of Fibonacci sequence mod 2012) and I think it's the better way to think about it.

But don't know how to do that. I would be very grateful for help, because the problem intrigued me a lot.

-
$a_2=2012$ ? Are you sure? –  Ehsan May 26 '12 at 12:48
that's the problem, sequence $a_n$ is given.. $a_n\neq Fib_n$, we have to find $a_{2012}\mod{2012}$ but it comes down to count $Fib_{2011}\mod{2012}$, because $a_1\mod{2012}=1, a_2\mod{2012}=0, a_3\mod{2012}=1$, and in general: $a_n\mod{2012}=Fib_{n-1}\mod{2012}$ .. if I'm not wrong of course.. –  xan May 26 '12 at 12:52
–  Ehsan May 26 '12 at 13:15
nice, and very easy, thanks ;-) so the closed form formula isn't rather possible? –  xan May 26 '12 at 13:38
But $a_{2012}=F_{2010}\pmod{2012}$, not $F_{2011}\pmod{2012}$. –  Did May 26 '12 at 15:24

This can be solved using the Chinese remainder theorem. It is easy to check that modulo 4 the Fibonacci sequence is cyclic with a period 6. As $2010\equiv0\pmod6$ this means that $$F_{2010}=F_0=0\pmod4.$$ Modulo the prime factor $503\mid2012$ we can use the usual Binet's formula $$F_n=\frac1{\sqrt5}\left(\tau^n-(-1)^n\tau^{-n}\right),$$ where $\tau=(1+\sqrt5)/2$ is the golden ratio, but we need to reinterpret $\sqrt5$. By quadratic reciprocity we have $$\left(\frac5{503}\right)=\left(\frac{503}5\right)=\left(\frac35\right)=-1,$$ so $5$ is not a quadratic residue modulo $503$. This means that we need to move the arithmetic to the finite field $K=F_{503^2}=F_{503}[\tau]$, with $\tau^2=\tau+1$. In $K$ the mapping $F:x\mapsto x^{503}$ is the unique non-trivial field automorphism, so it satisfies $F(\tau)=-\tau^{-1}$, as $\tau$ and $-\tau^{-1}$ share the same minimal polynomial over the prime field. So in the field $K$ we have $\tau^{503}=-\tau^{-1}$ and thus also $\tau^{504}=-1$ and $\tau^{1008}=1$. Therefore $\tau^{2010}=\tau^{2\cdot1008-6}=\tau^{-6}$ and similarly $\tau^{-2010}=\tau^6$. This means that modulo 503 we have $$F_{2010}\equiv\frac1{\sqrt5}\left(\tau^{-6}-\tau^6\right)=-F_{6}=-8.$$ So we know that $F_{2010}\equiv -8\pmod{503}.$ Together with our earlier calculation modulo 4 (and the Chinese remainder theorem) we can conclude that $$F_{2010}\equiv -8\pmod{2012}.$$ Note: it seems to me that we also proved that the Fibonacci sequence has period $1008$ modulo $503$ (but this may not be the smallest period). See the wikipage on Pisano periods for more information.
But $a_{2012}=F_{2010}\pmod{2012}$, not $F_{2011}\pmod{2012}$. –  Did May 26 '12 at 15:25