Background: The Baillie PSW primality test 1 tests if the number is a square before the Selfridge parameter selection. The Mathematica implementation of PrimeQ does not test if the number is square, but tests if the number is not both a pseudoprime with base 2 and a pseudoprime with base 3. Apparently a square number cannot pass both tests, as otherwise the Selfridge selection would fail. I could not find any example of a square number that passed both tests to about $5\cdot10^{18}$.

My question is: Can it be proved that an odd square number cannot be both pseudoprime with base 2 and a pseudoprime with base 3?

  • $\begingroup$ Mathematica is using strong fermat tests (Miller-Rabin). But I feel, that a weak fermat test will work too. $\endgroup$ – PaulH Sep 11 '18 at 10:03
  • $\begingroup$ A weak fermat test with base 2 produces below $10^{12}$ only 2 pseudoprimes for squares: $1093^2$ and $3511^2$ and with base 3: $11^2$ and $1006003^2$. $\endgroup$ – PaulH Sep 11 '18 at 10:17
  • 2
    $\begingroup$ In fact, a number that passes the weak fermat-test for bases $2$ and $3$ is almost surely squarefree, but whether this is always the case is an open problem. If there is a prime Wieferich to the bases $2$ and $3$ simultaneously, the weak test would not be sufficient, probably not even the strong test. $\endgroup$ – Peter Sep 11 '18 at 10:31
  • 1
    $\begingroup$ @Peter. Thanks for your answers. It is clear to me now. $\endgroup$ – PaulH Sep 11 '18 at 13:10
  • 2
    $\begingroup$ Looking at oeis.org/A005935, I was very surprised to find that 121 is a pseudoprime to base 3. Of course the smallest base 2 pseudoprime is quite famously 341. $\endgroup$ – Robert Soupe Sep 12 '18 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.