Encontrar (término $2012$ th de la secuencia) $\pmod {2012}$

Question

Sea $a_n$ una secuencia dada por la fórmula:

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

encontrar el valor: $a_{2012}\pmod{2012}$

Así que, de hecho, tenemos que encontrar el valor de $Fib_{2011}\pmod{2012}$ (término de $2011$-th de la secuencia de Fibonacci mod 2012) y creo que es la mejor manera de pensar.

Pero no saben cómo hacerlo. Estaría muy agradecido por la ayuda, porque el problema me intrigó mucho.

Answer 1

Esto se puede resolver utilizando el teorema del resto Chino. Es fácil comprobar que el módulo 4 de la secuencia de Fibonacci es cíclico, con un periodo de 6. Como $2010\equiv0\pmod6$ esto significa que $$ F_{2010}=F_0=0\pmod4. $$ Modulo el principal factor de $503\mid2012$ podemos utilizar la costumbre de la fórmula de Binet $$ F_n=\frac1{\sqrt5}\left(\tau^n-(-1)^n\tau^{-n}\right), $$ donde $\tau=(1+\sqrt5)/2$ es la proporción áurea, pero necesitamos reinterpretar $\sqrt5$. Por la reciprocidad cuadrática tenemos $$ \left(\frac5{503}\right)=\left(\frac{503}5\right)=\left(\frac35\right)=-1, $$ por lo $5$ no es un residuo cuadrático módulo $503$. Esto significa que necesitamos para salir de la aritmética al campo finito $K=F_{503^2}=F_{503}[\tau]$,$\tau^2=\tau+1$. En $K$ la asignación de $F:x\mapsto x^{503}$ es la única no-trivial de campo automorphism, por lo que satisface $F(\tau)=-\tau^{-1}$ $\tau$ $-\tau^{-1}$ comparten el mismo polinomio mínimo sobre el primer campo. Así, en el campo de $K$ tenemos $\tau^{503}=-\tau^{-1}$ y así, también,$\tau^{504}=-1$$\tau^{1008}=1$. Por lo tanto, $\tau^{2010}=\tau^{2\cdot1008-6}=\tau^{-6}$ y de manera similar a $\tau^{-2010}=\tau^6$. Esto significa que el modulo 503 tenemos $$ F_{2010}\equiv\frac1{\sqrt5}\left(\tau^{-6}-\tau^6\right)=-F_{6}=-8. $$ Así que sabemos que $F_{2010}\equiv -8\pmod{503}.$ Junto con nuestro anterior cálculo del módulo 4 (y el teorema del resto Chino) podemos concluir que $$ F_{2010}\equiv -8\pmod{2012}. $$ Nota: a mí me parece que nosotros también demostró que la secuencia de Fibonacci tiene período de $1008$ modulo $503$ (pero esto puede no ser el más pequeño período). Ver el wikipage en Pisano períodos para obtener más información.