Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
$a_2=2012$ ? Are you sure? –  Ehsan May 26 '12 at 12:48
5  
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
1  
    
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
show 1 more comment

1 Answer

up vote 4 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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