Fibonacci prime

Fibonacci prime
Number of known terms	49
Conjectured number of terms	Infinite^[1]
First terms	2, 3, 5, 13, 89, 233
Largest known term	F_2904353
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 OEIS):

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

Known Fibonacci primes

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 F_n 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.^[2]

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.^[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 OEIS)

As of September 2015, the largest known certain Fibonacci prime is F₈₁₈₃₉, 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 F_2904353. 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

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

(This implies the infinitude of primes.)

For n ≥ 3, F_n divides F_m 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 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."^[9]

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.

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 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.

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.^[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 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

π_pq>=π_q+π_p+1 {except for π_p²>=π_p+1}

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 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

Main article: Wall–Sun–Sun prime

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 $\left(\tfrac{{p}}{{5}}\right)$ defined as

\left(\frac{p}{5}\right) = \begin{cases} 1 &\text{if }p \equiv \pm1 \pmod 5\\ -1 &\text{if }p \equiv \pm2 \pmod 5 \end{cases}

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-\left(\tfrac{{p}}{{5}}\right)$ , that is, of $p-1$ or $p+1$ .^[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, $p \ge 3, n \ge 2, k \ge 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:

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²)	6	12	25	56	110	91	153	342	552	406	930	703	820	1892	752	1431	3422	915

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)

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

References

↑ http://mathworld.wolfram.com/FibonacciPrime.html
1 2 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
↑ The mathematical magic of Fibonacci numbers Factors of Fibonacci numbers
↑ Jarden - Recurring sequences, Volume 1, Fibonacci quarterly, by Brother U. Alfred
↑ Steven Vajda. Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications. Dover Books on Mathematics.
↑ (sequence A001602 in OEIS)
↑ 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

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

Prime number classes

By formula	Fermat (2^2ⁿ + 1) Mersenne (2^p − 1) Double Mersenne (2^{2^p−1} − 1) Wagstaff (2^p + 1)/3 Proth (k·2ⁿ + 1) Factorial (n! ± 1) Primorial (p_n# ± 1) Euclid (p_n# + 1) Pythagorean (4n + 1) Pierpont (2^u·3^v + 1) Quartan (x⁴ + y⁴) Solinas (2^a ± 2^b ± 1) Cullen (n·2ⁿ + 1) Woodall (n·2ⁿ − 1) Cuban (x³ − y³)/(x − y) Carol (2ⁿ − 1)² − 2 Kynea (2ⁿ + 1)² − 2 Leyland (x^y + y^x) Thabit (3·2ⁿ − 1) Mills (floor(A^3ⁿ))

By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Partitions Bell Motzkin

By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient

Base-dependent	Happy Dihedral Palindromic Emirp Repunit (10ⁿ − 1)/9 Permutable Circular Truncatable Strobogrammatic Minimal Weakly Full reptend Unique Primeval Self Smarandache–Wellin

Patterns	Twin (p, p + 2) Bi-twin chain (n − 1, n + 1, 2n − 1, 2n + 1, …) Triplet (p, p + 2 or p + 4, p + 6) Quadruplet (p, p + 2, p + 6, p + 8) k−Tuple Cousin (p, p + 4) Sexy (p, p + 6) Chen Sophie Germain (p, 2p + 1) Cunningham chain (p, 2p ± 1, …) Safe (p, (p − 1)/2) Arithmetic progression (p + a·n, n = 0, 1, …) Balanced (consecutive p − n, p, p + n)

By size	Titanic (1,000+ digits) Gigantic (10,000+) Mega (1,000,000+) Largest known

Complex numbers	Eisenstein prime Gaussian prime

Composite numbers	Pseudoprime Almost prime Semiprime Interprime

Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap

First 100 primes	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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541

List of prime numbers

This article is issued from Wikipedia - version of the Friday, April 22, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.