## More on Fermat witnesses and liars

In my previous post I stated, without proof, the following theorem:

Theorem: if $n$ is composite and there exists at least one Fermat witness for $n$, then at least half of the numbers relatively prime to $n$ are Fermat witnesses.

Were you able to prove this? Here’s one way to do it.

Suppose $n$ is composite and $a$ is a Fermat witness for $n$—that is, $a^{n-1} \not\equiv 1 \pmod n$. Let $b$ be some Fermat liar for $n$, that is, $b$ is relatively prime to $n$ but $b^{n-1} \equiv 1 \pmod n$. (How do we know there exists a Fermat liar for $n$, you ask? Well, we don’t, but if there aren’t any then the theorem is obviously true.) Then I claim that $ab$ is also a Fermat witness for $n$: $(ab)^{n-1} = a^{n-1} b^{n-1} \equiv a^{n-1} \cdot 1 \not \equiv 1 \pmod n$

So for every Fermat liar $b$ there is a corresponding Fermat witness $ab$. The only thing we might worry about is that some of these Fermat witnesses might not be distinct. But in fact, since $a$ is relatively prime to $n$, multiplication by $a$ modulo $n$ is invertible, so $ab_1$ and $ab_2$ must be distinct modulo $n$ whenever $b_1$ and $b_2$ 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 $n$, each $a$ we pick has a probability of at least $1/2$ of revealing that $n$ is composite. So if we pick $k$ different values for $a$ and all of them yield $a^{n-1} \equiv 1 \pmod n$, we can conclude that there is only a $1/2^k$ chance that $a$ is composite. That’s pretty good, and it’s nice that the probability is independent of $n$.

However, there’s one big flaw, which relates to my third question from the previous post: can there be composite values of $n$ with no Fermat witnesses? More in my next post! 