# Prove that an odd square cannot be a pseudoprime with both base 2 and base 3

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?

• Mathematica is using strong fermat tests (Miller-Rabin). But I feel, that a weak fermat test will work too. – PaulH Sep 11 '18 at 10:03
• 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$. – PaulH Sep 11 '18 at 10:17
• 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. – Peter Sep 11 '18 at 10:31
• @Peter. Thanks for your answers. It is clear to me now. – PaulH Sep 11 '18 at 13:10
• 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. – Robert Soupe Sep 12 '18 at 17:24