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的質數中有一個以上的費波那契原根者的總和。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 129.2.129.154
※ 編輯: tml 來自: 129.2.129.154 (09/26 14:02)