Let $a_n$ be a sequence given by formula:


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.

  • $\begingroup$ $a_2=2012$ ? Are you sure? $\endgroup$ – Ehsan May 26 '12 at 12:48
  • 5
    $\begingroup$ 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.. $\endgroup$ – xan May 26 '12 at 12:52
  • 1
    $\begingroup$ check this: mathoverflow.net/questions/40816/fibonacci-series-mod-a-number $\endgroup$ – Ehsan May 26 '12 at 13:15
  • $\begingroup$ nice, and very easy, thanks ;-) so the closed form formula isn't rather possible? $\endgroup$ – xan May 26 '12 at 13:38
  • $\begingroup$ But $a_{2012}=F_{2010}\pmod{2012}$, not $F_{2011}\pmod{2012}$. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ But $a_{2012}=F_{2010}\pmod{2012}$, not $F_{2011}\pmod{2012}$. $\endgroup$ – Did May 26 '12 at 15:25
  • $\begingroup$ Arrrggh! Thanks, @Didier! $\endgroup$ – Jyrki Lahtonen May 26 '12 at 15:26
  • $\begingroup$ Sorry... but your method goes through, doesn't it? $\endgroup$ – Did May 26 '12 at 15:27
  • $\begingroup$ Sure, editing.... $\endgroup$ – Jyrki Lahtonen May 26 '12 at 15:27
  • $\begingroup$ I'm terribly sorry for misleading! $\endgroup$ – xan May 26 '12 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.