Fibonacci Numbers and the Legendre Symbol

brittneyscheer 15 Mar 2009 23:28

While just looking up different things about the Legendre Symbol, I found that it can be related to the Fibonacci numbers.

So the Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … are defined by the recurrence F1 = F2 = 1, Fn+1 = Fn + Fn-1.

If p is a prime number then F_{p-$(\frac{p}{5})$} is congruent to 0 (mod p), and then F_{p} is congruent to $(\frac{p}{5})$ (mod p).

So for example,

$(\frac{2}{5})$= -1, F_{3}=2, F_{2}=1,

$(\frac{3}{5})$= -1, F_{4}=3, F_{3}=2,

$(\frac{5}{5})$ = 0, F_{5}=5,

$(\frac{7}{5})$= -1, F_{8}=21, F_{7}=13,

$(\frac{11}{5})$ = +1, F_{10}=55, F_{11}=89.

This result comes from the theory of Lucas sequences, which are used in primality tests.