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) = (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

$(D/p) = 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; (5/323) and (5/377) are both −1, the 324th Fibonacci number is a multiple of 323, and the 378th is a multiple of 377.