A big Fibonacci number

Let's start with an identitiy: $F_{3n}=5F_{n}^3+3(-1)^nF_{n}$ .

How can we use it to solve the problem? Let $n$ be some power of $3$ . $n$ is clearly odd. Using the identity, we get: $F_{3n}=5F_{n}^3-3F_{n}$ . So, $F_{3n} \mod 521$ is uniquely defined by $F_{n} \mod 521$ . Indeed, if $x_n=F_{3^n} \mod 521$ , one can verify that $x_0=1=x_3$ (it's easy to calculate $x_3$ using the identity and a calculator). Hence, $x_n$ has a period of 3, and $x_{5^7}=x_{2}=F_{9}=34$ .

There are probably many ways to prove the identity, here is one sketch: (it is just a straightforward proof. nothing interesting.)

Start with proving that for any $n,k$ the following holds: $F_{m}=F_{k}F_{m+1-k}+F_{k-1}F_{m-k}$ . It can be done by a trivial induction on k.

Put $m=3n,k=n$ and get $F_{3n}=F_{n}F_{2n+1}+F_{n-1}F_{2n}$ .

In the same manner, derive the following identities:

$F_{2n}=F_{n}(F_{n+1}+F_{n-1})$

$F_{2n+1}=F_{n}^2+F_{n+1}^2$

Put everything together: $F_{3n}=F_{n}(F_{n}^2+F_{n+1}^2)+F_{n-1}F_{n}(F_{n+1}+F_{n-1})$ .

If we divide $F_{3n}$ by $F_{n}$ , we get: $F_{n}^2+F_{n+1}^2+F_{n-1}(F_{n+1}+F_{n-1})$ .

Do some algebra and show it equals to $2F_{n}^2+3F_{n-1}F_{n+1}$ .

Now, prove by induction that $F_{n+1}F_{n-1}=F_{n}^2+(-1)^n$ , and you're done.