Math 2.0

Number theory Theorem

Consecutive Fibonacci numbers are coprime

Builds on Coprime integersGreatest common divisorEuclidean algorithm

Statement

Let (Fn)n≥0(F_n)_{n \ge 0} be the Fibonacci sequence, given by F0=0F_0 = 0, F1=1F_1 = 1 and Fn+2=Fn+1+FnF_{n+2} = F_{n+1} + F_n for n≥0n \ge 0. Then FnF_n and Fn+1F_{n+1} are coprime for each n≥0n \ge 0, that is, gcd⁡(Fn,Fn+1)=1\gcd(F_n, F_{n+1}) = 1.

Remarks

A proof by induction: gcd⁡(Fn+1,Fn+2)=gcd⁡(Fn+1,Fn+2−Fn+1)=gcd⁡(Fn+1,Fn)\gcd(F_{n+1}, F_{n+2}) = \gcd(F_{n+1}, F_{n+2} - F_{n+1}) = \gcd(F_{n+1}, F_n), and gcd⁡(F0,F1)=1\gcd(F_0, F_1) = 1. A stronger fact is gcd⁡(Fm,Fn)=Fgcd⁡(m,n)\gcd(F_m, F_n) = F_{\gcd(m, n)} for all m,n≥0m, n \ge 0. The Euclidean algorithm on Fn+1F_{n+1} and FnF_n takes many steps, and consecutive Fibonacci numbers give its worst case.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph
Divisibility, definition, no evidence levelDivisibilitydefinitionEuclidean algorithm, concept, no evidence levelEuclidean algorithmconceptGreatest common divisor, definition, no evidence levelGreatest common divis…definitionCoprime integers, definition, no evidence levelCoprime integersdefinitionConsecutive Fibonacci numbers are coprime, statement, no evidence levelConsecutive Fibonacci…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Divisibility definition
  2. Euclidean algorithm concept
  3. Greatest common divisor definition
  4. Coprime integers definition
  5. Consecutive Fibonacci numbers are coprime statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Fibonacci_sequence, Divisibility properties
About this page
Tag0D3PFXEAKF
URIm2://0D3PFXEAKF
Kindstatement, theorem
WritingW0 stub
MSC11B39
StatusThis copy of the site has no build data. Run m2 status 0D3PFXEAKF.
UsesCoprime integers, Greatest common divisor, Euclidean algorithm

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.