--- In

primenumbers@yahoogroups.com, Jud McCranie <j.mccranie@a...>

wrote:

> At 08:28 PM 7/1/2004, Kevin Acres wrote:

> >Does anyone know if a number can be pseudoprime in more than one

base?

> >Specifically more than one prime base?

>

> Yes. In particular, Carmichael numbers are pseudoprime to all

bases < n

> that are relatively prime to n.

>

> If a number could be pseudoprime to at most one base, that means

that a

> second Fermat test would be conclusive, but, alas, it isn't that

simple.

In fact, for the Fermat test, a number can be a pseudoprime to only

finitely many different numbers of bases in theory. Apparently, a

composite number that is a pseudoprime to any base must be a

pseudoprime to (1/2^n) bases relatively prime to it. For instance,

the number 4033 (= 37 times 109) could be a Fermat pseudoprime to

276, 138, or 69 of the 553 prime bases that are relatively prime to

it.