Editing Lucas pseudoprime (section)

===Checking additional congruence conditions===
If we have checked that congruence ({{EquationNote|2}}) is true, there are additional congruence conditions we can check that have almost no additional computational cost.  By providing an additional opportunity for ''n'' to be proved composite, these increase the reliability of the test.

If ''n'' is an odd prime and <math>\left(\tfrac{D}{n}\right)=-1</math>, then we have the following:{{r|lpsp|p=1392 Eq. 2}}

{{NumBlk|:|<math>V_{n+1} \equiv 2 Q \pmod n.</math>|{{EquationRef|3}}}}

Although this congruence condition is not part of the Lucas probable prime test proper, it is almost free to check this condition because, as noted above, the easiest way to compute ''U''<sub>''n''+1</sub> is to compute ''V''<sub>''n''+1</sub> as well.

If  Selfridge's method (above) for choosing parameters is modified so that, if it selects ''D'' = 5, it uses the parameters ''P'' = ''Q'' = 5 rather than ''P'' = 1, ''Q'' = −1, then 913 = 11·83 is the ''only'' composite less than 10<sup>8</sup> for which congruence ({{EquationNote|3}}) is true (see page 1409 and Table 6 of;<ref name="lpsp"/>). More extensive calculations show that, with this method of choosing ''D'', ''P'', and ''Q'', there are only five odd, composite numbers less than 10<sup>15</sup> for which congruence ({{EquationNote|3}}) is true.<ref name=bpsw2>{{cite journal |first1=Robert |last1=Baillie |first2=Andrew |last2=Fiori |first3=Samuel S. Jr. |last3=Wagstaff |author-link3=Samuel S. Wagstaff, Jr. |title=Strengthening the Baillie-PSW Primality Test |journal=Mathematics of Computation |date=July 2021 |volume=90 |issue=330 |pages=1931–1955 |doi=10.1090/mcom/3616 |arxiv=2006.14425 |s2cid=220055722 }}</ref>

If <math>Q \neq \pm 1 </math> (and GCD(''n'', ''Q'') = 1), then an [[Euler–Jacobi probable prime]] test to the base Q can also be implemented at minor computational cost.

The computation of <math>V_{n+1}</math> depends on <math>V_{(n+1)/2}</math> and <math>Q^{(n+1)/2}</math>.  This is <math>Q</math> times <math>Q^{(n-1)/2}</math>, and if ''n'' is prime, then by [[Euler's criterion]],
:<math>  Q^{(n-1)/2} \equiv \left(\tfrac{Q}{n}\right) \pmod {n}  </math> .
(Here, <math>\left(\tfrac{Q}{n}\right)</math> is the [[Legendre symbol]]; if ''n'' is prime, this is the same as the Jacobi symbol).

Therefore, if ''n'' is prime, we must have,
{{NumBlk|:|<math>Q^{(n+1)/2} \equiv Q \cdot Q^{(n-1)/2} \equiv Q \cdot \left(\tfrac{Q}{n}\right) \pmod n.</math>|{{EquationRef|4}}}}

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 ({{EquationNote|4}}) is equivalent to augmenting our Lucas test with a "base Q" [[Solovay–Strassen primality test]].

There is one more<!--There are two conditions, equations (3) and (4) from the paper, but if the V_{n+1} condition (2) is true, then they are equivalent.--> congruence condition on <math>U_n</math> and <math>V_n</math> which must be true if ''n'' is prime and can be checked.{{r|lpsp|p=§2,6}}