n) that declare a composite n to be probably prime is at most (4/15). Therefore, k applications of the strong Lucas test would declare a composite n to be probably prime with a probability at most (4/15)k. There are two trivial exceptions. One is n = 9. The other is when n = p(p+2) is the product of two twin primes. Such an n is easy to factor, because in this case, n+1 = (p+1)2 is a perfect square. One can quickly detect perfect squares using Newton's method for square roots. By combining a Lucas pseudoprime test with a Fermat primality test, say, to base 2, one can obtain very powerful probabilistic tests for primality, such as the Baillie–PSW primality test. Fibonacci pseudoprimes When P = 1 and Q = −1, the Un(P,Q) sequence represents the Fibonacci numbers. A Fibonacci pseudoprime is often defined as a composite number n not divisible by 5 for which congruence () holds with P = 1 and Q = −1 (but n is ). By this definition, the Fibonacci pseudoprimes form a sequence: 323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877, ... . The references of Anderson and Jacobsen below use this definition. If n is congruent to 2 or 3 modulo 5, then Bressoud, and Crandall and Pomerance point out that it is rare for a Fibonacci pseudoprime to also be a Fermat pseudoprime base 2. However, when n is congruent to 1 or 4 modulo 5, the opposite is true, with over 12% of Fibonacci pseudoprimes under 1011 also being base-2 Fermat pseudoprimes. If n is prime and GCD(n, Q) = 1, then we also have This leads to an alternative definition of Fibonacci pseudoprime: a Fibonacci pseudoprime is a composite number n for which congruence () holds with P = 1 and Q = −1. This definition leads the Fibonacci pseudoprimes form a sequence: 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251, ... , which are also referred to as Bruckman-Lucas pseudoprimes. Hoggatt and Bicknell studied properties of these pseudoprimes in 1974. Singmaster computed these pseudoprimes up to 100000. Jacobsen lists all 111443 of these pseudoprimes less than 1013. It has been shown that there are no even Fibonacci pseudoprimes as defined by equation (5). However, even Fibonacci pseudoprimes do exist under the first definition given by (). A strong Fibonacci pseudoprime is a composite number n