分别计算$8^n$模11，$n=0,1,\ldots,9$的余数得1, 8, 9, 6, 4, 10, 3, 2, 5, 7。

可以看出，1至10在这些余数中都出现了，因此8被称为11的一个原根。

不仅如此，进一步观察可以发现 \begin{align*} 1+8&=9 \pmod 11 \\ 8+9&=6 \pmod 11 \\ 9+6&=4 \pmod 11 \\ 6+4&=10 \pmod 11 \\ 4+10&=3 \pmod 11 \\ 10+3&=2 \pmod 11 \\ 3+2&=5 \pmod 11 \\ 2+5&=7 \pmod 11 \\ 5+7&=1 \pmod 11, \end{align*} 即 $$8^n+8^{n+1}=8^{n+2} \pmod 11.$$ 因此，8又被称为11的一个斐波那契原根。不是所有的素数都有斐波那契原根。小于10000的数中，只有323个素数有至少斐波那契原根，这些素数的和为1480491。

求小于$10^8$的数中，有斐波那契原根的素数之和。

本题难度:

解答

容易验证2没有斐波那契原根，5有斐波那契原根3，接下来考虑大于5的素数p，若p有斐波那契原根g，则有 $$g^{n+2}-g^{n+1}-g^n=g^n(g^2-g-1)=0\pmod p.$$ 由n的任意性可知需要$g^2-g-1$模p余0，两边同乘以4（p是奇数）即得 $$(2g-1)^2=5 \pmod p$$ 即需要5是p的二次剩余，由于5除4余1，由二次互反律可知p也是5的二次剩余，因此p模5余1或余4（p模5余1或余4只是充分条件，并不能保证g是原根，需要求出g后检验）。

综上，先用筛法找出小于$10^8$且模5余1或余4的素数，再在模p乘法群中求出5的平方根，然后找出g并判断其是否为p的原根，最后汇总即得结果$74204709657207$。

注：因使用sympy求解g并判断其是否原根，以下代码为Python 3，代码中还打印了进度信息。

注2：本题所涉及的数论知识，是《初等数论》一类课程的标准内容。

import sympy

target=10**8
d=[0]*target
n=2
while n < target:
    for i in range(n*n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1

tick=10**6
res=5
for p in range(10,target):
    if d[p]==0 and p%5 in (1,4):
        a=sympy.mod_inverse(2,p)
        for x in sympy.sqrt_mod(5,p,all_roots=True):
            g=(a*(x+1))%p
            if sympy.is_primitive_root(g,p):
                res+=p
                break
    if p%tick==0:
        print(p//tick,"percent completed, current sum:",res)

print(res)