← Complete problem index

PROJECT EULER · #0989

Fibonacci Sum

Statement only · UnsolvedOriginal problem ↗

Write Fn for the n-th Fibonacci number, with F1=F2=1 and Fn+1=Fn+Fn−1.

It is known that Fn is very well approximated by φn/5, where φ, the golden ratio, is the positive root of the equation x2=x+1.

Let G(n) be the number of distinct integers 0≤x<n such that x2≡x+1(modn).

You are given ∑n=1103FnG(n)≡190950976mod(109+9).

Find ∑n=11014FnG(n), giving your answer modulo 109+9.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.