Fibonacci prime

Fibonacci prime

Number of known terms	49
Conjectured number of terms	Infinite
First terms	2, 3, 5, 13, 89, 233
Largest known term	F2904353
OEIS index	A001605

A Fibonacci prime is a Fibonacci number that is prime, a type of integer sequence prime.

The first Fibonacci primes are (sequence A005478 in OEIS):

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, ....

Known Fibonacci primes

Open problem in mathematics: Are there an infinite number of Fibonacci primes? (more open problems in mathematics)

It is not known whether there are infinitely many Fibonacci primes. The first 33 are F_n for the n values (sequence A001605 in OEIS):

3, 4, 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.

In addition to these proven Fibonacci primes, there have been found probable primes for

n = 104911, 130021, 148091, 201107, 397379, 433781, 590041, 593689, 604711, 931517, 1049897, 1285607, 1636007, 1803059, 1968721, 2904353.

Except for the case n = 4, all Fibonacci primes have a prime index, because if a divides b, then $F_a$ also divides $F_b$, but not every prime is the index of a Fibonacci prime.

F_p is prime for 8 of the first 10 primes p; the exceptions are F₂ = 1 and F₁₉ = 4181 = 37 × 113. However, Fibonacci primes become rarer as the index increases. F_p is prime for only 26 of the 1,229 primes p below 10,000. 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, ... (sequence A080345 in OEIS)

As of September 2015, the largest known certain Fibonacci prime is F₈₁₈₃₉, with 17103 digits. It was proved prime by David Broadhurst and Bouk de Water in 2001. The largest known probable Fibonacci prime is F_2904353. It has 606974 digits and was found by Henri Lifchitz in 2014. It was shown by Nick MacKinnon that the only Fibonacci numbers that are also members of the set of prime twins are 3, 5 and 13.

Divisibility of Fibonacci numbers

A prime p≠5 divides F_p-1 if and only if p is congruent to ±1 (mod 5), and p divides F_p+1 if and only if is congruent to ±2 (mod 5). (For p=5, F₅=5 so 5 divides F₅)

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

GCD(F_n, F_m) = F_GCD(n,m).

(This implies the infinitude of primes.)

For n ≥ 3, F_n divides F_m iff n divides m.

If we suppose that m is a prime number p from the identity above, and n is less than p, then it is clear that F_p, cannot share any common divisors with the preceding Fibonacci numbers.

GCD(F_p, F_n) = F_GCD(p,n) = F₁ = 1

This means that F_p 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.

• 1. "F_nk is a multiple of F_k for all values of n and k from 1 up."

It's safe to say that F_nk will have "at least" the same number of distinct prime factors as F_k.

All F_p will have no factors of F_k, but "at least" one new characteristic prime from Carmichael's theorem.

• 2. Carmichael's Theorem applies to all Fibonacci numbers except 4 special cases. {except for 1, 8 and 144}

"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 π_n be the number of distinct prime factors of F_n. ( [[OEIS:{{{id}}}|{{{id}}}]])

If k | n then π_n >= π_k+1. {except for π₆ = π₃ = 1}

If k=1, and n is an odd prime, then 1 | p and π_p >= π₁+1, or simply put π_p>=1.

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
Fn	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
πn	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_n is to divide out the prime factors of all earlier Fibonacci numbers F_k for which k | n.

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_pq are characteristic, except for those of F_p and F_q.

GCD(F_pq, F_q) = F_GCD(pq,q) = F_q

GCD(F_pq, F_p) = F_GCD(pq,p) = F_p

π_pq>=π_q+π_p+1 {except for π_p²>=π_p+1}

For example, F₂₄₇ π_(19*13)>=(π₁₃+π₁₉)+1.

The number of distinct prime factors of the Fibonacci numbers with a prime index is directly relevant to the counting function.( A080345)

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
πp	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

Fibonacci–Wieferich Wall-Sun-Sun prime

A prime p ≠ 2, 5 is called a Fibonacci–Wieferich prime or a Wall-Sun-Sun prime if p² divides the Fibonacci number F_q, where q is p minus the Legendre symbol $\textstyle\left(\frac{{p}}{{5}}\right)$ defined as

$\left(\frac{p}{5}\right) = \begin{cases} 1 &\text{if }p \equiv \pm1 \pmod 5\\ -1 &\text{if }p \equiv \pm2 \pmod 5 \end{cases}$

Let F_u, u > 0, be the smallest Fibonacci number divisibly by the prime p.

The subscript u is called the rank of apparition of p, and we know that it is a factor of, or equal to, p–1 or p+1.

Let FEP_p be the Fibonacci Entry Point of p, which is the smallest index of a Fibonacci number that has p as a factor.

FEP_p <= q

p | F_q

For some factor k>=1, p will divide this Fibonacci number satisfying u = (q/k):

p | F_{q / k}

The rank of apparition of p, is periodicity, for divisibility of Fibonacci numbers by the n-th prime.

For the greatest divisibility of Fibonacci numbers by powers of a prime, p >= 3, n >= 2, k >= 0:

pⁿ | F_ukp^n-1

Subsequently, for n=2 and k=1 we get:

p² | F_pu

The rank of apparition of p, multiplied by p, indicates an early appearance of p² in the Fibonacci sequence.

pu > q $\infty$

p	2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61
u	3	4	5	8	10	7	9	18	24	14	30	19	20	44	16	27	58	15
n	6	12	25	56	110	91	153	342	552	406	930	703	820	1892	752	1431	3422	915

Fibonacci primitive part

The primitive part 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, ... (sequence A178763 in OEIS)

The natural number n for which the primitive part of $F_n$ is prime 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, ... (sequence A152012 in OEIS)

Number of primitive prime factors of $F_n$ 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, ... (sequence A086597 in OEIS)

The least primitive prime factor of $F_n$ 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, ... (sequence A001578 in OEIS)

If and only if a prime p is in this sequence, then $F_p$ is a Fibonacci prime, and if and only if 2p is in this sequence, then $L_p$ is a Lucas prime (where $L_n$ is the Lucas sequence), and if and only if 2ⁿ is in this sequence, then $L_{2^{n-1}}$ is a Lucas prime.

See also

• Lucas number

External links

• Weisstein, Eric W., "Fibonacci Prime", MathWorld.
• R. Knott Fibonacci primes
• Caldwell, Chris. Fibonacci number, Fibonacci prime, and Record Fibonacci primes at the Prime Pages
• Factorization of the first 300 Fibonacci numbers
• Factorization of Fibonacci and Lucas numbers
• Small parallel Haskell program to find probable Fibonacci primes at haskell.org