Editing Fibonacci sequence (section)

== Primes and divisibility ==

=== Divisibility properties ===
Every third number of the sequence is even (a multiple of <math>F_3=2</math>) and, more generally, every {{mvar|k}}-th number of the sequence is a multiple of ''F<sub>k</sub>''. Thus the Fibonacci sequence is an example of a [[divisibility sequence]]. In fact, the Fibonacci sequence satisfies the stronger divisibility property<ref>{{Citation | first = Paulo | last = Ribenboim | author-link = Paulo Ribenboim | title = My Numbers, My Friends | publisher = Springer-Verlag | year = 2000}}</ref><ref>{{Citation | last1 = Su | first1 = Francis E | others = et al | publisher = HMC | url = http://www.math.hmc.edu/funfacts/ffiles/20004.5.shtml | contribution = Fibonacci GCD's, please | year = 2000 | title = Mudd Math Fun Facts | access-date = 2007-02-23 | archive-url = https://web.archive.org/web/20091214092739/http://www.math.hmc.edu/funfacts/ffiles/20004.5.shtml | archive-date = 2009-12-14 | url-status = dead }}</ref>
<math display=block>\gcd(F_a,F_b,F_c,\ldots) = F_{\gcd(a,b,c,\ldots)}\,</math>
where {{math|gcd}} is the [[greatest common divisor]] function.  (This relation is different if a different indexing convention is used, such as the one that starts the sequence with {{tmath|1=F_0 = 1}} and {{tmath|1=F_1 = 1}}.)

In particular, any three consecutive Fibonacci numbers are pairwise [[Coprime integers|coprime]] because both <math>F_1=1</math> and <math>F_2 = 1</math>.  That is,
: <math>\gcd(F_n, F_{n+1}) = \gcd(F_n, F_{n+2}) = \gcd(F_{n+1}, F_{n+2}) = 1</math>
for every {{mvar|n}}.

Every [[prime number]] {{mvar|p}} divides a Fibonacci number that can be determined by the value of {{mvar|p}} [[modular arithmetic|modulo]]&nbsp;5. If {{mvar|p}} is congruent to 1 or 4 modulo 5, then {{mvar|p}} divides {{math|''F''<sub>''p''−1</sub>}}, and if {{mvar|p}} is congruent to 2 or 3 modulo 5, then, {{mvar|p}} divides {{math|''F''<sub>''p''+1</sub>}}. The remaining case is that {{math|1=''p'' = 5}}, and in this case {{mvar|p}} divides ''F<sub>p</sub>''.

<math display=block>\begin{cases} p =5 & \Rightarrow p \mid F_{p}, \\ p \equiv \pm1 \pmod 5 & \Rightarrow p \mid F_{p-1}, \\ p \equiv \pm2 \pmod 5 &  \Rightarrow p \mid F_{p+1}.\end{cases}</math>

These cases can be combined into a single, non-[[piecewise]] formula, using the [[Legendre symbol]]:<ref>{{citation
 | last = Williams | first = H. C.
 | doi = 10.4153/CMB-1982-053-0 | doi-access=free
 | issue = 3
 | journal = [[Canadian Mathematical Bulletin]]
 | mr = 668957
 | pages = 366–70
 | title = A note on the Fibonacci quotient <math>F_{p-\varepsilon}/p</math>
 | volume = 25
 | year = 1982| hdl = 10338.dmlcz/137492
 | hdl-access = free
 }}. Williams calls this property "well known".</ref>
<math display=block>p \mid F_{p \;-\, \left(\frac{5}{p}\right)}.</math>

=== Primality testing ===
The above formula can be used as a [[primality test]] in the sense that if
<math display=block>n \mid F_{n \;-\, \left(\frac{5}{n}\right)},</math>
where the Legendre symbol has been replaced by the [[Jacobi symbol]], then this is evidence that {{mvar|n}} is a prime, and if it fails to hold, then {{mvar|n}} is definitely not a prime. If {{mvar|n}} is [[composite number|composite]] and satisfies the formula, then {{mvar|n}} is a ''Fibonacci pseudoprime''.  When {{mvar|m}} is large{{snd}}say a 500-[[bit]] number{{snd}}then we can calculate {{math|''F''<sub>''m''</sub> (mod ''n'')}} efficiently using the matrix form.  Thus

<math display=block> \begin{pmatrix} F_{m+1} & F_m \\ F_m & F_{m-1} \end{pmatrix} \equiv \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^m \pmod n.</math>
Here the matrix power {{math|''A''<sup>''m''</sup>}} is calculated using [[modular exponentiation]], which can be [[Modular exponentiation#Matrices|adapted to matrices]].<ref>''Prime Numbers'', Richard Crandall, Carl Pomerance, Springer, second edition, 2005, p. 142.</ref>

=== Fibonacci primes ===
{{Main|Fibonacci prime}}

A ''Fibonacci prime'' is a Fibonacci number that is [[prime number|prime]]. The first few are:<ref>{{Cite OEIS|1=A005478|2=Prime Fibonacci numbers|mode=cs2}}</ref>

: 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, ...

Fibonacci primes with thousands of digits have been found, but it is not known whether there are infinitely many.<ref>{{citation
 | last = Diaconis
 | first = Persi
 | author-link = Persi Diaconis
 | editor1-last = Butler
 | editor1-first = Steve
 | editor1-link = Steve Butler (mathematician)
 | editor2-last = Cooper
 | editor2-first = Joshua
 | editor3-last = Hurlbert
 | editor3-first = Glenn
 | contribution = Probabilizing Fibonacci numbers
 | contribution-url = https://statweb.stanford.edu/~cgates/PERSI/papers/probabilizing-fibonacci.pdf
 | isbn = 978-1-107-15398-1
 | mr = 3821829
 | pages = 1–12
 | publisher = Cambridge University Press
 | title = Connections in Discrete Mathematics: A Celebration of the Work of Ron Graham
 | year = 2018
 | access-date = 2022-11-23
 | archive-date = 2023-11-18
 | archive-url = https://web.archive.org/web/20231118192225/https://statweb.stanford.edu/~cgates/PERSI/papers/probabilizing-fibonacci.pdf
 | url-status = dead
 }}</ref>

{{math|''F''<sub>''kn''</sub>}} is divisible by {{math|''F''<sub>''n''</sub>}}, so, apart from {{math|1=''F''<sub>4</sub> = 3}}, any Fibonacci prime must have a prime index. As there are [[Arbitrarily large|arbitrarily long]] runs of [[composite number]]s, there are therefore also arbitrarily long runs of composite Fibonacci numbers.

No Fibonacci number greater than {{math|1=''F''<sub>6</sub> = 8}} is one greater or one less than a prime number.<ref>{{Citation | first = Ross | last = Honsberger | title = Mathematical Gems III | journal = AMS Dolciani Mathematical Expositions | year = 1985 | isbn = 978-0-88385-318-4 | page = 133 | issue = 9}}</ref>

The only nontrivial [[square number|square]] Fibonacci number is 144.<ref>{{citation | last = Cohn | first = J. H. E. | doi = 10.1112/jlms/s1-39.1.537 | journal = The Journal of the London Mathematical Society | mr = 163867 | pages = 537–540 | title = On square Fibonacci numbers | volume = 39 | year = 1964}}</ref>  Attila Pethő proved in 2001 that there is only a finite number of [[perfect power]] Fibonacci numbers.<ref>{{Citation | first = Attila | last = Pethő | title = Diophantine properties of linear recursive sequences II | journal = Acta Mathematica Academiae Paedagogicae Nyíregyháziensis | volume = 17 | year = 2001 | pages = 81–96}}</ref> In 2006, Y. Bugeaud, M. Mignotte, and S. Siksek proved that 8 and 144 are the only such non-trivial perfect powers.<ref>{{Citation|first1=Y|last1=Bugeaud|first2=M|last2= Mignotte|first3=S|last3=Siksek|title = Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers | journal = Ann. Math.|volume = 2 | year = 2006 | pages = 969–1018 | issue = 163 | bibcode = 2004math......3046B | arxiv = math/0403046| doi = 10.4007/annals.2006.163.969|s2cid=10266596}}</ref>

1, 3, 21, and 55 are the only [[triangular number|triangular]] Fibonacci numbers, which was [[conjecture]]d by [[Verner Emil Hoggatt Jr.|Vern Hoggatt]] and proved by Luo Ming.<ref>{{Citation|first=Ming|last=Luo|title = On triangular Fibonacci numbers | journal = Fibonacci Quart. | volume = 27 | issue = 2 | year = 1989 | pages = 98–108 |doi=10.1080/00150517.1989.12429576 | url = https://www.fq.math.ca/Scanned/27-2/ming.pdf }}</ref>

No Fibonacci number can be a [[perfect number]].<ref name="Luca2000">{{citation | first=Florian | last=Luca | title=Perfect Fibonacci and Lucas numbers | journal=Rendiconti del Circolo Matematico di Palermo | year=2000 | volume=49 | issue=2 | pages=313–18 | doi=10.1007/BF02904236 | mr=1765401 | s2cid=121789033 | issn=1973-4409 }}</ref> More generally, no Fibonacci number other than 1 can be [[multiply perfect number|multiply perfect]],<ref name="BGLLHT2011">{{citation | first1=Kevin A. | last1=Broughan | first2=Marcos J. | last2=González | first3=Ryan H. | last3=Lewis | first4=Florian | last4=Luca | first5=V. Janitzio | last5=Mejía Huguet | first6=Alain | last6=Togbé | title=There are no multiply-perfect Fibonacci numbers | journal=Integers | year=2011 | volume=11a | page=A7 | url=https://math.colgate.edu/~integers/vol11a.html | mr=2988067 }}</ref> and no ratio of two Fibonacci numbers can be perfect.<ref name="LucaMH2010">{{citation | first1=Florian | last1=Luca | first2= V. Janitzio | last2=Mejía Huguet | title=On Perfect numbers which are ratios of two Fibonacci numbers | journal=Annales Mathematicae at Informaticae | year=2010 | volume=37 | pages=107–24 | url=http://ami.ektf.hu/index.php?vol=37 | mr=2753031 | issn=1787-6117 }}</ref>

=== Prime divisors ===
With the exceptions of 1, 8 and 144 ({{math|1=''F''<sub>1</sub> = ''F''<sub>2</sub>}}, {{math|''F''<sub>6</sub>}} and {{math|''F''<sub>12</sub>}}) every Fibonacci number has a prime factor that is not a factor of any smaller Fibonacci number ([[Carmichael's theorem]]).<ref>{{Citation | first = Ron | last = Knott | url = http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html | title = The Fibonacci numbers | publisher = Surrey | place = UK}}</ref> As a result, 8 and 144 ({{math|''F''<sub>6</sub>}} and {{math|''F''<sub>12</sub>}}) are the only Fibonacci numbers that are the product of other Fibonacci numbers.<ref>{{Cite OEIS|1=A235383|2=Fibonacci numbers that are the product of other Fibonacci numbers|mode=cs2}}</ref>

The divisibility of Fibonacci numbers by a prime {{mvar|p}} is related to the [[Legendre symbol]] <math>\bigl(\tfrac{p}{5}\bigr)</math> which is evaluated as follows:
<math display=block>\left(\frac{p}{5}\right) = \begin{cases} 0 & \text{if } p = 5\\ 1 & \text{if } p \equiv \pm 1 \pmod 5\\ -1 & \text{if } p \equiv \pm 2 \pmod 5.\end{cases}</math>

If {{mvar|p}} is a prime number then
<math display=block> F_p \equiv \left(\frac{p}{5}\right) \pmod p \quad \text{and}\quad F_{p-\left(\frac{p}{5}\right)} \equiv 0 \pmod p.</math><ref>{{Citation | first = Paulo | last = Ribenboim | author-link = Paulo Ribenboim | year = 1996 | title = The New Book of Prime Number Records | place = New York | publisher = Springer | isbn = 978-0-387-94457-9 | page = 64}}</ref>{{Sfn | Lemmermeyer | 2000 | loc = ex. 2.25–28 | pp = 73–74}}

For example,
<math display=block>\begin{align}
\bigl(\tfrac{2}{5}\bigr) &= -1, &F_3  &= 2, &F_2&=1, \\
\bigl(\tfrac{3}{5}\bigr) &= -1, &F_4  &= 3,&F_3&=2, \\
\bigl(\tfrac{5}{5}\bigr) &= 0, &F_5  &= 5, \\
\bigl(\tfrac{7}{5}\bigr) &= -1, &F_8  &= 21,&F_7&=13, \\
\bigl(\tfrac{11}{5}\bigr)& = +1, &F_{10}&  = 55, &F_{11}&=89.
\end{align}</math>

It is not known whether there exists a prime {{mvar|p}} such that

<math display=block>F_{p-\left(\frac{p}{5}\right)} \equiv 0 \pmod{p^2}.</math>

Such primes (if there are any) would be called [[Wall–Sun–Sun prime]]s.

Also, if {{math|''p'' ≠ 5}} is an odd prime number then:{{Sfn | Lemmermeyer | 2000 | loc = ex. 2.28 | pp = 73–74}}
<math display=block>5 {F_{\frac{p \pm 1}{2}}}^2 \equiv \begin{cases}
\tfrac{1}{2} \left (5\bigl(\tfrac{p}{5}\bigr)\pm 5 \right ) \pmod p & \text{if } p \equiv 1 \pmod 4\\
\tfrac{1}{2} \left (5\bigl(\tfrac{p}{5}\bigr)\mp 3 \right ) \pmod p & \text{if } p \equiv 3 \pmod 4.
\end{cases}</math>

'''Example 1.''' {{math|1=''p'' = 7}}, in this case {{math|1=''p'' ≡ 3 (mod 4)}} and we have:
<math display=block>\bigl(\tfrac{7}{5}\bigr) = -1: \qquad \tfrac{1}{2}\left(5 \bigl(\tfrac{7}{5}\bigr)+3 \right ) =-1, \quad \tfrac{1}{2} \left(5\bigl(\tfrac{7}{5}\bigr)-3 \right )=-4.</math>
<math display=block>F_3=2 \text{ and } F_4=3.</math>
<math display=block>5{F_3}^2=20\equiv -1 \pmod {7}\;\;\text{ and }\;\;5{F_4}^2=45\equiv -4 \pmod {7}</math>

'''Example 2.''' {{math|1=''p'' = 11}}, in this case {{math|1=''p'' ≡ 3 (mod 4)}} and we have:
<math display=block>\bigl(\tfrac{11}{5}\bigr) = +1: \qquad  \tfrac{1}{2}\left( 5\bigl(\tfrac{11}{5}\bigr)+3 \right)=4, \quad \tfrac{1}{2} \left(5\bigl(\tfrac{11}{5}\bigr)- 3 \right)=1.</math>
<math display=block>F_5=5 \text{ and } F_6=8.</math>
<math display=block>5{F_5}^2=125\equiv 4 \pmod {11} \;\;\text{ and }\;\;5{F_6}^2=320\equiv 1 \pmod {11}</math>

'''Example 3.''' {{math|1=''p'' = 13}}, in this case {{math|1=''p'' ≡ 1 (mod 4)}} and we have:
<math display=block>\bigl(\tfrac{13}{5}\bigr) = -1: \qquad \tfrac{1}{2}\left(5\bigl(\tfrac{13}{5}\bigr)-5 \right) =-5, \quad \tfrac{1}{2}\left(5\bigl(\tfrac{13}{5}\bigr)+ 5 \right)=0.</math>
<math display=block>F_6=8 \text{ and } F_7=13.</math>
<math display=block>5{F_6}^2=320\equiv -5 \pmod {13} \;\;\text{ and }\;\;5{F_7}^2=845\equiv 0 \pmod {13}</math>

'''Example 4.''' {{math|1=''p'' = 29}}, in this case {{math|1=''p'' ≡ 1 (mod 4)}} and we have:
<math display=block>\bigl(\tfrac{29}{5}\bigr) = +1: \qquad \tfrac{1}{2}\left(5\bigl(\tfrac{29}{5}\bigr)-5 \right)=0, \quad \tfrac{1}{2}\left(5\bigl(\tfrac{29}{5}\bigr)+5 \right)=5.</math>
<math display=block>F_{14}=377 \text{ and } F_{15}=610.</math>
<math display=block>5{F_{14}}^2=710645\equiv 0 \pmod {29} \;\;\text{ and }\;\;5{F_{15}}^2=1860500\equiv 5 \pmod {29}</math>

For odd {{mvar|n}}, all odd prime divisors of {{math|''F''<sub>''n''</sub>}} are congruent to 1 modulo 4, implying that all odd divisors of {{math|1=''F''<sub>''n''</sub>}} (as the products of odd prime divisors) are congruent to 1 modulo 4.{{Sfn | Lemmermeyer | 2000 | loc = ex. 2.27 | p = 73}}

For example,
<math display=block>F_1 = 1,\ F_3 = 2,\ F_5 = 5,\ F_7 = 13,\ F_9 = {\color{Red}34} = 2 \cdot 17,\ F_{11} = 89,\ F_{13} = 233,\ F_{15} = {\color{Red}610} = 2 \cdot 5 \cdot 61.</math>

All known factors of Fibonacci numbers {{math|''F''(''i'')}} for all {{math|''i'' < 50000}} are collected at the relevant repositories.<ref>{{Citation | url = https://mersennus.net/fibonacci/ | title = Fibonacci and Lucas factorizations | publisher = Mersennus}} collects all known factors of {{math|''F''(''i'')}} with {{math|''i'' < 10000}}.</ref><ref>{{Citation | url =http://fibonacci.redgolpe.com/ | title = Factors of Fibonacci and Lucas numbers | publisher = Red golpe}} collects all known factors of {{math|''F''(''i'')}} with {{math|10000 < ''i'' < 50000}}.</ref>

=== Periodicity modulo ''n'' ===
{{Main|Pisano period}}

If the members of the Fibonacci sequence are taken mod&nbsp;{{mvar|n}}, the resulting sequence is [[periodic sequence|periodic]] with period at most&nbsp;{{math|6''n''}}.<ref>{{Citation | title = Problems and Solutions: Solutions: E3410 | last1 = Freyd | first1 = Peter | last2 = Brown | first2 = Kevin S. | journal = The American Mathematical Monthly | volume = 99 | issue = 3 | pages = 278–79 |date= 1993 | doi=10.2307/2325076| jstor = 2325076 }}</ref> The lengths of the periods for various {{mvar|n}} form the so-called [[Pisano period]]s.<ref>{{Cite OEIS|1=A001175|2=Pisano periods (or Pisano numbers): period of Fibonacci numbers mod n|mode=cs2}}</ref> Determining a general formula for the Pisano periods is an [[open problem]], which includes as a subproblem a special instance of the problem of finding the [[multiplicative order]] of a [[modular arithmetic|modular integer]] or of an element in a [[finite field]]. However, for any particular {{mvar|n}}, the Pisano period may be found as an instance of [[cycle detection]].