Project Euler

Fibonacci Primitive Roots

A primitive root g of a prime p is a Fibonacci primitive root if g^n + g^(n+1) equiv g^(n+2) (mod p) for all n >= 0. Find the sum of all primes less than 10^8 that have at least one Fibonacci primi...

Source sync Apr 19, 2026

Problem #0437

Level Level 15

Solved By 978

Languages C++, Python

Answer 74204709657207

Length 325 words

modular_arithmeticnumber_theorysequence

When we calculate $8^n$ 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:

\begin {equation*} \begin {array}{l} 1+8=9 \\ 8+9=17 \equiv 6 \bmod 11 \\ 9+6=15 \equiv 4 \bmod 11 \\ 6+4=10 \\ 4+10=14 \equiv 3 \bmod 11 \\ 10+3=13 \equiv 2 \bmod 11 \\ 3+2=5 \\ 2+5=7 \\ 5+7=12 \equiv 1 \bmod 11 \end {array} \end {equation*}

So the powers of $8 \bmod 11$ are cyclic with period $10$, and $8^n + 8^{n+1} \equiv 8^{n+2} \pmod {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.

Problem 437: Fibonacci Primitive Roots

Mathematical Foundation

Theorem 1 (Characterization of Fibonacci Primitive Roots). A primitive root $g$ of prime $p$ is a Fibonacci primitive root if and only if $g^2 - g - 1 \equiv 0 \pmod{p}$ .

Proof. The condition $g^n + g^{n+1} \equiv g^{n+2} \pmod{p}$ for all $n \geq 0$ is equivalent (dividing both sides by $g^n$ , which is nonzero mod $p$ since $g$ is a primitive root) to $1 + g \equiv g^2 \pmod{p}$ , i.e., $g^2 - g - 1 \equiv 0 \pmod{p}$ . The forward direction gives this for $n = 0$ ; conversely, if $g^2 \equiv g + 1 \pmod{p}$ , then multiplying by $g^n$ yields $g^{n+2} \equiv g^{n+1} + g^n \pmod{p}$ for all $n$ . $\square$

Theorem 2 (Existence of Candidate Roots). The equation $x^2 - x - 1 \equiv 0 \pmod{p}$ has solutions in $\mathbb{F}_p$ if and only if $5$ is a quadratic residue modulo $p$ , which (for $p \neq 2, 5$ ) holds if and only if $p \equiv \pm 1 \pmod{5}$ .

Proof. By the quadratic formula, $x = (1 \pm \sqrt{5})/2 \pmod{p}$ . Solutions exist iff $\sqrt{5}$ exists in $\mathbb{F}_p$ , iff $\left(\frac{5}{p}\right) = 1$ . By quadratic reciprocity (since $5 \equiv 1 \pmod{4}$ ):

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

The quadratic residues modulo 5 are $1^2 \equiv 1$ and $2^2 \equiv 4$ , so $\left(\frac{p}{5}\right) = 1$ iff $p \equiv 1$ or $4 \pmod{5}$ , i.e., $p \equiv \pm 1 \pmod{5}$ . $\square$

Theorem 3 (Primitive Root Test). An element $g \in \mathbb{F}_p^*$ is a primitive root of $p$ if and only if $g^{(p-1)/q} \not\equiv 1 \pmod{p}$ for every prime $q \mid (p-1)$ .

Proof. The order of $g$ divides $p - 1$ . If $\mathrm{ord}(g) < p - 1$ , then $\mathrm{ord}(g) \mid (p-1)/q$ for some prime $q \mid (p-1)$ , so $g^{(p-1)/q} \equiv 1$ . Conversely, if $\mathrm{ord}(g) = p - 1$ , then $g^{(p-1)/q} \not\equiv 1$ for all prime $q \mid (p-1)$ , since $(p-1)/q < p - 1$ and $p - 1 \nmid (p-1)/q$ . $\square$

Lemma 1 (Special Case $p = 5$ ). For $p = 5$ : $x^2 - x - 1 \equiv x^2 - x + 4 \equiv (x - 3)^2 \pmod{5}$ , so $g = 3$ . Since $3^1 = 3$ , $3^2 = 4$ , $3^3 = 2$ , $3^4 = 1 \pmod{5}$ , $g = 3$ has order 4 = $p - 1$ , so 3 is a Fibonacci primitive root of 5. Thus $p = 5$ is included.

Proof. Direct computation. $\square$

Editorial

A Fibonacci primitive root g of prime p satisfies g^2 - g - 1 = 0 (mod p) and g is a primitive root of p. This requires p ≡ ±1 (mod 5) for sqrt(5) to exist mod p. We sieve primes and smallest prime factors up to N. We then iterate over p in primes. Finally, compute sqrt(5) mod p.

Pseudocode

Sieve primes and smallest prime factors up to N
for p in primes
Compute sqrt(5) mod p
Compute two candidates
Factor p - 1 using SPF sieve
Test if g1 or g2 is a primitive root

Complexity Analysis

Time: $O(N \log \log N)$ for the prime sieve and SPF sieve. For each qualifying prime $p$ (roughly $O(N / \log N)$ primes, of which $\approx 2/5$ pass the mod-5 filter): $O(\log p)$ for Tonelli-Shanks, $O(\omega(p-1) \cdot \log p)$ for the primitive root test (where $\omega(p-1)$ is the number of distinct prime factors). Total: $O(N \log \log N)$ dominated by the sieve.
Space: $O(N)$ for the SPF sieve array.

Answer

\boxed{74204709657207}

C++ project_euler/problem_437/solution.cpp

#include <bits/stdc++.h>
using namespace std;

// Project Euler 437: Fibonacci Primitive Roots
// Find sum of primes < 10^8 having at least one Fibonacci primitive root.

const int LIMIT = 100000000;

vector<int> spf; // smallest prime factor
vector<bool> is_prime_sieve;

void sieve() {
    spf.assign(LIMIT, 0);
    is_prime_sieve.assign(LIMIT, true);
    is_prime_sieve[0] = is_prime_sieve[1] = false;
    for (int i = 2; i < LIMIT; i++) {
        if (is_prime_sieve[i]) {
            spf[i] = i;
            for (long long j = (long long)i * i; j < LIMIT; j += i) {
                is_prime_sieve[j] = false;
                if (spf[j] == 0) spf[j] = i;
            }
        }
    }
}

// Get distinct prime factors of n using SPF sieve
vector<int> prime_factors(int n) {
    vector<int> factors;
    while (n > 1) {
        int p = spf[n];
        factors.push_back(p);
        while (n % p == 0) n /= p;
    }
    return factors;
}

long long power_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (__int128)result * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return result;
}

// Tonelli-Shanks algorithm: compute sqrt(n) mod p
long long tonelli_shanks(long long n, long long p) {
    if (n == 0) return 0;
    if (p == 2) return n & 1;

    // Check if n is QR
    if (power_mod(n, (p - 1) / 2, p) != 1) return -1;

    if (p % 4 == 3) {
        return power_mod(n, (p + 1) / 4, p);
    }

    // Factor out powers of 2 from p-1
    long long Q = p - 1, S = 0;
    while (Q % 2 == 0) { Q /= 2; S++; }

    // Find a non-residue
    long long z = 2;
    while (power_mod(z, (p - 1) / 2, p) != p - 1) z++;

    long long M = S;
    long long c = power_mod(z, Q, p);
    long long t = power_mod(n, Q, p);
    long long R = power_mod(n, (Q + 1) / 2, p);

    while (true) {
        if (t == 1) return R;
        long long i = 0, tmp = t;
        while (tmp != 1) { tmp = (__int128)tmp * tmp % p; i++; }
        long long b = c;
        for (long long j = 0; j < M - i - 1; j++)
            b = (__int128)b * b % p;
        M = i;
        c = (__int128)b * b % p;
        t = (__int128)t * c % p;
        R = (__int128)R * b % p;
    }
}

bool is_primitive_root(long long g, long long p, const vector<int>& factors) {
    if (g == 0) return false;
    for (int q : factors) {
        if (power_mod(g, (p - 1) / q, p) == 1)
            return false;
    }
    return true;
}

int main() {
    sieve();

    long long ans = 0;

    // p=5: check if it has a Fibonacci primitive root
    // g^2 - g - 1 = 0 mod 5: g^2 - g - 1, try g=1..4:
    // g=3: 9-3-1=5=0 mod 5, and 3 is primitive root of 5 (3^1=3,3^2=4,3^3=2,3^4=1)
    ans += 5;

    for (int p = 2; p < LIMIT; p++) {
        if (!is_prime_sieve[p]) continue;
        if (p <= 5) continue; // handled p=5 above, p=2,3 don't work

        // Check p ≡ ±1 (mod 5)
        int r = p % 5;
        if (r != 1 && r != 4) continue;

        // Compute sqrt(5) mod p
        long long sqrt5 = tonelli_shanks(5, p);
        if (sqrt5 < 0) continue;

        // inv(2) mod p
        long long inv2 = (p + 1) / 2;

        // Two candidates
        long long g1 = (__int128)(1 + sqrt5) * inv2 % p;
        long long g2 = (__int128)(1 + p - sqrt5) * inv2 % p;

        // Factor p-1
        vector<int> factors = prime_factors(p - 1);

        if (is_primitive_root(g1, p, factors) || is_primitive_root(g2, p, factors)) {
            ans += p;
        }
    }

    printf("%lld\n", ans);
    return 0;
}

Python project_euler/problem_437/solution.py

"""
Project Euler Problem 437: Fibonacci Primitive Roots

Find the sum of primes < 10^8 with at least one Fibonacci primitive root.

A Fibonacci primitive root g of prime p satisfies g^2 - g - 1 = 0 (mod p)
and g is a primitive root of p.

This requires p ≡ ±1 (mod 5) for sqrt(5) to exist mod p.
"""

import math

def sieve_spf(limit):
    """Sieve of smallest prime factors."""
    spf = list(range(limit))
    for i in range(2, int(limit**0.5) + 1):
        if spf[i] == i:  # i is prime
            for j in range(i*i, limit, i):
                if spf[j] == j:
                    spf[j] = i
    return spf

def prime_factors_from_spf(n, spf):
    """Get distinct prime factors using SPF array."""
    factors = []
    while n > 1:
        p = spf[n]
        factors.append(p)
        while n % p == 0:
            n //= p
    return factors

def power_mod(base, exp, mod):
    """Fast modular exponentiation."""
    return pow(base, exp, mod)

def tonelli_shanks(n, p):
    """Compute sqrt(n) mod p using Tonelli-Shanks algorithm."""
    if n == 0:
        return 0
    if power_mod(n, (p - 1) // 2, p) != 1:
        return -1
    if p % 4 == 3:
        return power_mod(n, (p + 1) // 4, p)

    Q, S = p - 1, 0
    while Q % 2 == 0:
        Q //= 2
        S += 1

    z = 2
    while power_mod(z, (p - 1) // 2, p) != p - 1:
        z += 1

    M = S
    c = power_mod(z, Q, p)
    t = power_mod(n, Q, p)
    R = power_mod(n, (Q + 1) // 2, p)

    while True:
        if t == 1:
            return R
        i, tmp = 0, t
        while tmp != 1:
            tmp = tmp * tmp % p
            i += 1
        b = c
        for _ in range(M - i - 1):
            b = b * b % p
        M = i
        c = b * b % p
        t = t * c % p
        R = R * b % p

def is_primitive_root(g, p, factors):
    """Check if g is a primitive root of p."""
    if g == 0:
        return False
    for q in factors:
        if power_mod(g, (p - 1) // q, p) == 1:
            return False
    return True

def solve():
    LIMIT = 100_000_000
    print("Sieving...")
    spf = sieve_spf(LIMIT)

    # Identify primes
    primes = [i for i in range(2, LIMIT) if spf[i] == i]
    print(f"Found {len(primes)} primes")

    ans = 0

    for p in primes:
        if p == 2 or p == 3:
            continue

        if p == 5:
            # g=3: 3^2 - 3 - 1 = 5 ≡ 0 (mod 5), and 3 is a primitive root of 5
            ans += 5
            continue

        r = p % 5
        if r != 1 and r != 4:
            continue

        sqrt5 = tonelli_shanks(5, p)
        if sqrt5 < 0:
            continue

        inv2 = (p + 1) // 2
        g1 = (1 + sqrt5) * inv2 % p
        g2 = (1 + p - sqrt5) * inv2 % p

        factors = prime_factors_from_spf(p - 1, spf)

        if is_primitive_root(g1, p, factors) or is_primitive_root(g2, p, factors):
            ans += p

    print(f"Answer: {ans}")

if __name__ == "__main__":
    solve()