Lucas sequence

Lucas sequences are the particular generalisation of sequences like Fibonacci numbers, Lucas numbers, Pell numbers or Jacobsthal numbers. Every of this sequences has one common factor. They could be generatet over quadratic equatations of the form: $x^{2}-Px+Q=0\$.

There exists kinds of Lucas sequences:

• Sequence $U(P,Q)=(U_{n}(P,Q))_{n\geq 1}$ with $U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}$
• Sequence $V(P,Q)=(V_{n}(P,Q))_{n\geq 1}$ with $U_{n}(P,Q)=a^{n}+b^{n}\$

$a\$ and $b\$ are the solutions $a={\frac {P+{\sqrt {P^{2}-4Q}}}{2}}$ and $b={\frac {P-{\sqrt {P^{2}-4Q}}}{2}}$ of the quadratic equatation $x^{2}-Px+Q=0\$.

Properties

• The variables $a\$ and $b\$, and the parameter $P\$ and $Q\$ are interdependent. So it is true, that $P=a+b\$ and $Q=a\cdot b.$.
• For every sequence $U(P,Q)=(U_{n}(P,Q))_{n\geq 1}$ is it true, that $U_{0}=0\$ and $U_{1}=1\$.
• For every sequence $V(P,Q)=(V_{n}(P,Q))_{n\geq 1}$ is it true, that $V_{0}=2\$ and $V_{1}=P\$.

For every Lucas sequence is true that

• $U_{2n}=U_{n}\cdot V_{n}\$
• $V_{n}=U_{n+1}-QU_{n-1}\$
• $V_{2n}=V_{n}^{2}-2Q^{n}\$
• $\operatorname {ggT} (U_{m},U_{n})=U_{\operatorname {ggT} (m,n)}$
• $m\mid n\implies U_{m}\mid U_{n}$; für alle $U_{m}\neq 1$

Fibonacci numbers and Lucas numbers

The both best-known Lucas sequences are the Fibonacci numbers $U(1,-1)\$ and the Lucas numbers $V(1,-1)\$ with $a={\frac {1+{\sqrt {5}}}{2}}$ and $b={\frac {1-{\sqrt {5}}}{2}}$.

Lucas sequences and the Prime numbers

Is the natural number $p\$ a Prime number, then it is true, that

• $p\$ divides $U_{p}(P,Q)-\left({\frac {D}{p}}\right)$
• $p\$ divides $V_{p}(P,Q)-P\$

Fermat's little theorem you can see as a special case of $p\$ divides $(V_{n}(P,Q)-P)\$ because $a^{p}\equiv a\mod p$ is äquivalent to $V_{p}(a+1,a)\equiv V_{1}(a+1,a)\mod p$

The converse (If $n\$ divides $U_{n}(P,Q)-\left({\frac {D}{n}}\right)$ then is $n\$ a prime number and if $m\$ divides $V_{m}(P,Q)-P\$ then is $m\$ a prime number) is false and lead to Fibonacci pseudoprimes respectively to Lucas pseudoprimes.

Further reading

• The new Book of Primenumber Records, Paolo Ribenboim, ISBN 0-387-94457-5
• My Numbers, my Friends, Paolo Ribenboim, ISBN 0-387-98911-0