Intereting Posts

Is this argument valid? (Number Theory)
In which case $M_1 \times N \cong M_2 \times N \Rightarrow M_1 \cong M_2$ is true?
$L^1$ convergence gives a pointwise convergent subsequence
About the number of zeros of the zeta function?
the Nordhaus-Gaddum problems for chromatic number of graph and its complement
exterior covariant derivative of $\operatorname{End}(E)$-valued $p$-form
Norms on C inducing the same topology as the sup norm
sequential continuity vs. continuity
A functional structure on the graph of the absolute value function
Suppose that $P(x)$ is a polynomial of degree $n$ such that $P(k)=\dfrac{k}{k+1}$ for $k=0,1,\ldots,n$. Find the value of $P(n+1)$
Fermat's Little Theorem: exponents powers of p
Local coefficient System and universal cover
Determine all the values of $1^{\sqrt{2}}$
Prove $\cos 3x =4\cos^3x-3\cos x$
Show reflexive normed vector space is a Banach space

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.

- Need some help with this recurrence equation
- Closed form for the sequence defined by $a_0=1$ and $a_{n+1} = a_n + a_n^{-1}$
- Does equation $f(g(x))=a f(x)$ have a solution?
- How to solve this recurrence $T(n)=2T(n/2)+n/\log n$
- Can Master Theorem be applied on any of these?
- $n$-Bit Strings Not Containing $010$
- How to show that this binomial sum satisfies the Fibonacci relation?
- How to solve this recurrence relation? $f_n = 3f_{n-1} + 12(-1)^n$
- Links between difference and differential equations?
- How to find $\lim a_n$ if $ a_{n+1}=a_n+\frac{a_n-1}{n^2-1} $ for every $n\ge2$

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.

- Stirling Number of second kind (unsigned) and binomial coefficient, proof of equality?
- L'hospital rule for two variable.
- What is the sum of this? $ 1 + \frac12 + \frac13 + \frac14 + \frac16 + \frac18 + \frac19 + \frac1{12} +\cdots$
- Equivalent norms
- Calculate $\mathbb{E}(W_t^k)$ for a Brownian motion $(W_t)_{t \geq0}$ using Itô's Lemma
- Interesting Integral $\int_{-\infty}^{\infty}\frac{e^{i nx}}{\Gamma(\alpha+x) \Gamma(\beta -x)}dx$
- Is there a geometric meaning to the outer product of two vectors?
- Is 1+1 =2 a theorem?
- What is the oldest open problem in geometry?
- Power-reduction formula
- Divisors of Pell Equation Solutions
- Inverse Nasty Integral
- Reference request: proof that the first hitting time of a Borel set is a stopping time
- Prove that ${\sqrt2}^{\sqrt2}$ is an irrational number without using a theorem.
- Prove that $(0)$ is a radical ideal in $\mathbb{Z}/n\mathbb{Z}$ iff $n$ is square free