Fibonacci prime
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):
Known Fibonacci primes
Are there an infinite number of Fibonacci primes? |
It is not known whether there are infinitely many Fibonacci primes. The first 33 are Fn 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.[1]
Except for the case n = 4, all Fibonacci primes have a prime index, because if a divides b, then also divides
, but not every prime is the index of a Fibonacci prime.
Fp is prime for 8 of the first 10 primes p; the exceptions are F2 = 1 and F19 = 4181 = 37 × 113. However, Fibonacci primes become rarer as the index increases. Fp is prime for only 26 of the 1,229 primes p below 10,000.[2]
As of August 2014, the largest known certain Fibonacci prime is F81839, with 17103 digits. It was proved prime by David Broadhurst and Bouk de Water in 2001.[3][4] The largest known probable Fibonacci prime is F2904353. It has 606974 digits and was found by Henri Lifchitz in 2014.[1] 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.[5]
Divisibility of Fibonacci numbers
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(Fn, Fm) = FGCD(n,m).[6]
(This implies the infinitude of primes.)
For n ≥ 3, Fn divides Fm iff n divides m.[7]
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 Fp, cannot share any common divisors with the preceding Fibonacci numbers.
- GCD(Fp, Fn) = FGCD(p,n) = F1 = 1
Carmichael's theorem states that every Fibonacci number (except for 1, 8 and 144) has at least one prime factor that has not been a factor of the preceding Fibonacci numbers.
If and only if a prime p congruent to 1 or 4 (mod 5), then p divides Fp-1, otherwise, p divides Fp+1. (The only exception is p = 5, if and only if p = 5, then p divides Fp)
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)
These natural number ns which the primitive part of 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 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 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 is a Fibonacci prime, and if and only if 2p is in this sequence, then
is a Lucas prime (where
is the Lucas sequence), and if and only if 2n is in this sequence, then
is a Lucas prime.
See also
References
- ↑ 1.0 1.1 PRP Top Records, Search for : F(n). Retrieved 2014-08-12.
- ↑ Sloane's
A005478,
A001605
- ↑ Number Theory Archives announcement by David Broadhurst and Bouk de Water
- ↑ Chris Caldwell, The Top Twenty: Fibonacci Number from the Prime Pages. Retrieved 2009-11-21.
- ↑ N. MacKinnon, Problem 10844, Amer. Math. Monthly 109, (2002), p. 78
- ↑ Paulo Ribenboim, My Numbers, My Friends, Springer-Verlag 2000
- ↑ Wells 1986, p.65
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
|