Problem 437
Fibonacci primitive roots
When we calculate 8n modulo 11 for n=0 to 9 we get: 1, 8, 9, 6, 4, 10, 3, 2, 5, 7.
As we see all possible values from 1 to 10 occur. So 8 is a primitive root of 11.
But there is more:
If we take a closer look we see:
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.
So the powers of 8 mod 11 are cyclic with period 10, and 8n + 8n+1 ≡ 8n+2 (mod 11).
8 is called a Fibonacci primitive root of 11.
Not every prime has a Fibonacci primitive root.
There are 323 primes less than 10000 with one or more Fibonacci primitive roots and the sum of these primes is 1480491.
Find the sum of the primes less than 100,000,000 with at least one Fibonacci primitive root.
斐波那契原根
对于n=0至9分别计算8n模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为周期重复，而且8n + 8n+1 ≡ 8n+2 (mod 11)。
因此，8被称为11的一个斐波那契原根。
不是所有的素数都有一个斐波那契原根。
在小于10000的数中，有323个质数有至少一个斐波那契原根，这些质数的和为1480491。
求在小于100,000,000的数中，至少有一个斐波那契原根的素数的和。