Euclid (and probably his predecessors) imagined a line segment cut into two pieces of lengths x and y, where x > y, and the ratio of x+y to x equals the ration of x to y. The total over the longer equals the longer over the shorter.
Set x = 1, and 1+y = 1/y. Solve this using the quadratic formula, and y = ½(sqrt(5)-1). the total length, 1+y, is ½(sqrt(5)+1), which is approximately 1.618034. This constant is now called the golden ratio, and is sometimes assigned the Greek letter φ.
The Greeks, ever fascinated with ruler and compass construction, found that φ was a constructable number. (We now know that anything involving square roots is constructable.) They used φ to build the regular pentagon. If a pentagon has sides of length one, its diagonals have length φ. Let's see why this is so.
If a pentagon looks like a house, draw the two diagonals from the apex down to the corners of the floor, building an isosceles triangle that points upward. The triangles on either side are also isosceles, and congruent. Their base angles are half of 180-108, or 36 degrees. Thus the base angles of the central triangle are 108-36, or 72 degrees. We need to prove that the cosine of 72 degrees, or the sine of 18 degrees, is ½ over φ, or 1 over sqrt(5)+1.
Let s and c be the sine and cosine of 18 degrees. The cosine of 5×18 degrees is 0. Use the multiple angle formula to write this.
0 = c5 - 10c3s2 + 5cs4
divide through by c and replace c2 with 1-s2.
0 = 1-12s2+16s4
12s2 = 1 + 16s4
12/s2 = 1/s4 + 16
Remember that 1/s is suppose to be sqrt(5)+1. Substitute in the above and verify the equation. Both sides become 24×sqrt(5)+72. The length of the diagonal is indeed φ.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …
This sequence satisfies the difference equation y(x+2) = y(x) + y(x+1). Equations of this type have exponential solutions, as described in the previous section. Replace y(x) with sx and solve the equation s2 = s+1. apply the quadratic formula, and s = ½(1±sqrt(5)). These are φ and 1-φ respectively. These two solutions are linearly independent, and since the maximum phase shift is 2, they span the entire solution space.
The initial conditions set y(0) = 0 and y(1) = 1. This yields the following solution.
y(x) = (φx - (1-φ)x) / sqrt(5)
Since φ is larger than 1-φ in absolute value, the first term dominates. In other words, the terms of the fibonacci sequence approach φx/sqrt(5). The ratio between two successive terms approaches φ, the golden ratio.
To save time and space I'm going to right f(n) for fib(n).
It is easy to see that the sequence runs: odd odd even odd odd even odd odd even, and so on, so that every third element is even.
Look mod 3 and the series is 1,1,2,0,2,2,1,0, repeat.
Let's generalize this to mod p. We begin 1,1,2 and so on, until that magic moment when we get a 0, if we ever do. Say the prior value is v. The next two values are v and v. After that comes 2v, then 3v, then 5v, and so on. The pattern is the same as before, except multiplied by v. Since p is prime, this isn't going to produce 0 until we reach 0*v. In other words, there is some d such that f(d) f(2d) f(3d) and so on are divisible by p, and nothing else is.
Look at a higher power ph. The sequence starts out 1,1,2,3,5 as usual, and becomes 0 for some index xd. It has to be a multiple of d, since those are the fibonacci numbers divisible by p. Let v be f(xd-1) mod ph. The next two values are v and v. Note that v is not divisible by p. It is therefore relatively prime to ph. The cycle that starts with v v is the same as the cycle that starts with 1 1 - justmultiplied by v, and you don't get 0 until f(2xd). Only the multiples of xd have a fibonnaci number divisible by ph.
For any index d, f(d) is the product of various primes raised to various powers. These all divide f(2d) f(3d) f(4d) etc. If d is the gcd ( m and n, f(d) divides f(m) and f(n), and their gcd.
That's one direction. Let's consider the other direction. Assume ph divides f(m) and f(n). Fibonacci numbers first become divisible by ph at some index l, and l has to divide m and n. Thus l divides d, and ph divides f(d). Do this across all primes, and gcd(f(m),f(n)) divides f(d).
Each divides the other, giving gcd(f(m),f(n)) = f(gcd(m,n)).
This assumes every ph leads to 0 eventually. Look at the sequence mod ph, and suppose it never becomes 0. The possibilities are finite, so the sequence repeats a pair of numbers at some point. Perhaps it attains the values 2,7, and then later on 2,7. We can reverse the process. In both cases the value before 2,7 was 5. Back up all the way to start and find two copies of 1,1. This means the cycle repeats starting at 1,1. And what comes just before the second instance of 1,1? Zero. Thus there is some fibonacci number divisible by ph.
If ph divides f(c) and qi divides f(d), then phqi divides f(cd). For any integer k, there is some fibonacci number divisible by k.
This is not the only sequence that commutes with gcd. Apply the same proof to the following sequence.
f(1) = 1
f(2) = 2
f(n) = f(n-2) + 2f(n-1)