Lucas numbers are a generalization of Fibonacci numbers. Let X2-PX+Q be a polynomial in X where P and Q are not zero. Let a and b be the solutions. We assume D = P2 - 4Q does not equal zero. Then we define the Lucas numbers as

          Un(P,Q) = (an-bn)/(a-b)
          Vn(P,Q) = an+bn

This means U0(P,Q) = 0 and U1(P,Q) = 1. V0(P,Q) = 2 and V1(P,Q)=P.

Fibonacci numbers come from the special case Un(1,-1) which produce the Fibonacci numbers.
          1,1,2,3,5,8,13...
The Fibonacci numbers obey the law Fn = Fn-1+Fn-2

For the Lucas numbers there are similar recurrence formulas:

          Un(P,Q) = P Un-1(P,Q) - Q Un-2(P,Q)
          Vn(P,Q) = P Vn-1(P,Q) - Q Vn-2(P,Q)

If P=3 Q=2 then

          Un(3,2) = 2n - 1
          Vn(3,2) = 2n + 1

As can be seen many sequences can be generated by Lucas numbers.

Lucas numbers can be used to test whether a number is prime. An example of those type of tests is the following:

Theorem

Let N > 1 be an odd integer and suppose that qi are the prime factors of N+1. Assume that there exist a D such that D mod p does not equal a2 mod p for any a, and for every qi there exists a Lucas sequence U(i) with Pi2-4 Qi=D, where Pi,Qi have no common prime factors or Qi and N have no common prime factors and such that N divides U(i)N+1 and N does not divide U(i)N/qi. Then N is prime.

All the tests for N being prime are like this with various partial factorizations of N+1.

 

Below you can put in  a P and Q and generate the Nth Lucas numbers.

         P                                                    Q                                                 N

                                   

U                  V    



Fermat's Little Theorem
If p is a prime and a is an integer then ap is congruent to a mod p.
Test it out:

p        a          ap mod p                       a mod p                                                                   
                                                               

There is an analogue theorem for Lucas Numbers:

Theorem
Let p be an odd prime (not 2).
If p divides P and p divides Q then p divides UN for every N>1.
If p divides P and p does not divide Q then p divides UN exactly when  N is even.
If p does not divide P and p divides Q then p does not divide UN for N ≥ 1.
If p does not divide P and p does not divide Q and p divides P2-4Q then p divides UN exactly when p divides N.

Try it out below using the same P and Q and N as above:

 P               Q                 N                 U              P2 - 4Q        
 

 p                                                                               

                                                               

           


Disclaimer: There may be overflow because Lucas numbers get large fast. This will be indicated where U appears. It will say Overflow occured

Reference: All material about Lucas numbers is taken from The Little Book of Bigger Primes by Paulo Ribenboim. There is a lot more about Lucas numbers in the book. It's a fun book about primes though its heavy on the mathematics.


by the Coding Zebra