1392 of ): Although this congruence condition is not, by definition, part of the Lucas probable prime test, it is almost free to check this condition because, as noted above, the value of Vn+1 was computed in the process of computing Un+1. If either congruence () or () is false, this constitutes a proof that n is not prime. If both of these congruences are true, then it is even more likely that n is prime than if we had checked only congruence (). If Selfridge's method (above) for choosing D, P, and Q happened to set Q = −1, then we can adjust P and Q so that D and remain unchanged and P = Q = 5 (see Lucas sequence-Algebraic relations). If we use this enhanced method for choosing P and Q, then 913 = 11·83 is the only composite less than 108 for which congruence () is true (see page 1409 and Table 6 of;). More extensive calculations show that, with this method of choosing D, P, and Q, there are only five odd, composite numbers less than 1015 for which congruence () is true. If , then a further congruence condition that involves very little additional computation can be implemented. Recall that is computed during the calculation of , and we can easily save the previously computed power of , namely, . If n is prime, then, by Euler's criterion, . (Here, is the Legendre symbol; if n is prime, this is the same as the Jacobi symbol). Therefore, if n is prime, we must have, The Jacobi symbol on the right side is easy to compute, so this congruence is easy to check. If this congruence does not hold, then n cannot be prime. Provided GCD(n, Q) = 1 then testing for congruence () is equivalent to augmenting our Lucas test with a "base Q" Solovay–Strassen primality test. Additional congruence conditions that must be satisfied if n is prime are described in Section 6 of. If any of these conditions fails to hold, then we have proved that n is not prime. Comparison with the Miller–Rabin primality test k applications of the Miller–Rabin primality test declare a composite n to be probably prime with a probability at most (1/4)k. There is a similar probability estimate for the strong Lucas probable prime test. Aside from two trivial exceptions (see below), the fraction of (P,Q) pairs (modulo