作者tml (流刑人形)
看板puzzle
标题[中译] ProjectEuler 437 Fibonacci primitive r
时间Thu Sep 26 13:53:43 2013
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)