with different D, P and Q, then unless one of the tests proves that n is composite, we gain more confidence that n is prime. Examples: If P = 3, Q = −1, and D = 13, the sequence of Us is : U0 = 0, U1 = 1, U2 = 3, U3 = 10, etc. First, let n = 19. The Jacobi symbol is −1, so δ(n) = 20, U20 = 6616217487 = 19·348221973 and we have Therefore, 19 is a Lucas probable prime for this (P, Q) pair. In this case 19 is prime, so it is not a Lucas pseudoprime. For the next example, let n = 119. We have = −1, and we can compute However, 119 = 7·17 is not prime, so 119 is a Lucas pseudoprime for this (P, Q) pair. In fact, 119 is the smallest pseudoprime for P = 3, Q = −1. We will see below that, in order to check equation () for a given n, we do not need to compute all of the first n + 1 terms in the U sequence. Let Q = −1, the smallest Lucas pseudoprime to P = 1, 2, 3, ... are 323, 35, 119, 9, 9, 143, 25, 33, 9, 15, 123, 35, 9, 9, 15, 129, 51, 9, 33, 15, 21, 9, 9, 49, 15, 39, 9, 35, 49, 15, 9, 9, 33, 51, 15, 9, 35, 85, 39, 9, 9, 21, 25, 51, 9, 143, 33, 119, 9, 9, 51, 33, 95, 9, 15, 301, 25, 9, 9, 15, 49, 155, 9, 399, 15, 33, 9, 9, 49, 15, 119, 9, ... Strong Lucas pseudoprimes Now, factor into the form where is odd. A strong Lucas pseudoprime for a given (P, Q) pair is an odd composite number n with GCD(n, D) = 1, satisfying one of the conditions or for some 0 ≤ r < s; see page 1396 of. A strong Lucas pseudoprime is also a Lucas pseudoprime (for the same (P, Q) pair), but the converse is not necessarily true. Therefore, the strong test is a more stringent primality test than equation (). There are infinitely many strong Lucas pseudoprimes, and therefore, infinitely many Lucas pseudoprimes. Theorem 7 in states: Let and be relatively prime positive integers for which is positive but not a square. Then there is a positive constant (depending on and ) such