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!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →