Number Theory – Relationship Between Primes and Fibonacci Sequence

divisibilityfibonacci-numbersnumber theoryopen-problemprime numbers

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection seems worth exploring. I'm interested whether anyone knows of a theorem or proof of whether this relationship holds true in general for primes > 5 — I've empirically tested it for the first 100k primes using Mathematica, but that's hardly a proof.

$$
S_n = GCD(n, Fib(n+1))
$$
If we evaluate this for $n ~ in ~{1..100}$ we get:

{1, 2, 3, 1, 1, 1, 7, 2, 1, 1, 1, 1, 13, 2, 3, 1, 17, 1, 1, 2, 1, 1,
23, 1, 1, 2, 3, 1, 1, 1, 1, 2, 1, 1, 1, 1, 37, 2, 3, 1, 1, 1, 43, 2,
1, 1, 47, 1, 1, 2, 3, 1, 53, 1, 1, 2, 1, 1, 1, 1, 1, 2, 21, 1, 1, 1,
67, 2, 1, 1, 1, 1, 73, 2, 3, 1, 1, 1, 1, 2, 1, 1, 83, 1, 1, 2, 3, 1,
1, 1, 1, 2, 1, 1, 1, 1, 97, 2, 33, 1}

What's interesting about this result is that primes appears at their natural indexes: 2 appears at $n_2$, 13 appears at $n_{13}$, 83 appears at $n_{83}$, and so on. But some of the primes are missing, including:

{5, 11, 19, 29, 31, 41, 59, 61, 71, 79, 89}

But let's also examine the sequence:
$$
P_n = GCD(n, Fib(n-1))
$$

Here we find that in the first 100 terms we get:

{1, 1, 1, 2, 1, 1, 1, 1, 3, 2, 11, 1, 1, 1, 1, 2, 1, 1, 19, 1, 3, 2,
1, 1, 1, 1, 1, 2, 29, 1, 31, 1, 3, 2, 1, 1, 1, 1, 1, 2, 41, 1, 1, 1,
3, 2, 1, 1, 7, 1, 1, 2, 1, 1, 1, 1, 3, 2, 59, 1, 61, 1, 1, 2, 1, 1,
1, 1, 3, 2, 71, 1, 1, 1, 1, 2, 1, 13, 79, 1, 3, 2, 1, 1, 1, 1, 1, 2,
89, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 2}

If we combine the sequences $S_n$ and $P_n$ we seem to get all of the primes, except 5:

{2, 3, (missing: 5), 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97}

Below is a simple Mathematica program that tests this for the first few thousand values:

fibSuc[x_] := GCD[n, Fibonacci[n + 1]];
fibPre[x_] := GCD[n, Fibonacci[n - 1]];
fibPRZ[w_, fp_] :=
  (Cases[Select[Transpose[{Table[fp[n], {n, 1, w}], 
     Table[x, {x, 1, w}]}], PrimeQ[#1[[2]]] & ], {a_, a_}]) /. {a_, a_} -> a;
genPrimes[z_] := Union[fibPRZ[z, fibSuc], fibPRZ[z, fibPre]];

With[{pz = genPrimes[50000]},
   Complement[Table[Prime[n], {n, 1, Length[pz] + 1}], pz]]

Best Answer

For primes $p > 5$, the Binet formula applies mod $p$, in the following sense. If $p \equiv \pm 1 \mod 5$, $5$ is a quadratic residue mod $p$, and $z^2 - z - 1$ has two roots $\phi_\pm = (1 \pm \sqrt{5})/2$ in ${\mathbb Z}_p$. Then $F_n \equiv ((\phi_+^n - \phi_-^n)/\sqrt{5} \mod p$. In particular, $F_{p-1}$ is divisible by $p$, so $\gcd(p, F_{p-1}) = p$.

If $p \equiv \pm 2 \mod 5$, $z^2 - z - 1$ doesn't have roots in ${\mathbb Z}_p$, but it has roots in an extension field $GF(p^2)$. In this case it turns out that $F_{p+1}$ is divisible by $p$, so $\gcd(p, F_{p+1}) = p$.

EDIT: Note that we have $\phi_+ + \phi_- = 1$ and $\phi_+ \phi_- = -1$. Since we're in characteristic $p$, $\phi_+^p + \phi_-^p = 1^p = 1$, and $\phi_+^p\phi_-^p = (-1)^p = -1$ as well. So $\phi_+^p$ and $\phi_-^p$ are also roots of $z^2 - z - 1$. But there are only two such roots. In the second case, we can't have $\phi_+^p = \phi_+$, because only elements of ${\mathbb Z}_p$ have the property $z^p = z$, so we must have $\phi_+^p = \phi_-$, and similarly $\phi_-^p = \phi_+$. Then $$F_{p+1} = \dfrac{\phi_+^{p+1} - \phi_-^{p+1}}{\sqrt{5}} = \dfrac{\phi_- \phi_+ - \phi_+ \phi_-}{\sqrt{5}} = 0 \ \text{(as a member of $GF(p^2)$)}$$ i.e. $F_{p+1} \equiv 0 \mod p$.

Related Question