7
$\begingroup$

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.

  • 0
    @Didier, you're right, thank you for pointing it out..2012-05-26

1 Answers 1

4

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.

  • 0
    @xan, very basic facts about finite fields and field extensions were used. I don't see a way to do without those facts, i.e. not within a reasonable space. Trust me, they are not deep at all, and should be covered in a first course dealing with field extensions. In other words, you don't need to become smarter to understand the details here. You will need a bit more exposure to algebraic structures though :-)2012-05-26