[seqfan] Re: Primes p = nk-1 dividing Fibonacci( k )

[Max Alekseyev]

On Thu, Nov 26, 2009 at 12:44 PM, Max Alekseyev <maxale at gmail.com> wrote:
> On Wed, Nov 25, 2009 at 6:33 PM, Maximilian Hasler
> <maximilian.hasler at gmail.com> wrote:
>
>> Least prime p = -1 (mod n) which divides Fibonacci((p+1)/n), or 0 if
>> there is no such prime < 99999
>> I get
>>
>> 2, 13, 47, 0, 0, 113, 307, 0, 233, 0, 967, 0, 2417, 797, 0, 0, 1087,
>> 233, 5737, 0, 5417, 5653, 1103, 0, 0, 2417, 4373, 0, 6263, ...
>>
>> Has anyone a simple and/or universal explanation for the 0's ?
>
> Only multiples of 4 and 5 seems to be excluded.
>
> For multiples of 5, there is a simple explanation:
> If n is a mulpliple of 5 and  p==-1 (mod n), then p == -1 (mod 5) and
> thus p divides F(p-1). But if p also divides F((p+1)/n) then it
> divides F(gcd(p-1,(p+1)/n))=F(1)=1, a contradiction.

Zero for multiples of 4 can be explained as follows.
Let n==0 (mod 4) and prime p==-1 (mod 4) be such that p divides
F((p+1)/4). Arguments similar to the above imply that 5 is not a
square modulo p.
According to Binet's formula, we have the following equality in the
field Z_p(sqrt(5)):
((1+sqrt(5))/2)^((p+1)/4) = ((1-sqrt(5))/2)^((p+1)/4)
implying that
((1+sqrt(5))/2)^((p+1)/2) = (-1)^((p+1)/4)
Squaring, we have:
((1+sqrt(5))/2)^(p+1) = 1.
But ((1+sqrt(5))/2)^(p+1) equals the norm of (1+sqrt(5))/2 that is -1.
The contradiction proves that the required p does not exist.

Max