Fibonacci prime

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Fibonacci prime
Number of known terms 49
Conjectured number of terms Infinite[1]
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 the OEIS):

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

Known Fibonacci primes[edit]

Question dropshade.png Unsolved problem in mathematics:
Are there an infinite number of Fibonacci primes?
(more unsolved problems in mathematics)


It is not known whether there are infinitely many Fibonacci primes. The first 33 are Fn for the n values (sequence A001605 in the 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.[2]

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.[3] 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 September 2015, the largest known certain Fibonacci prime is F81839, with 17103 digits. It was proved prime by David Broadhurst and Bouk de Water in 2001.[4][5] The largest known probable Fibonacci prime is F2904353. It has 606974 digits and was found by Henri Lifchitz in 2014.[2] 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.[6]

Divisibility of Fibonacci numbers[edit]

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

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).[7]

(This implies the infinitude of primes.)

For n ≥ 3, Fn divides Fm iff n divides m.[8]

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

This means that Fp 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. "Fnk is a multiple of Fk for all values of n and k from 1 up."[9]
It's safe to say that Fnk will have "at least" the same number of distinct prime factors as Fk.
All Fp will have no factors of Fk, 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 Fn. (sequence A022307 in the OEIS)
If k | n then πn >= πk+1. {except for π6 = π3 = 1}
If k=1, and n is an odd prime, then 1 | p and πp >= π1+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 Fn is to divide out the prime factors of all earlier Fibonacci numbers Fk for which k | n.[10]

The exact quotients left over are prime factors that have not yet appeared.

If p and q are both primes, then all factors of Fpq are characteristic, except for those of Fp and Fq.

GCD(Fpq, Fq) = FGCD(pq,q) = Fq
GCD(Fpq, Fp) = FGCD(pq,p) = Fp
πpq>=πqp+1 {except for πp2>=πp+1}

For example, F247 π(19*13)>=(π1319)+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)

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

Wall-Sun-Sun primes[edit]

A prime p ≠ 2, 5 is called a Fibonacci–Wieferich prime or a Wall-Sun-Sun prime if p2 divides the Fibonacci number Fq, where q is p minus the Legendre symbol defined as

For a prime p, the smallest index u > 0 such that Fu 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 , that is, of or .[11]

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

For the greatest divisibility of Fibonacci numbers by powers of a prime, :

pn | Fukpn-1

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

p2 | Fpu

For every prime p that is not a Wall-Sun-Sun prime, a(p2) = a(p) · 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(p2) 6 12 25 56 110 91 153 342 552 406 930 703 820 1892 752 1431 3422 915

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

The natural number n for 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 the 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.

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

See also[edit]

References[edit]

  1. ^ http://mathworld.wolfram.com/FibonacciPrime.html
  2. ^ a b PRP Top Records, Search for : F(n). Retrieved 2014-08-12.
  3. ^ Sloane's OEISA005478, OEISA001605
  4. ^ Number Theory Archives announcement by David Broadhurst and Bouk de Water
  5. ^ Chris Caldwell, The Top Twenty: Fibonacci Number from the Prime Pages. Retrieved 2009-11-21.
  6. ^ N. MacKinnon, Problem 10844, Amer. Math. Monthly 109, (2002), p. 78
  7. ^ Paulo Ribenboim, My Numbers, My Friends, Springer-Verlag 2000
  8. ^ Wells 1986, p.65
  9. ^ The mathematical magic of Fibonacci numbers Factors of Fibonacci numbers
  10. ^ Jarden - Recurring sequences, Volume 1, Fibonacci quarterly, by Brother U. Alfred
  11. ^ Steven Vajda. Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications. Dover Books on Mathematics. 
  12. ^ (sequence A001602 in the OEIS)
  13. ^ John Vinson (1963). "The Relation of the Period Modulo m to the Rank of Apparition of m in the Fibonacci Sequence" (PDF). Fibonacci Quarterly 1: 37–45. 

External links[edit]