← 完整题目索引

PROJECT EULER · #0437

斐波那契原根

Fibonacci Primitive Roots

仅题目 · 待解原题 ↗

当我们计算 8n 模 11(n=0 到 9)时,我们得到:1,8,9,6,4,10,3,2,5,7。
正如我们所见,从 1 到 10 的所有可能值都会出现。所以 8 是 11 的原根。
但还有更多:
如果我们仔细观察,我们会发现:
1+8=9
8+9=17≡6mod11
9+6=15≡4mod11
6+4=10
4+10=14≡3mod11
10+3=13≡2mod11
3+2=5
2+5=7
5+7=12≡1mod11。

因此 8mod11 的幂是循环的,周期为 10,并且 8n+8n+1≡8n+2(mod11)。
8 被称为 11 的斐波那契原根。
并非每个质数都有斐波那契原根。
有 323 个小于 10000 的质数,具有一个或多个斐波那契原根,这些质数的总和为 1480491。
求出小于 100000000 并且至少有一个斐波那契原根的质数之和。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。