Fibonacci prime

Last updated
Fibonacci prime
No. of known terms15
Conjectured no. of termsInfinite [1]
First terms 2, 3, 5, 13, 89, 233
Largest known termF6530879
OEIS index
  • A001605
  • Indices of prime Fibonacci numbers

A Fibonacci prime is a Fibonacci number that is prime, a type of integer sequence prime.

Contents

The first Fibonacci primes are (sequence A005478 in the 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?

It is not known whether there are infinitely many Fibonacci primes. With the indexing starting with F1 = F2 = 1, the first 37 indices n for which Fn is prime are (sequence A001605 in the OEIS ):

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, 130021, 148091, 201107.

(Note that the actual values Fn rapidly become very large, so, for practicality, only the indices are listed.)

In addition to these proven Fibonacci primes, several probable primes have been found:

n = 397379, 433781, 590041, 593689, 604711, 931517, 1049897, 1285607, 1636007, 1803059, 1968721, 2904353, 3244369, 3340367, 4740217, 6530879. [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 index results in a Fibonacci prime). That is to say, the Fibonacci sequence is a divisibility sequence.

Fp is prime for 8 of the first 10 primes p; the exceptions are F2 = 1 and F19 = 4181 = 37 × 113. However, Fibonacci primes appear to become rarer as the index increases. Fp is prime for only 26 of the 1229 primes p smaller than 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 2023, the largest known certain Fibonacci prime is F201107, with 42029 digits. It was proved prime by Maia Karpovich in September 2023. [4] The largest known probable Fibonacci prime is F6530879. It was found by Ryan Propper in August 2022. [2] It was proved by Nick MacKinnon that the only Fibonacci numbers that are also twin primes are 3, 5, and 13. [5]

Divisibility of Fibonacci numbers

A prime divides if and only if p is congruent to ±1 modulo 5, and p divides if and only if it is congruent to ±2 modulo 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: [6]

For n  3, Fn divides Fm if and only if n divides m. [7]

If we suppose that m is a prime number p, and n is less than p, then it is clear that Fp cannot share any common divisors with the preceding Fibonacci numbers.

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.

If k | n then except for
If k = 1, and n is an odd prime, then 1 | p and
n012345678910111213141516171819202122232425
Fn0112358132134558914423337761098715972584418167651094617711286574636875025
πn00011111222121233132432142

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

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.

Therefore:

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 )

p2357111317192329313741434753596167717379838997
πp0111111211232112223222124

Rank of apparition

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). The rank of apparition a(p) is defined for every prime p. [10] The rank of apparition divides the Pisano period π(p) and allows to determine all Fibonacci numbers divisible by p. [11]

For the divisibility of Fibonacci numbers by powers of a prime, and

In particular

Wall–Sun–Sun primes

A prime p ≠ 2, 5 is called a Fibonacci–Wieferich prime or a Wall–Sun–Sun prime if where

and is the Legendre symbol:

It is known that for p ≠ 2, 5, a(p) is a divisor of: [12]

For every prime p that is not a Wall–Sun–Sun prime, as illustrated in the table below:

p23571113171923293137414347535961
a(p)345810791824143019204416275815
a(p2)612255611091153342552406930703820189275214313422915

The existence of Wall–Sun–Sun primes is conjectural.

Fibonacci primitive part

Because , we can divide any Fibonacci number by the least common multiple of all where . The result is called the primitive part of . The primitive parts 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, ... (sequence A061446 in the OEIS )

Any primes that divide and not any of the s are called primitive prime factors of . 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, ... (sequence A178763 in the OEIS )

The first case of more than one primitive prime factor is 4181 = 37 × 113 for .

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, .... (sequence A178764 in the OEIS )

The natural numbers n for which 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, ... (sequence A152012 in the OEIS )

For a prime p, p is in this sequence if and only if is a Fibonacci prime, and 2p is in this sequence if and only if is a Lucas prime (where is the th Lucas number). Moreover, 2n is in this sequence if and only if is a Lucas prime.

The 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 factors 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 )

It is conjectured that all the prime factors of are primitive when is a prime number. [13]

Fibonacci numbers in prime-like sequences

Although it is not known whether there are infinitely primes in the Fibonacci sequence, Melfi proved that there are infinitely many primes [14] among practical numbers, a prime-like sequence.

See also

Related Research Articles

<span class="mw-page-title-main">Fibonacci sequence</span> Numbers obtained by adding the two previous ones

In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted Fn. The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes from 1 and 2. Starting from 0 and 1, the first few values in the sequence are:

The Möbius function μ(n) is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated Moebius) in 1832. It is ubiquitous in elementary and analytic number theory and most often appears as part of its namesake the Möbius inversion formula. Following work of Gian-Carlo Rota in the 1960s, generalizations of the Möbius function were introduced into combinatorics, and are similarly denoted μ(x).

<span class="mw-page-title-main">Quadratic reciprocity</span> Gives conditions for the solvability of quadratic equations modulo prime numbers

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:

<span class="mw-page-title-main">Euler's totient function</span> Number of integers coprime to and not exceeding n

In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as or , and may also be called Euler's phi function. In other words, it is the number of integers k in the range 1 ≤ kn for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n.

2 (two) is a number, numeral and digit. It is the natural number following 1 and preceding 3. It is the smallest and only even prime number. Because it forms the basis of a duality, it has religious and spiritual significance in many cultures.

<span class="mw-page-title-main">Root of unity</span> Number that has an integer power equal to 1

In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power n. Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, and the discrete Fourier transform.

In number theory, a k-hyperperfect number is a natural number n for which the equality holds, where σ(n) is the divisor function (i.e., the sum of all positive divisors of n). A hyperperfect number is a k-hyperperfect number for some integer k. Hyperperfect numbers generalize perfect numbers, which are 1-hyperperfect.

In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.

In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers. Because there are infinitely many prime numbers, there are also infinitely many semiprimes. Semiprimes are also called biprimes.

63 (sixty-three) is the natural number following 62 and preceding 64.

In number theory, Carmichael's theorem, named after the American mathematician R. D. Carmichael, states that, for any nondegenerate Lucas sequence of the first kind Un(PQ) with relatively prime parameters PQ and positive discriminant, an element Un with n ≠ 1, 2, 6 has at least one prime divisor that does not divide any earlier one except the 12th Fibonacci number F(12) = U12(1, −1) = 144 and its equivalent U12(−1, −1) = −144.

Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.

<span class="mw-page-title-main">Pisano period</span> Period of the Fibonacci sequence modulo an integer

In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 1774.

<span class="mw-page-title-main">Practical number</span> Number such that it and all smaller numbers may be represented as sums of its distinct divisors

In number theory, a practical number or panarithmic number is a positive integer such that all smaller positive integers can be represented as sums of distinct divisors of . For example, 12 is a practical number because all the numbers from 1 to 11 can be expressed as sums of its divisors 1, 2, 3, 4, and 6: as well as these divisors themselves, we have 5 = 3 + 2, 7 = 6 + 1, 8 = 6 + 2, 9 = 6 + 3, 10 = 6 + 3 + 1, and 11 = 6 + 3 + 2.

In algebra, Gauss's lemma, named after Carl Friedrich Gauss, is a statement about polynomials over the integers, or, more generally, over a unique factorization domain. Gauss's lemma underlies all the theory of factorization and greatest common divisors of such polynomials.

Cubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x3 ≡ p (mod q) is solvable; the word "reciprocity" comes from the form of the main theorem, which states that if p and q are primary numbers in the ring of Eisenstein integers, both coprime to 3, the congruence x3p is solvable if and only if x3q is solvable.

744 is the natural number following 743 and preceding 745.

The square root of 5 is the positive real number that, when multiplied by itself, gives the prime number 5. It is more precisely called the principal square root of 5, to distinguish it from the negative number with the same property. This number appears in the fractional expression for the golden ratio. It can be denoted in surd form as:

In number theory, a cyclotomic field is a number field obtained by adjoining a complex root of unity to Q, the field of rational numbers.

<span class="mw-page-title-main">Chebyshev's bias</span>

In number theory, Chebyshev's bias is the phenomenon that most of the time, there are more primes of the form 4k + 3 than of the form 4k + 1, up to the same limit. This phenomenon was first observed by Russian mathematician Pafnuty Chebyshev in 1853.

References

  1. "Fibonacci Prime".
  2. 1 2 PRP Top Records, Search for : F(n). Retrieved 2018-04-05.
  3. Sloane's OEIS:  A005478 , OEIS:  A001605
  4. "The Top Twenty: Fibonacci Number". primes.utm.edu. Retrieved 15 September 2023.
  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
  8. The mathematical magic of Fibonacci numbers Factors of Fibonacci numbers
  9. Jarden - Recurring sequences, Volume 1, Fibonacci quarterly, by Brother U. Alfred
  10. (sequence A001602 in the OEIS )
  11. 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.
  12. Steven Vajda. Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications. Dover Books on Mathematics.
  13. The mathematical magic of Fibonacci numbers Fibonacci Numbers and Primes
  14. Giuseppe Melfi (1995). "A survey on practical numbers" (PDF). Rend. Sem. Mat. Torino. 53: 347–359.