TAOCP 1.2.8 Exercise 7
Assume that $n$ is composite.
Section 1.2.8: Fibonacci Numbers
Exercise 7. [15] If $n$ is not a prime number, $F_n$ is not a prime number (with one exception). Prove this and find the exception.
Verified: no
Solve time: -
Solution
Assume that $n$ is composite. Then there exist integers $a,b$ such that
$$ n=ab, \qquad a>1, \qquad b>1. $$
By the remark following Eq. (6), if $m$ is a multiple of $n$, then $F_m$ is a multiple of $F_n$. Since $n=ab$, the index $n$ is a multiple of $a$, hence $F_n$ is a multiple of $F_a$.
Now $a>1$, so $F_a\ge F_2=1$. If $a>2$, then
$$ F_a \ge F_3 = 2, $$
and because $b>1$ we have $n=ab>a$, hence
$$ F_n > F_a, $$
since the Fibonacci numbers are strictly increasing for $n\ge 2$. Therefore, when $a>2$, $F_n$ has a divisor $F_a$ satisfying
$$ 1<F_a<F_n, $$
so $F_n$ is not prime.
The only remaining case is $a=2$. Since $n=ab$ with $b>1$, this means $n$ is even. Every third Fibonacci number is even, and in particular
$$ F_2=1,\qquad F_4=3,\qquad F_6=8,\qquad \ldots $$
Because $n=2b$ with $b>1$, we have $n\ge 4$. Again by the divisibility consequence of Eq. (6), $F_n$ is a multiple of $F_2=1$, which gives no information. We must examine the smallest even composite index separately.
If $n=4$, then
$$ F_4=3, $$
which is prime.
If $n>4$ is even, then $n$ is a multiple of $2$ and satisfies $n\ge 6$. Since every third Fibonacci number is even, $F_6=8$ and the sequence is increasing; moreover $F_n$ is divisible by $F_2=1$ and, because $n$ has a divisor $a>2$ unless $n$ is a power of $2$, the previous argument applies. For powers of $2$ with $n\ge 8$, observe that $4\mid n$, hence $F_n$ is a multiple of $F_4=3$, and
$$ F_n>F_4. $$
Thus $F_n$ is composite.
Hence the unique exception is $n=4$, for which $n$ is not prime but $F_n$ is prime. Therefore, if $n$ is not prime, then $F_n$ is not prime, except when
$$ n=4. $$
Since
$$ F_4=3, $$
the exception is
$$ \boxed{n=4}. $$