This is probably Quixotic, given that four PowerMods plus some fooling around will give you strong pseudoprime testing, where "the bases 2, 13, 23, and 1662803 have no exceptions up to [image: 10^(12)]" http://mathworld.wolfram.com/StrongPseudoprime.html (That's a trillion, in case GMail trashed it) without even CarmichaelQ. But it seems likely there is a pair of fifty-or-so digit a and b that beat the quad strong pseudoprime test (without requiring fifty digit arithmetic), if we could only find them. --rwg On Sat, May 31, 2014 at 12:51 AM, Bill Gosper <billgosper@gmail.com> wrote:
with CarmichaelQ (fairly simple), and three special cases, Block[{a = 15485857, b = 29462131}, Reap[Do[If[! PrimeQ[k] && ! CarmichaelQ[k] && Divisible[ PowerMod[a + b, k, k] - PowerMod[a, k, k] - PowerMod[b, k, k], k], Sow[k]], {k, 2, 117568}]]]
{Null, {{56033, 73633, 93961, 104653}}}
There may well be superior and smaller a and b. And almost certainly superior larger ones. But I don't have a good way to look for them. --rwg