On the Baillie PSW-conjecture

Abstract

The Baillie PSW hypothesis was formulated in 1980 and was named after the authors R. Baillie, C. Pomerance, J. Selfridge and S. Wagstaff. The hypothesis is related to the problem of the existence of odd numbers n \equiv \pm 2 (mod 5), which are both Fermat and Lucas-pseudoprimes (in short, FL-pseudoprimes). A Fermat pseudoprime to base a is a composite number n satisfying the condition an - 1 \equiv 1 (mod n). Base a is chosen to be equal to 2. A Lucas pseudoprime is a composite n satisfying Fn - e(n) \equiv 0 (mod n), where n(e) is the Legendre symbol e(n) = \bigl( n 5 \bigr) , Fm the mth term of the Fibonacci series. According to Baillie’s PSW conjecture, there are no FL-pseudoprimes. If the hypothesis is true, the combined primality test checking Fermat and Lucas conditions for odd numbers not divisible by 5 gives the correct answer for all numbers of the form n \equiv \pm 2 (mod 5), which generates a new deterministic polynomial primality test detecting the primality of 60 percent of all odd numbers in just two checks. In this work, we continue the study of FL-pseudoprimes, started in our article "On a combined primality test" published in the journal "Izvestia VUZov.Matematika" No. 12 in 2022. We have established new restrictions on probable FL-pseudoprimes and described new algorithms for checking FL-primality, and with the help of them we proved the absence of such numbers up to the boundary B = 1021, which is more than 30 times larger than the previously known boundary 264 found by J. Gilchrist in 2013. An inaccuracy in the formulation of theorem 4 in the mentioned article has also been corrected.