Fibonacci sequence is defined by f(1)=1,f(2)=1 and f(m) =f(m1)+f(m2)
i.e. 1, 1, 2, 3, 5, 8, 13, ...
Prove that for all composite values of n>4, f(n) is composite.
What follows is MUCH easier to show by a table than by description  no doubt any errors of expression will be quickly noted and corrected!
1. There are various ways of writing the Fibonacci numbers.
If n = 3, f(n) = 2, or 2*1+1*0. Algebraically, f(3)*m_{1}+f(2)*m_{2}
If n = 4 f(n) = 3, or 2*1+1*1 which is also 3*1+1*0
If n = 5, f(n) = 5, or 2*2+1*1 which is also 3*1+2*1, or 5*1+3*0
If n = 6 f(n) = 8; 2*3+1*2; 3*2+2*1; 5*1+3*1; 8*1+5*0
If n = 7, f(n) = 13; 2*5+1*3; 3*3+2*2; 5*2+3*1; 8*1+5*1; 13*1+8*0
and so on. It is clear that m_{1} and m_{2} are also in the Fibonacci sequence, so that f(n) = f(3)*f(n2)+f(2)*f(n3)=f(4)*f(n3)+f(3)*(n4)=f(5)*f(n4)+f(4)*f(n5) etc., for sufficiently large n; generally, f(n) = f(x)*f(nx+1) +f(x1)*f(nx)  for sufficiently large n.
2. For clarity of exposition, let n = 3, f(x)=2 for f(n) = f(x)*f(nx+1) +f(x1)*f(nx). The first part of the expression, f(x)*f(nx+1) is clearly divisible by 2. Also, f(x1) = 1 and f(nx) = 0, giving 0 as the value of the second part of the expression, so that the whole is divisible by 2. Now let n = 6; we need only evaluate the second part of the expression: f(x1) is still 1; f(nx) is f(3), which is already shown to be even. since any yet higher multiple will simply incorporate the lower (even) multiple, it follows immediately that if n is a multiple of 3, the second part of the expression will always be even.
3. By parity of reasoning, if n=4 or a multiple of 4, f(n) must be a multiple of 3; if n=5 or a multiple of 5, f(n) must be a multiple of 5; if n = 6 or a multiple of 6, f(n) must be a multiple of 8; and so on.
4. The function f(n) = f(x)*f(nx+1) +f(x1)*f(nx) therefore works as a kind of sieve of Eratosthenes over the Fibonacci sequence, with the exception of the number 2. In other words, for n >4 f(n) is composite, unless both :
a. n is singly divisible by 2; and
b. n is not a multiple of 3, or any larger number than 3;
5. Hence, it appears to be necessary, although not sufficient, for n to be prime, if f(n) is to be prime also.
Edited on July 22, 2010, 1:17 pm

Posted by broll
on 20100722 10:12:40 