Detailed mathematical approach

Problem Summary

We want the sum of all primes \(p \lt 10^8\) for which there exists an element \(g \in \mathbb{F}_p^{\times}\) that is both a primitive root modulo \(p\) and satisfies the Fibonacci-type recurrence

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

Such an element is called a Fibonacci primitive root. A naive strategy would search through many primitive roots for every prime, but the recurrence collapses to one quadratic congruence, so each prime has at most two relevant candidates.

Mathematical Approach

Step 1: Reduce the recurrence to a quadratic congruence

Because \(g\) is a primitive root modulo a prime, it is nonzero modulo \(p\). Dividing the recurrence by \(g^n\) gives

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

Therefore a Fibonacci primitive root is exactly a primitive root that solves

$x^2-x-1\equiv 0\pmod{p}.$

This is the key simplification: instead of checking infinitely many recurrence steps, we only need to study one fixed polynomial.

Step 2: Decide when solutions exist

The discriminant of \(x^2-x-1\) is

$\Delta = 1+4 = 5.$

For \(p\neq 5\), the quadratic has solutions if and only if \(5\) is a quadratic residue modulo \(p\), equivalently

$\left(\frac{5}{p}\right)=1.$

Since \(5\equiv 1\pmod 4\), quadratic reciprocity yields

$\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right),$

so for odd primes \(p\neq 5\) the only possible residue classes are

$p\equiv 1 \text{ or } 4 \pmod{5}.$

This explains the early residue-class filter in the implementation. The small primes are exceptional: \(p=2\) and \(p=3\) give no solutions, while for \(p=5\) the polynomial becomes \((x-3)^2\), so \(3\) is the unique candidate and it is primitive modulo \(5\).

Step 3: Recover the two candidates from \(\sqrt{5}\)

If \(s^2\equiv 5\pmod p\), then the inverse of \(2\) modulo an odd prime is

$2^{-1}\equiv \frac{p+1}{2}\pmod p,$

and the quadratic roots are

$g_{\pm}\equiv \frac{1\pm s}{2}\pmod p.$

For \(p\neq 5\) there are exactly two such roots. Their sum is \(1\) and their product is \(-1\) modulo \(p\), but that algebraic relation does not guarantee primitiveness, so both candidates must still be tested.

Step 4: Primitive-root criterion

The multiplicative group \(\mathbb{F}_p^{\times}\) is cyclic of order \(p-1\). An element is primitive if and only if its order is exactly \(p-1\). Write

$p-1=\prod_{i=1}^{k} q_i^{e_i}$

for the prime factorization of \(p-1\). Only the distinct prime divisors \(q_i\) are needed. The standard criterion is

$g^{(p-1)/q_i}\not\equiv 1\pmod p\qquad \text{for every } i=1,\dots,k.$

If even one of these powers is \(1\), then the order of \(g\) is a proper divisor of \(p-1\). If none is \(1\), the order cannot drop, so \(g\) is a primitive root.

Worked Example: \(p=11\)

The prime \(11\) passes the residue filter because \(11\equiv 1\pmod 5\). A square root of \(5\) modulo \(11\) is \(4\), since \(4^2=16\equiv 5\pmod{11}\). Therefore

$g_{\pm}\equiv \frac{1\pm 4}{2}\equiv 8,\ 4 \pmod{11}.$

Now \(11-1=10=2\cdot 5\). For \(g=8\), the primitive-root checks are

$8^{10/2}=8^5\equiv 10\not\equiv 1\pmod{11},\qquad 8^{10/5}=8^2\equiv 9\not\equiv 1\pmod{11}.$

So \(8\) has order \(10\), hence it is a primitive root and \(11\) contributes to the final sum. This also shows that the residue test is only a necessary condition: it tells us when the quadratic has roots, not whether those roots generate the full group.

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline. They first build an odd-only smallest-prime-factor sieve. That single preprocessing step both identifies primes up to the limit and later factorizes \(p-1\) efficiently. The scan skips \(2\) and \(3\), adds \(5\) directly, and rejects all other primes with \(p\bmod 5\notin\{1,4\}\).

For the remaining primes, the implementation computes \(\sqrt{5}\pmod p\). When \(p\equiv 3\pmod 4\), a short exponentiation formula gives the square root immediately; otherwise it uses Tonelli-Shanks. From that square root it constructs the two roots \((1\pm \sqrt{5})/2\), extracts the distinct prime divisors of \(p-1\), and applies the primitive-root criterion. If either candidate passes, the prime is added to the running total.

Complexity Analysis

Let \(N=10^8\). The odd-only sieve uses \(O(N)\) memory asymptotically, with roughly half the storage of a full sieve, and it is built in \(O(N\log\log N)\) time. After that, each surviving prime needs only a small number of modular exponentiations, one modular square-root computation, and factorization of \(p-1\) through the precomputed SPF table.

In practice the sieve and the prime scan dominate the runtime. The per-prime work stays modest because only two candidates are ever examined, and the primitive-root test uses only the distinct prime divisors of \(p-1\). This is dramatically faster than searching through all primitive roots or checking the Fibonacci recurrence term by term.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=437
2. Primitive root modulo \(n\): Wikipedia — Primitive root modulo n
3. Legendre symbol and quadratic reciprocity: Wikipedia — Legendre symbol
4. Tonelli-Shanks algorithm: Wikipedia — Tonelli-Shanks algorithm
5. Finite fields and cyclic multiplicative groups: Wikipedia — Finite field