In my previous post I stated, without proof, the following theorem:
Theorem: if is composite and there exists at least one Fermat witness for , then at least half of the numbers relatively prime to are Fermat witnesses.
Were you able to prove this? Here’s one way to do it.
Suppose is composite and is a Fermat witness for —that is, . Let be some Fermat liar for , that is, is relatively prime to but . (How do we know there exists a Fermat liar for , you ask? Well, we don’t, but if there aren’t any then the theorem is obviously true.) Then I claim that is also a Fermat witness for :
So for every Fermat liar there is a corresponding Fermat witness . The only thing we might worry about is that some of these Fermat witnesses might not be distinct. But in fact, since is relatively prime to , multiplication by modulo is invertible, so and must be distinct modulo whenever and are. This proves that there are at least as many Fermat witnesses as there are liars; hence at least half are witnesses.
This means that, as long as there is at least one Fermat witness for , each we pick has a probability of at least of revealing that is composite. So if we pick different values for and all of them yield , we can conclude that there is only a chance that is composite. That’s pretty good, and it’s nice that the probability is independent of .
However, there’s one big flaw, which relates to my third question from the previous post: can there be composite values of with no Fermat witnesses? More in my next post!