Project Euler Problem 437

Solution

Answer: 74204709657207

Using the defining recurrence condition,

$$g^n+g^{n+1}\equiv g^{n+2}\pmod p,$$

divide by $g^n$ (valid since $g\neq 0$):

$$1+g\equiv g^2 \pmod p.$$

So a Fibonacci primitive root $g$ must satisfy

$$g^2-g-1\equiv 0\pmod p.$$

Thus the only candidates are

$$g \equiv \frac{1\pm \sqrt5}{2}\pmod p.$$

Hence:

$5$ must be a quadratic residue mod $p$, so for $p>5$,

$$p \equiv 1,9 \pmod{10}.$$ 2. For each such prime, compute the two roots of $x^2-x-1\equiv0\pmod p$ using Tonelli–Shanks. 3. Check whether either root is a primitive root modulo $p$.

If $q$ runs over the distinct prime divisors of $p-1$, then $g$ is primitive iff

$$g^{(p-1)/q}\not\equiv 1 \pmod p$$

for every $q\mid(p-1)$.

A correct implementation reproduces the problem’s check:

$323$ primes below $10000$,
sum $=1480491$,

and for $p<100000000$ gives the final total.

Answer: 74204709657207