Maximal number of bases for which composite number is Fermat pseudoprime

  • Context: Graduate 
  • Thread starter Thread starter pedja
  • Start date Start date
  • Tags Tags
    Bases Composite
Click For Summary
SUMMARY

The discussion centers on the properties of Fermat pseudoprimes, specifically the maximum number of bases for which a composite number n, that is not a Carmichael number, can be classified as a Fermat pseudoprime. It is established that composite number 2701 achieves approximately 48% pseudoprime bases. The conversation highlights that for non-Carmichael numbers, the pseudoprime bases typically remain below 50%. Additionally, it notes that numbers approaching this threshold often have another root of 1, aside from -1, influencing the results of the Fermat test.

PREREQUISITES
  • Understanding of Fermat pseudoprimes
  • Knowledge of Carmichael numbers
  • Familiarity with number theory concepts
  • Basic principles of primality testing
NEXT STEPS
  • Research the properties of Carmichael numbers
  • Explore the implications of Fermat's Little Theorem
  • Study the distribution of pseudoprimes among composite numbers
  • Investigate advanced primality testing algorithms
USEFUL FOR

Mathematicians, number theorists, and computer scientists interested in primality testing and the characteristics of pseudoprimes.

pedja
Messages
14
Reaction score
0
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 ?
 
Physics news on Phys.org
2701 does pretty well, at about 48% bases.
 
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.
 

Similar threads

Undergrad Carmichael Numbers: Understanding Their Significance and Properties
  • · Replies 5 ·
Replies
5
Views
3K
Graduate What techniques can speed up counting pseudoprimes?
  • · Replies 1 ·
Replies
1
Views
3K
Graduate Prime Number Powers of Integers and Fermat's Last Theorem
  • · Replies 1 ·
Replies
1
Views
2K
Graduate How to find composition series of Z_n^* of length k?
  • · Replies 7 ·
Replies
7
Views
3K
Graduate Extended Goldbach: every odd number the sum of 5 primes
  • · Replies 1 ·
Replies
1
Views
4K
Graduate Anti-dual numbers and what are their properties?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Proving inequality about dimension of quotient vector spaces
  • · Replies 25 ·
Replies
25
Views
4K
Is Any Carmichael Number Divisible by a Perfect Square Greater Than 1?
  • · Replies 1 ·
Replies
1
Views
2K
High School Is it invalid to redefine the sgn function in this way in a proof?
  • · Replies 15 ·
Replies
15
Views
5K
Undergrad MathCan Numerical Observations Lead to a Simpler Proof of Fermat's Last Theorem?
  • · Replies 20 ·
Replies
20
Views
4K