ProjectEuler 437 Fibonacci primitive r - 拼圖

437. Fibonacci primitive roots

http://projecteuler.net/problem=437

將n代入0到9去計算8^n除以11的餘數，會分別得到1, 8, 9, 6, 4, 10, 3, 2, 5, 7。

不難發現所有可能的餘數1到10都有出現在這串數列中，意即8是模11的一個原根。

還不止如此：

如果我們仔細觀察這串數列，可以發現

1+8=9
8+9=17≡6 mod 11
9+6=15≡4 mod 11
6+4=10
4+10=14≡3 mod 11
10+3=13≡2 mod 11
3+2=5
2+5=7
5+7=12≡1 mod 11

故8的次方除以11的餘數是週期10的循環數列，並有8^n + 8^(n+1)≡8^(n+2) (mod 11)。

我們稱8是模11的一個「費波那契原根」。

並非所有質數都有自己的費波那契原根。

小於10000的質數中有323個質數有一個以上的費波那契原根，這些質數的和為1480491。

請求出小於100,000,000的質數中有一個以上的費波那契原根者的總和。

--