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.