# 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.

#### Solutions Collecting From Web of "Finding ($2012$th term of the sequence) $\pmod {2012}$"

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.