Project Euler Problem 437 – Fibonacci Primitive Roots

Spoiler Alert! This blog entry contains content that might help you solve problem 437 of Project Euler. Please don’t read any further if you have yet to attempt to solve the problem on your own. The information is intended for those who failed to solve the problem and are looking for hints. It is posted not before the problem has a hundred solvers already.

Apparently, Project Euler doesn’t want people to present solutions to their problems outside of their forum. So even after you struggle for days on a difficult problem, you should not be able to see the solution to the problem (and, God forbid, get to know the math “secrets” behind the problem). I feel very differently about that, I think everyone should decide for themselves how much time (if at all) he or she wants to spend on a problem. I personally learn a lot more by studying the solutions to ten problems, than by working five hours on arduous integrals, fighting my way through math papers or spending painful time debugging my code just to solve one contrived math problem. But then again I’m interested in CS and not so much in math, so of course I’ll honor the position of Project Euler and won’t post any more solutions. So instead I present ten snippets in the realm of problem 437.

Ten Ideas Related to Fibonacci Primitive Roots

Hint 1: Generating Prime Numbers – Sieve of Eratosthenes

If you need a list of prime numbers up to a reasonably small number, then the easy Sieve of Eratosthenes is probably the best choice. It is very easy to understand and implement.

Hint 2: Repeated Squaring

Many Euler problems – and number-theoretic computations in general – are based on the following operation: compute a to the power of b modulo m. An efficient way to do that is called repeated squaring. An implementation in python

  def mod_exp(a, b, m):
    if b == 1:
        return a
    if b % 2:
        return a*mod_exp(a, b-1, m) % m
    r = mod_exp(a, b//2, m)

    return r*r % m</pre>

Hint 3: Fibonacci Primitive Root Condition

The problem statement lists all nine equations to gently prepare the reader for the concept.

$$ \begin{align} 1+8 &\equiv 9 \text{ mod }11 \\ 8+9&\equiv 6 \text{ mod }11\\ 9+6&\equiv 4 \text{ mod }11\\ 6+4&\equiv \text{ mod }11\\ 4+10&\equiv 3 \text{ mod }11\\ 10+3&\equiv 2 \text{ mod }11\\ 3+2&\equiv \text{ mod }11\\ 2+5&\equiv \text{ mod }11\\ 5+7&\equiv 1 \text{ mod }11 \end{align} $$

As one of the first Google hits on primitive roots shows, you only need to check the property for one triple of numbers. If it holds, then it holds for all other triples as well. So for a root g it is sufficient to check if

$$ g^2 \equiv g + 1 $$

Because by multiplying with g you can induce all other triples as well:

$$ \begin{align} g \cdot g^2 &\equiv g\cdot(g + 1) \\\ g^3 &\equiv g^2 + g \end{align} $$

Hint 4: Quadratic Equations

The potential solution(s) to quadratic equations in modular arithmetic are derived the same way as for regular algebra. The solutions of

$$ \begin{equation} ax^2+bx+c \equiv 0 \text{ mod }m \end{equation} $$

are

$$ \begin{equation} x \equiv \frac{-b \pm \sqrt {b^2-4ac}}{2a} \text{ mod }m \end{equation} $$

The differences to regular algebra are

1. Instead of dividing by $2a$ , you multiply by the modular multiplicative inverse of $2a$
2. The square root is given by the quadratic residue

Hint 5: Modular Multiplicative Inverse of 2″

You can calculate the modular multiplicative inverse for an odd prime p like you would calculate the inverse for any other number using Euler’s theorem:

$$ \begin{equation} 2^{-1} \equiv 2^{p-2} \text{ mod }p \end{equation} $$

Since p is odd, and therefore p+1 divisible by two, the inverse of two can be found much simpler by:

$$ \begin{equation} 2^{-1} \equiv \frac{p+1}{2} \text{ mod }p \end{equation} $$

Hint 6: Existance of Quadratic residue – Legendre symbol

The quadratic residue doesn’t alwalys exists. To define if a number a is a quadratic residue mod p we can use the Legendre symbol:

$$ \begin{align} \left(\frac{a}{p}\right) &= \begin{cases};;,0\text{ if }p \text{ divides } a\\+1\text{ if }a \text{ is a residue } p \text{ and }p \text{ does not divide } a\\-1\text{ if }a \text{ is a non-residue } p .\end{cases} \\ &\equiv a^{\frac{p-1}{2}} \text{ mod } p \end{align} $$

Or in C

int legendre_symbol(num a, num p) {
        long ls = mod_pow(a, (p-1)/2, p);
  return ls == p - 1 ? -1 : ls;
}

Only if the Legendre symbol is 1 does the quadratic residue exist.

Hint 7: Existance of Quadratic Residue – Quadratic reciprocity

The law of quadratic reciprocity says (Gauss’s version):

If $q \equiv 1 \pmod 4$ or $p \equiv 1 \pmod 4$ (or both) then the congruence $x^2 \equiv p \pmod q$ is solvable if an only if $x^2 \equiv q \pmod p$ .”

So for example $x^2 \equiv 5 \pmod p$ is only solvable if $x^2 \equiv p \pmod 5$ . Since the only residues mod 5 are $\pm 1$ , we know that $x^2 \equiv 5 \pmod p$ has a solution if $p \equiv \pm 1 \pmod 5$ .

Hint 8: Determine the Quadratic Residue – Tonelli-Shanks Algorithm

The Tonelli-Shanks algorithm can be used to solve the congruence:

$$ x^2 \equiv n \pmod p $$

An implementation in Python can be found here

Hint 9: Determine if a Number is Primitive Root

To determine whether a is a primitive root modulo p, you need know whether the order of a is $p-1$ (it is a primitive root) or less (not a primitive root). Since the order has to be a prime factor, you need to test:

$$ \begin{equation} a^{((p-1)/f)} \not\equiv 1 (\mod p) \end{equation} $$

for all prime factors $f$ of $p-1$ .

For example, lets check if $a=8$ is indeed a primitive root of $p=11$ . The factors of $p-1=10$ are $2$ and $5$ .

$$ \begin{align} 8^{10/2} \equiv 10 \not\equiv 1(\mod 11) \\ 8^{10/5} \equiv 9 \not\equiv 1 (\mod 11) \end{align} $$

Hence $8$ is a primitive root. Here’s some incomplete Python code to illustrate the algorithm:

def is_primitive_root(a, p):    
    for f in prime_factors(p-1):
        if mod_pow(a,(n-1)/f, p) == 1:  
            return False
    return True

Hint 10: Prime Factorization – Sieve of Eratosthenes (Modified)

The Sieve of Eratosthenes just crosses out all numbers that are not prime. So for instance, you would cross 49 as soon as you get to the prime 7. A modification of this algorithm would instead store 7 at position 49. Since 7 is the first number that divides 49 and the sieve uses increasingly larger primes, we know that 7 is the smallest divisor of 49.

number: 2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20
mindiv: p   p   2   p   2   p   2   3    2    p    2    p    2    3    2    p    2    p    2

The complexity of the algorithm doesn’t increase, and we have the following added benefit: To factor a number you look up the smallest divisor. This will be your first prime factor. Then you divide the number by that divisor. You then repeat the procedure for this new number, until you get a prime, at which point you stop.

For example lets factor 20:

1. The smallest divisor of 20 is 2, so the first prime factor is 2. We divide 20 by 2 and get 10.
2. The smallest divisor of 10 is 2, so the second prime factor is 2. We divide 10 by 2 and get 5.
3. 5 is a prime number, so it is our third and last prime factor.

Archived Comments