Editing Fibonacci sequence (section)

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