Loading ...
Sorry, an error occurred while loading the content.

Pseudoprime question

Expand Messages
  • Kevin Acres
    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
    • 0 Attachment
      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.
    • Jud McCranie
      ... Yes. In particular, Carmichael numbers are pseudoprime to all bases
      Message 2 of 3 , Jul 1, 2004
      • 0 Attachment
        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.
      • julienbenney
        ... base? ... bases
        Message 3 of 3 , Jul 7, 2004
        • 0 Attachment
          --- 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.