Fibonacci prime

Known Fibonacci primes

It is not known whether there are infinitely many Fibonacci primes. With the indexing starting with F₁ = F₂ = 1, the first 33 are F_n for the n values (sequence A001605 in the OEIS):

n = 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, 104911.

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

n = 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 the OEIS)

As of March 2017, the largest known certain Fibonacci prime is F₁₃₀₀₂₁, with 21925 digits. It was proved prime by Mathew Steine and Bouk de Water in 2015. 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."

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. (sequence A022307 in the OEIS) 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.

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

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. (sequence A080345 in the OEIS)

Wall-Sun-Sun primes

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 ( p 5 ) defined as

( p 5 ) = { 1 if  p ≡ ± 1 ( mod 5 ) − 1 if  p ≡ ± 2 ( mod 5 )

For a prime p, the smallest index u > 0 such that F_u is divisible by p is called the rank of apparition (sometimes called Fibonacci entry point) of p and denoted a(p). It is known that for p ≠ 2, 5, a(p) is a divisor of p − ( p 5 ) , that is, of p − 1 or p + 1 .

The rank of apparition a(p) is defined for every prime p. The rank of apparition divides the Pisano period π(p) and allows to determine all Fibonacci numbers divisible by p.

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

For every prime p that is not a Wall-Sun-Sun prime, a(p²) = a(p) · p as illustrated in the table below:

Fibonacci primitive part

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

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

The first case of more than one primitive prime factor is 4181 = 37 × 113 for F 19 .

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, .... (sequence A178764 in the OEIS)

The natural numbers n for which F n 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, ... (sequence A152012 in the 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.

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 the 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 the OEIS)