Number theory · Maths EE idea · Solid
When Fermat's little theorem fools us
A research question to start from
How reliable is the Fermat test as a primality test, and how do Carmichael numbers defeat it?
A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.
Why it works as a maths EE
Combines a proof, an algorithm and a counterexample family: a natural line of argument from method to evaluation.
Mathematics you would need
- Modular exponentiation
- Fermat's little theorem and its proof
- Korselt's criterion
- Pseudoprimes
Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.
One possible line of attack
- Prove Fermat's little theorem two ways (combinatorial and group-based).
- Define Fermat pseudoprimes and count them for small bases.
- Prove Korselt's criterion in one direction and use it to find Carmichael numbers.
- Evaluate the test's reliability and compare with a stronger test.
Scope and difficulty
Solid. Solid; the comparison with the Miller–Rabin test can be brief.
Pitfalls
- Turning it into a computer science essay about code.
- Not proving the claims used.
Where to start reading
Search a library catalogue or a university's open lecture notes for: Fermat primality test; Carmichael numbers; Korselt's criterion. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).