View source for Fibonacci prime

{{Short description|Prime number in the Fibonacci sequence}}
{{Infobox integer sequence
| terms_number       = 17
| con_number         = Infinite<ref>{{Cite web|url=http://mathworld.wolfram.com/FibonacciPrime.html|title=Fibonacci Prime}}</ref>
| first_terms        = [[2 (number)|2]], [[3 (number)|3]], [[5 (number)|5]], [[13 (number)|13]], [[89 (number)|89]], [[233 (number)|233]]
| largest_known_term = F<sub>10367321</sub>
| OEIS               = A001605
| OEIS_name          = Indices of prime Fibonacci numbers

}}

A '''Fibonacci prime''' is a [[Fibonacci number]] that is [[prime number|prime]], a type of integer sequence prime.

The first Fibonacci primes are {{OEIS|id=A005478}}:

:[[2 (number)|2]], [[3 (number)|3]], [[5 (number)|5]], [[13 (number)|13]], [[89 (number)|89]], [[233 (number)|233]], 1597, 28657, 514229, 433494437, 2971215073, ....

==Known Fibonacci primes==
{{unsolved|mathematics|Are there an infinite number of Fibonacci primes?}}
It is not known whether there are [[Infinity|infinitely]] many Fibonacci primes. With the indexing starting with {{nowrap|1=''F''<sub>1</sub> = ''F''<sub>2</sub> = 1}}, the first 37 indices ''n'' for which ''F''<sub>''n''</sub> is prime are {{OEIS|id=A001605}}:
:''n'' = 3, 4<!--DO NOT REMOVE 4. n is the index. n=4 gives the Fibonacci number F_4 = 3 which is prime so 4 belongs in this list.-->, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677, 14431, 25561, 30757, 35999, 37511, 50833, 81839, 104911, 130021, 148091, 201107.
(Note that the actual values ''F''<sub>''n''</sub> rapidly become very large, so, for practicality, only the indices are listed.)

In addition to these proven Fibonacci primes, several [[probable prime]]s have been found:
:''n'' = 397379, 433781, 590041, 593689, 604711, 931517, 1049897, 1285607, 1636007, 1803059, 1968721, 2904353, 3244369, 3340367, 4740217, 6530879, 7789819, 10317107, 10367321.<ref name="prptop">[http://www.primenumbers.net/prptop/searchform.php?form=F%28n%29&action=Search PRP Top Records, Search for : F(n)]. Retrieved 2018-04-05.</ref>

Except for the case ''n'' = 4, all Fibonacci primes have a prime index, because if ''a'' [[divisor|divides]] ''b'', then <math>F_a</math> also divides <math>F_b</math> (but not every prime index results in a Fibonacci prime). That is to say, the Fibonacci sequence is a [[divisibility sequence]].

''F''<sub>''p''</sub> is prime for 8 of the first 10 primes ''p''; the exceptions are ''F''<sub>2</sub> = 1 and ''F''<sub>19</sub> = 4181 = 37 &times; 113. However, Fibonacci primes appear to become rarer as the index increases. ''F''<sub>''p''</sub> is prime for only 26 of the 1229 primes ''p'' smaller than 10,000.<ref>Sloane's {{OEIS2C|A005478}}, {{OEIS2C|A001605}}</ref> The number of prime factors in the Fibonacci numbers with prime index are:
:0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 1, 2, 4, 2, 3, 2, 2, 2, 2, 1, 1, 3, 4, 2, 4, 4, 2, 2, 3, 3, 2, 2, 4, 2, 4, 4, 2, 5, 3, 4, 3, 2, 3, 3, 4, 2, 2, 3, 4, 2, 4, 4, 4, 3, 2, 3, 5, 4, 2, 1, ... {{OEIS|A080345}}

{{As of|2023|09}}, the largest known certain Fibonacci prime is ''F''<sub>201107</sub>, with 42029 digits. It was proved prime by Maia Karpovich in September 2023.<ref>{{cite web |title=The Top Twenty: Fibonacci Number |url=https://primes.utm.edu/top20/page.php?id=39 |website=primes.utm.edu |access-date=15 September 2023}}</ref> The largest known probable Fibonacci prime is ''F''<sub>10367321</sub>. It was found by Ryan Propper in July 2024.<ref name="prptop"/>
It was proved by Nick MacKinnon that the only Fibonacci numbers that are also [[twin prime]]s are 3, 5, and 13.<ref>N. MacKinnon, Problem 10844, Amer. Math. Monthly 109, (2002), p. 78</ref>

==Divisibility of Fibonacci numbers==
A prime <math>p</math> divides <math>F_{p-1}</math> [[if and only if]] ''p'' is [[Modular arithmetic|congruent]] to ±1 modulo 5, and ''p'' divides <math>F_{p+1}</math> if and only if it is congruent to ±2 modulo 5. (For ''p'' = 5, ''F''<sub>5</sub> = 5 so 5 divides ''F''<sub>5</sub>)

Fibonacci numbers that have a prime index ''p'' do not share any common divisors greater than 1 with the preceding Fibonacci numbers, due to the identity:<ref>[[Paulo Ribenboim]], ''My Numbers, My Friends'', Springer-Verlag 2000</ref>

:<math>\gcd(F_n, F_m) = F_{\gcd(n,m)}.</math>

For {{math|''n''&nbsp;≥&nbsp;3}}, ''F<sub>n</sub>'' divides ''F<sub>m</sub>'' if and only if ''n'' divides ''m''.<ref>Wells 1986, p.65</ref>

If we suppose that ''m'' is a prime number ''p'', and ''n'' is less than ''p'', then it is clear that ''F''<sub>''p''</sub> cannot share any common divisors with the preceding Fibonacci numbers.

:<math>\gcd(F_p, F_n) = F_{\gcd(p,n)} = F_1 = 1.</math>

This means that ''F<sub>p</sub>'' will always have characteristic factors or be a prime characteristic factor itself. The number of distinct prime factors of each Fibonacci number can be put into simple terms.

* ''F''<sub>''nk''</sub> is a multiple of ''F''<sub>''k''</sub> for all values of ''n'' and ''k'' such that ''n'' ≥ 1 and ''k'' ≥ 1.<ref>The mathematical magic of Fibonacci numbers [http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html#section2 Factors of Fibonacci numbers]</ref> It's safe to say that ''F<sub>nk</sub>'' will have "at least" the same number of distinct prime factors as ''F<sub>k</sub>''. All ''F''<sub>''p''</sub> will have no factors of ''F''<sub>''k''</sub>, but "at least" one new characteristic prime from [[Carmichael's theorem]].
* Carmichael's Theorem applies to all Fibonacci numbers except four special cases: <math>F_1 =F_2 =1, F_6 = 8</math> and <math>F_{12} = 144.</math> If we look at the prime factors of a Fibonacci number, there will be at least one of them that has never before appeared as a factor in any earlier Fibonacci number. Let ''π<sub>n</sub>'' be the number of distinct prime factors of ''F<sub>n</sub>''. {{OEIS|id=A022307}}
::If ''k'' | ''n'' then <math>\pi_n \geqslant \pi_k +1</math> except for <math>\pi_6 = \pi_3 =1.</math>
::If ''k'' = 1, and ''n'' is an [[parity (mathematics)|odd]] prime, then 1 | ''p'' and <math>\pi_p \geqslant \pi_1 +1 = 1.</math>
{| class="wikitable" style="text-align:right"
|-
! ''n''
| 0 || 1 || '''2''' || '''3''' || 4 || '''5''' || 6 || '''7''' || 8 || 9 || 10 || '''11''' || 12 || '''13''' || 14 || 15 || 16 || '''17''' || 18 || '''19''' || 20 || 21 || 22 || '''23''' || 24 || 25
|-
! ''F<sub>n</sub>''
| 0 || 1 || 1 || 2 || 3 || 5 || 8 || 13 || 21 || 34 || 55 || 89 || 144 || 233 || 377 || 610 || 987 || 1597 || 2584 || 4181 || 6765 || 10946 || 17711 || 28657 || 46368 || 75025
|-
! ''π<sub>n</sub>''
| 0 || 0 || 0 || 1 || 1 || 1 || 1 || 1 || 2 || 2 || 2 || 1 || 2 || 1 || 2 || 3 || 3 || 1 || 3 || 2 || 4 || 3 || 2 || 1 || 4 || 2
|}

The first step in finding the characteristic quotient of any ''F<sub>n</sub>'' is to divide out the prime factors of all earlier Fibonacci numbers ''F<sub>k</sub>'' for which ''k'' | ''n''.<ref>Jarden - Recurring sequences, Volume 1, Fibonacci quarterly, by Brother U. Alfred</ref>

The exact quotients left over are prime factors that have not yet appeared.

If ''p'' and ''q'' are both primes, then all factors of ''F<sub>pq</sub>'' are characteristic, except for those of ''F<sub>p</sub>'' and ''F<sub>q</sub>''.

:<math>\begin{align}
\gcd (F_{pq}, F_q ) &= F_{\gcd(pq, q)} = F_q \\
\gcd (F_{pq}, F_p ) &= F_{\gcd(pq, p)} = F_p 
\end{align}</math>

Therefore:

:<math>\pi_{pq} \geqslant \begin{cases} \pi_p + \pi_q + 1 & p\neq q \\ \pi_p + 1 & p = q \end{cases}</math>

The number of distinct prime factors of the Fibonacci numbers with a prime index is directly relevant to the counting function. {{OEIS|id=A080345}}
{| class="wikitable"  style="text-align:right"
|-
! ''p'' 
| 2 || 3 || 5 || 7 || 11 || 13 || 17 || 19 || 23 || 29 || 31 || 37 || 41 || 43 || 47 || 53 || 59 || 61 || 67 || 71 || 73 || 79 || 83 || 89 || 97
|-
! ''π<sub>p</sub>'' 
| 0 || 1 || 1 || 1 || 1 || 1 || 1 || 2 || 1 || 1 || 2 || 3 || 2 || 1 || 1 || 2 || 2 || 2 || 3 || 2 || 2 || 2 || 1 || 2 || 4
|}

==Rank of apparition==

For a prime ''p'', the smallest index ''u'' > 0 such that ''F<sub>u</sub>'' is divisible by ''p'' is called the '''rank of apparition''' (sometimes called '''Fibonacci entry point''') of ''p'' and denoted ''a''(''p''). The rank of apparition ''a''(''p'') is defined for every prime ''p''.<ref>{{OEIS|A001602}}</ref> The rank of apparition divides the [[Pisano period]] π(''p'') and allows to determine all Fibonacci numbers divisible by ''p''.<ref>{{cite journal|title=The Relation of the Period Modulo ''m'' to the Rank of Apparition of ''m'' in the Fibonacci Sequence |author=John Vinson |journal=Fibonacci Quarterly |volume=1 |year=1963 |issue=2 |pages=37–45 |doi=10.1080/00150517.1963.12431578 |url=http://www.fq.math.ca/Scanned/1-2/vinson.pdf}}</ref>

For the divisibility of Fibonacci numbers by powers of a prime, <math>p \geqslant 3, n \geqslant 2</math> and <math>k \geqslant 0</math>

:<math>p^n \mid F_{a(p)kp^{n-1}}.</math>

In particular

:<math>p^2 \mid F_{a(p)p}.</math>

== Wall–Sun–Sun primes ==
{{main|Wall–Sun–Sun prime}}

A prime ''p'' ≠ 2, 5 is called a Fibonacci–Wieferich prime or a [[Wall–Sun–Sun prime]] if <math>p^2 \mid F_q,</math> where

:<math>q = p - \left(\frac{{p}}{{5}}\right)</math>

and <math>\left(\tfrac{{p}}{{5}}\right)</math> is the [[Legendre symbol]]:

:<math>\left(\frac{p}{5}\right) = \begin{cases} 1 & p \equiv \pm 1 \bmod 5\\ -1 & p \equiv \pm 2 \bmod 5 \end{cases}</math>

It is known that for ''p'' ≠ 2, 5, ''a''(''p'') is a divisor of:<ref>{{cite book |author=Steven Vajda |title=Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications |series=Dover Books on Mathematics}}</ref>

:<math>p-\left(\frac{{p}}{{5}}\right) = \begin{cases} p-1 & p \equiv \pm 1 \bmod 5\\ p+1 & p \equiv \pm 2 \bmod 5 \end{cases}</math>

For every prime ''p'' that is not a Wall–Sun–Sun prime, <math>a(p^2) = p a(p)</math> as illustrated in the table below:

{| class="wikitable"  style="text-align:right"
|-
! ''p'' 
| 2 || 3 || 5 || 7 || 11 || 13 || 17 || 19 || 23 || 29 || 31 || 37 || 41 || 43 || 47 || 53 || 59 || 61 
|-
! ''a''(''p'') 
| 3 || 4 || 5 || 8 || 10 || 7 || 9 || 18 || 24 || 14 || 30 || 19 || 20 || 44 || 16 || 27 || 58 || 15
|-
! ''a''(''p''<sup>2</sup>) 
| 6 || 12 || 25 || 56 || 110 || 91 || 153 || 342 || 552 || 406 || 930 || 703 || 820 || 1892 || 752 || 1431 || 3422 || 915
|}

The existence of Wall–Sun–Sun primes is [[conjecture|conjectural]].

==Fibonacci primitive part==
Because <math>F_a | F_{ab}</math>, we can divide any Fibonacci number <math>F_n</math> by the [[least common multiple]] of all <math>F_d</math> where <math>d | n</math>. The result is called the '''primitive part''' of <math>F_n</math>. The primitive parts of the Fibonacci numbers are
:1, 1, 2, 3, 5, 4, 13, 7, 17, 11, 89, 6, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 46, 15005, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 321, 24157817, 9349, 135721, 2161, 165580141, 211, 433494437, 13201, 109441, ... {{OEIS|id=A061446}}

Any primes that divide <math>F_n</math> and not any of the <math>F_d</math>s are called '''primitive prime factors''' of <math>F_n</math>. The product of the primitive prime factors of the Fibonacci numbers are
:1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 23, 3001, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 107, 24157817, 9349, 135721, 2161, 165580141, 211, 433494437, 13201, 109441, 64079, 2971215073, 1103, 598364773, 15251, ... {{OEIS|id=A178763}}

The first case of more than one primitive prime factor is 4181 = 37 × 113 for <math>F_{19}</math>.

The primitive part has a non-primitive prime factor in some cases. The ratio between the two above sequences is
:1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, .... {{OEIS|id=A178764}}

The [[natural number]]s ''n'' for which <math>F_n</math> has exactly one primitive prime factor are
:3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 43, 45, 47, 48, 51, 52, 54, 56, 60, 62, 63, 65, 66, 72, 74, 75, 76, 82, 83, 93, 94, 98, 105, 106, 108, 111, 112, 119, 121, 122, 123, 124, 125, 131, 132, 135, 136, 137, 140, 142, 144, 145, ... {{OEIS|id=A152012}}

For a prime ''p'', ''p'' is in this sequence if and only if <math>F_p</math> is a Fibonacci prime, and 2''p'' is in this sequence if and only if <math>L_p</math> is a [[Lucas prime]] (where <math>L_p</math> is the <math>p</math>th [[Lucas sequence|Lucas number]]). Moreover, 2<sup>''n''</sup> is in this sequence if and only if <math>L_{2^{n-1}}</math> is a Lucas prime.

The number of primitive prime factors of <math>F_n</math> are
:0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2, 1, 1, 3, 2, 3, 2, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, 1, 3, 2, 4, 1, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 3, 1, 2, 1, 1, 1, 1, 1, 2, 2, 2, ... {{OEIS|id=A086597}}

The least primitive prime factors of <math>F_n</math> are
:1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 37, 41, 421, 199, 28657, 23, 3001, 521, 53, 281, 514229, 31, 557, 2207, 19801, 3571, 141961, 107, 73, 9349, 135721, 2161, 2789, 211, 433494437, 43, 109441, 139, 2971215073, 1103, 97, 101, ... {{OEIS|id=A001578}}

It is conjectured that all the prime factors of  <math>F_n</math> are primitive when  <math>n</math> is a prime number.<ref>The mathematical magic of Fibonacci numbers [http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html#section5 Fibonacci Numbers and Primes]</ref>

==Fibonacci numbers in prime-like sequences==
Although it is not known whether there are infinitely many Fibonacci numbers which are prime, [[Giuseppe Melfi|Melfi]] proved that there are infinitely many which are [[practical number]]s,<ref>{{cite journal|title=A survey on practical numbers |author=Giuseppe Melfi |journal=Rend. Sem. Mat. Torino |volume=53 |year=1995 |pages=347–359 |url=http://www.seminariomatematico.polito.it/rendiconti/cartaceo/53-4/347.pdf}}</ref> a sequence which resembles the primes in some respects.

==See also==
* [[Lucas number]]

==References==
{{Reflist}}

==External links==
* {{MathWorld|title=Fibonacci Prime|urlname=FibonacciPrime}}
* [https://web.archive.org/web/20090906052011/http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibmaths.html#fibprimes R. Knott ''Fibonacci primes'']
* Caldwell, Chris. [http://primes.utm.edu/glossary/page.php/FibonacciNumber.html Fibonacci number], [http://primes.utm.edu/glossary/page.php?sort=FibonacciPrime Fibonacci prime], and [http://primes.utm.edu/top20/page.php?id=39 Record Fibonacci primes] at the [[Prime Pages]]
* [http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html Factorization of the first 300 Fibonacci numbers]
* [http://mersennus.net/fibonacci// Factorization of Fibonacci and Lucas numbers] {{Webarchive|url=https://web.archive.org/web/20160819071116/http://mersennus.net/fibonacci/ |date=2016-08-19 }}
* Small parallel Haskell program to find probable Fibonacci primes at [http://www.haskell.org/haskellwiki/Fibonacci_primes_in_parallel haskell.org]

{{Prime number classes}}

[[Category:Classes of prime numbers]]
[[Category:Fibonacci numbers]]
[[Category:Unsolved problems in number theory]]