# Relationship between Primes and Fibonacci Sequence

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]]

• It's probably of note that the primes in the first list are $\pm 3 \pmod{10}$ and in the second are $\pm1 \pmod{10}$. $2,5$ are the only primes not in these categories – Mathmo123 Aug 29 '14 at 18:24
• I'd also note that if $p$ is prime, then $P_p$ is either $1$ or $p$, so this result is not that surprising - what it says, for example, is that if $p \equiv \pm 1 \pmod {10}$ then $p \not \mid Fib(p-1)$ – Mathmo123 Aug 29 '14 at 18:31
• @LBushkin can you please write in your question what $Fib(1)$ is, so not every reader has to figure out on their own=) – flawr Aug 29 '14 at 18:33
• This seems to be a known result, as it is listed on the Wikipedia page for the Fibonacci numbers (in the section "Prime divisors of Fibonacci numbers"). Unfortunately, no proof is given, although it references two books. – William Ballinger Aug 29 '14 at 22:29
• I was playing around with Fibonacci, and surprise!, i found this prime number relationship: repl.it/JJPL/55 – djangofan Jun 30 '17 at 18:52

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$.

• Is there a simple proof that $F_{p+1}$ is divisible by $p$? I know how to do this with the binomial theorem, but I don't see how to get here directly from $GP(p^2)$ (naively, we can show that $F_{p^2-1}$ is divisible by $p$, of course, which is a strong hint). – Slade Aug 29 '14 at 19:42
• @you-sir-33433 : see latest edit. – Robert Israel Aug 30 '14 at 0:20
• @you-sir-33433 also see here: math.stackexchange.com/questions/695979/… – tc1729 Aug 30 '14 at 1:09

I would like to point out that $$p$$ cannot divide $$F_{p}$$ save perhaps in the case of $$p=5$$. Your indexing might be off by one; for example, $$83 | F_{84}$$ not $$F_{83}$$ as you suggest with the notation $$n_{83}$$.

In general, if $$p$$ is a prime then either $$p|F_{p-1}$$ or $$p|F_{p+1}$$ but not both. If, say, you consider $$p = 83$$, then $$83 | F_{84}$$ and so it must follow that $$gcd(83, F_{84}) = 83$$ for $$83$$ has no prime factors other than itself. The study of the Fibonacci sequence is perhaps best facilitated by an in-depth study of the Lucas sequences as the Fibonacci sequence is but one of a Lucas sequence.

• This should be a comment. – YiFan Jun 30 '19 at 4:09