Lucas pseudoprime

From Wikipedia, the free encyclopedia

In mathematics, Lucas pseudoprimes in number theory are defined in terms of Lucas sequences. Suppose that

$U_n(P,Q) = \frac{a^n-b^n}{a-b}$

is a Lucas sequence, and D is the discriminant for the sequence. If p is an odd prime number for which the Jacobi symbol

$\left(\frac{D}{p}\right) = k \ne 0$ ,

then p is a factor of U_p-k. However, there are also composite numbers satisfying this condition. These numbers are called Lucas pseudoprimes, named by analogy with pseudoprimes.

In the specific case of the Fibonacci sequence, where D = 5, the first pseudoprimes are 323 and 377; $\left(\frac{5}{323}\right)$ and $\left(\frac{5}{377}\right)$ are both −1, the 324th Fibonacci number is a multiple of 323, and the 378th is a multiple of 377.