Fibonacci prime

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

List of unsolved problems in mathematics
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 F_a also divides F_b, 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] In completely different hand, Nick MacKinnon proved 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[edit]

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[edit]

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 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 2n is in this sequence, then L_{2^{n-1}} is a Lucas prime.

See also[edit]

References[edit]

  1. ^ a b PRP Top Records, Search for : F(n). Retrieved 2014-08-12.
  2. ^ Sloane's OEISA005478, OEISA001605
  3. ^ Number Theory Archives announcement by David Broadhurst and Bouk de Water
  4. ^ Chris Caldwell, The Top Twenty: Fibonacci Number from the Prime Pages. Retrieved 2009-11-21.
  5. ^ N. MacKinnon, Problem 10844, Amer. Math. Monthly 109, (2002), p. 78
  6. ^ Paulo Ribenboim, My Numbers, My Friends, Springer-Verlag 2000
  7. ^ Wells 1986, p.65

External links[edit]