## Pseudoprime question

Expand Messages
• Does anyone know if a number can be pseudoprime in more than one base? Specifically more than one prime base? Is there a proof or example either way? Kevin.
Message 1 of 3 , Jul 1, 2004
Does anyone know if a number can be pseudoprime in more than one base?
Specifically more than one prime base?

Is there a proof or example either way?

Kevin.
• ... Yes. In particular, Carmichael numbers are pseudoprime to all bases
Message 2 of 3 , Jul 1, 2004
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.
• ... base? ... bases
Message 3 of 3 , Jul 7, 2004
--- 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.
Your message has been successfully submitted and would be delivered to recipients shortly.