Fibonacci

A special property

We will consider a remarkable property of the sequence of Fibonacci.
If a and b are positive integers, then the largest number that divides both a and b is denoted by (a,b) (the greatest common divisor (gcd) of a and b).
The sequence of Fibonacci has the following property:
F_(n,m) = (F_n,F_m).
In order to prove this theorem we need some lemmas.

Formula 1.
F_m+n = F_m L_n - (-1)ⁿ F_m-n
Proof: (the values for r and s are defined on the previous page )
(r-s) F_m L_n =
(r^m - s^m) (rⁿ + sⁿ) =
r^m+n - s^m+n + r^msⁿ - rⁿs^m =
(r-s) F_m+n + (rs)ⁿ(r^m-n - s^m-n) =
(r-s) F_m+n + (-1)ⁿ (r-s) F_m-n
We have shown that (r-s) F_m L_n = (r-s) F_m+n + (-1)ⁿ (r-s) F_m-n
and thus that F_m+n = F_m L_n - (-1)ⁿ F_m-n.

Let k be a fixed positive integer. With the help of formula 1 we can prove that F_kn can be divided by F_k for each n:
The statement is correct for n=1 (trivial).
Note that F_2k = F_kL_k, so the statement is also correct for n=2.
Now we will prove that the statement is correct for n=3, and then for n=4, and then for n=5, and so on.
In other words, if we have already proven that the statement is correct for, say, n<=N, how may we prove that the statement is correct for n=N+1? As we have already proven that F_Nk and F_(N-1)k are divisible by F_k
the right hand side of the equation F_(N+1)k = F_Nk L_k - (-1)^k F_(N-1)k is divisible by F_k and therefore also the left hand side. And that is what we wanted to prove.
Apparently the statement is true for each n.

The gcd (n,m) divides both n and m. This shows that F_(n,m) divides both F_n and F_m, and so it divides (F_n,F_m).
We still have to prove that it is the largest of all divisors of (F_n,F_m).
For that we need the following formula:

Formula 2.
F_m L_n - F_n L_m = 2 (-1)ⁿF_m-n
Proof:
(r-s)(F_m L_n - F_n L_m) =
(r^m - s^m)(rⁿ + sⁿ) - (rⁿ - sⁿ)(r^m + s^m) =
r^m+n + r^msⁿ - rⁿs^m - s^m+n - r^m+n - rⁿs^m + r^msⁿ + s^m+n =
2(r^msⁿ - rⁿs^m) =
2(rs)ⁿ(r^n-m - s^n-m) =
(r-s) 2(-1)ⁿF_n-m

We know that F_(n,m) divides F_n as well as F_m.
The question whether a common divisor of F_n and F_m is even can be answered very quickly.
Notice that in both the sequence of Fibonacci and the sequence of Lucas each e(ven) number is followed by 2 o(dd) numbers; the sequences have the following pattern o,o,e,o,o,e,o,o,e,...
Thus a common divisor can only be even if both numbers m en n are divisible by 3.
Suppose for the moment that this is not the case and suppose that X divides F_n as well as F_m. Then X is odd.
We have to show that X <= F_(n,m).
There are positive numbers p and q so that (m,n) = p.m - q.n or so that (m,n) = q.n - p.m. (for a proof see below).
Formula 2 shows that for (e.g.) (m,n) = p.m - q.n: F_pm L_qn - F_qn L_pm = 2 (-1)ⁿF_(m,n)
X divides both F_n and F_m and therefore also F_qn and F_pm and consequently the left hand side. But that means that X divides 2F_(m,n) too and so (as X is odd) F_(m,n). That proves (for (m,n) not a multiple of 3) that F_(m,n) is the greatest common divisor of F_n and F_m.

We supposed that (m,n) was not divisible by 3. If 3 divides (m,n) then we replace formula 2 by F_m L_n/2 - F_n L_m/2 = (-1)ⁿF_m-n. Notice that L_n/2 and L_m/2 are integers.
The proof is analogous to the previous.

We still have to proof:
If (m,n)=1 then there are numbers p and q so that pm+qn=1.
(This yields: if (m,n)=d then there are numbers p and q so that pm+qn=d).
The set V = {um+vn | u,v integers} has a smallest positive element, say b.
Then {kb | k integer} is a subset of V.
Suppose ym+zn is an element of V and there is no integer k such that ym+zn = kb.
Then there is an integer k₁ so that k₁b < ym+zn < (k₁+1)b.
Then 0 < ym+zn - k₁b < b.
As b is the smallest positive element of V this shows that ym+zn - k₁b is not an element of V, which is incorrect.
Then um+vn is divisible by b for each y,z. So m (=1.m+0.n) and n are divisible by b. This shows that b = 1 and there are numbers u and v so that 1 = um+vn.