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.