Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Maximal number of bases for which composite number is Fermat pseudoprime

  1. Apr 7, 2012 #1
    According to the Wikipedia article a composite number n is a strong pseudoprime to at most one quarter of all bases below n .

    Do Fermat pseudoprimes have some similar property ? Is it known what is the largest number of bases for which composite n , that is not Carmichael number is Fermat pseudoprime ?
  2. jcsd
  3. Apr 10, 2012 #2
    2701 does pretty well, at about 48% bases.
  4. Apr 12, 2012 #3
    Looks like it stays under 50% pseudoprime bases for non-Carmichaels. Typically for the close approaches to 50% there's another root of 1 (other than -1) which also takes almost half of the results. The multiples of the factors take a different value from the Fermat test of course.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook