Template:Infobox integer sequence
A Fibonacci prime is a Fibonacci number that is prime, a type of integer sequence prime.
The first Fibonacci primes are OEIS A{{{1}}}:
Known Fibonacci primesEdit
Template:Unsolved It is not known whether there are infinitely many Fibonacci primes. With the indexing starting with Template:Nowrap, the first 34 are F_{n} for the n values OEIS A{{{1}}}:
- 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, 3244369.^{[1]}
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_{2} = 1 and F_{19} = 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.^{[2]} 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 AA080345
Template:As of, the largest known certain Fibonacci prime is F_{104911}, with 21925 digits. It was proved prime by Mathew Steine and Bouk de Water in 2015.^{[3]} The largest known probable Fibonacci prime is F_{3244369}. It was found by Henri Lifchitz in 2017.^{[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.^{[4]}
Divisibility of Fibonacci numbersEdit
A prime
$ p \neq 5 $ divides
$ F_{p-1} $ if and only if p is congruent to ±1 modulo 5, and p divides
$ F_{p+1} $ if and only if is congruent to ±2 modulo 5. (For p = 5, F_{5} = 5 so 5 divides F_{5})
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:^{[5]}
- $ \gcd(F_n, F_m) = F_{\gcd(n,m)}, $
which implies the infinitude of primes.
For Template:Math, F_{n} divides F_{m} iff n divides m.^{[6]}
If we suppose that m is a prime number p, 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 = 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.
- F_{nk} is a multiple of F_{k} for all values of n and k from 1 up.^{[7]} 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.
- Carmichael's Theorem applies to all Fibonacci numbers except 4 special cases:
$ F_1 =F_2 =1, F_6 = 8 $ and $ F_{12} = 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 A{{{1}}}
- If k | n then
$ \pi_n \geqslant \pi_k +1 $ except for $ \pi_6 = \pi_3 =1. $
- If k = 1, and n is an odd prime, then 1 | p and
$ \pi_p \geqslant \pi_1 +1 = 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 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
F_{n} | 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.^{[8]}
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}.
- $ \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} $
Therefore:
- $ \pi_{pq} \geqslant \begin{cases} \pi_p + \pi_q + 1 & p\neq q \\ \pi_p + 1 & p = q \end{cases} $
The number of distinct prime factors of the Fibonacci numbers with a prime index is directly relevant to the counting function. OEIS A{{{1}}}
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 |
Rank of ApparitionEdit
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). The rank of apparition a(p) is defined for every prime p.^{[9]} The rank of apparition divides the Pisano period π(p) and allows to determine all Fibonacci numbers divisible by p.^{[10]}
For the divisibility of Fibonacci numbers by powers of a prime,
$ p \geqslant 3, n \geqslant 2 $ and
$ k \geqslant 0 $
- $ p^n \mid F_{a(p)kp^{n-1}}. $
In particular
- $ p^2 \mid F_{a(p)p}. $
Wall-Sun-Sun primes Edit
A prime p ≠ 2, 5 is called a Fibonacci–Wieferich prime or a Wall-Sun-Sun prime if
$ p^2 \mid F_q, $ where
- $ q = p - \left(\frac{{p}}{{5}}\right) $
in which
$ \left(\tfrac{{p}}{{5}}\right) $ is the Legendre symbol defined as:
- $ \left(\frac{p}{5}\right) = \begin{cases} 1 & p \equiv \pm 1 \bmod 5\\ -1 & p \equiv \pm 2 \bmod 5 \end{cases} $
It is known that for p ≠ 2, 5, a(p) is a divisor of:^{[11]}
- $ 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} $
For every prime p that is not a Wall-Sun-Sun prime,
$ a(p^2) = p a(p) $ as illustrated in the table below:
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^{2}) | 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 conjectural.
Fibonacci primitive partEdit
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, ... OEIS A{{{1}}}
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 A{{{1}}}
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, .... OEIS A{{{1}}}
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, ... OEIS A{{{1}}}
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^{n} 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, ... OEIS A{{{1}}}
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, ... OEIS A{{{1}}}
See alsoEdit
ReferencesEdit
- ↑ ^{1.0} ^{1.1} PRP Top Records, Search for : F(n). Retrieved 2017-03-03.
- ↑ Sloane's Template:OEIS2C, Template:OEIS2C
- ↑ Chris Caldwell, The Top Twenty: Fibonacci Number from the Prime Pages. Retrieved 2017-03-03.
- ↑ N. MacKinnon, Problem 10844, Amer. Math. Monthly 109, (2002), p. 78
- ↑ Paulo Ribenboim, My Numbers, My Friends, Springer-Verlag 2000
- ↑ Wells 1986, p.65
- ↑ The mathematical magic of Fibonacci numbers Factors of Fibonacci numbers
- ↑ Jarden - Recurring sequences, Volume 1, Fibonacci quarterly, by Brother U. Alfred
- ↑ OEIS AA001602
- ↑ Template:High-risk Template:Citation Style documentation/lua Template:Citation Style documentation/cs1 Template:Citation Style documentation/lead
- ↑ Template:Cite book
External linksEdit
- Template: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