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.
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:
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.
Below you can put in a P and Q and generate the Nth Lucas numbers.
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:
ap mod p
a mod p
There is an analogue theorem for Lucas Numbers:
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
Try it out below using the same P and Q and N as above:
P2 - 4Q
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.