FT17: Divisibility Properties for the Fibonacci Numbers

Let's look at the first two congruences from the previous section:

• F(kn + m) ≡ (−1)^nk/2 F (m) (mod F(n)),
  for k even.

• F(kn + m) ≡ (−1)^n(k−1)/2 F (m) F(n−1) (mod F(n)),
  for k odd.

Since F(0) = 0, we can take m = 0 here to see that:

• n | j implies F(n) | F(j)

(where "x | y" means "y is a multiple of x").

Here's a direct consequence of this:

• If F(n) is prime, then either n is prime or n=4.

In fact, we can improve on the divisibility property. We'll show that:

• gcd(F(m), F(n)) = F(gcd(m, n)) for non-zero m and n.

To see this, first observe that it's sufficient to look at positive m and n, since F(−x) = ±F(x).

Also, for x > 1, it's easy to see by induction that F(x−1) and F(x) are relatively prime.

Now, since gcd(m, n) | m and gcd(m, n) | n, the divisibility property above tells us that F(gcd(m, n)) is a common divisor of F(m) and F(n).

To complete the proof, we'll use mathematical induction. If the claim fails, we can let n be the least positive integer for which (*) there exists a positive integer m < n such that F(m) and F(n) have a common divisor d > F(gcd(m, n)).

Divide n by m to write n = qm + r, with 0 ≤ r < m.

Note that r > 0, since if m | n, we already know that there is no such d.

By the congruence for F, we have

F(n) = F (qm + r) ≡ ±F(r) or ±F(r) F(m−1) (mod F(m)).

So at least one of the four numbers ±F(r) or ±F(r) F(m−1) is equal to F(n) plus some multiple of F(m).

Since d divides both F(m) and F(n), d also divides at least one of the four numbers ±F(r) or ±F(r) F(m−1).

Now, d and F(m−1) are relatively prime; this is because d divides F(m), which is relatively prime to F(m−1). It follows that d divides F(r).

So we know that 0 < r < m and that d is a common divisor of F(r) and F(m). Also, n = qm+r, so gcd(r, m) = gcd(n, m), and hence that d > F(gcd(r, m)). But this contradicts the choice of n as the least positive number satisfying (*), completing the proof by induction.