# Can the product of two Fermat witnesses where the witnesses are prime be a Fermat liar?

Let $n$ be composite. If $a$ is coprime to $n$ such that $a^{n-1} \equiv 1 \pmod n$ then $a$ is called a Fermat liar. If $a^{n-1} \not\equiv 1 \pmod n$, then $a$ is a Fermat witness to the compositeness of $n$.

Assume the witnesses or liars are themselves prime. If two Fermat liars are multiplied together their product will also be a Fermat liar. If a Fermat witness and a Fermat liar are multiplied together, the product is a Fermat witness.

Is it possible for the product of two Fermat witnesses to be a Fermat liar if the witnesses are themselves prime?

My motivation for the question is to consider what might happen if I use a product of primes as the base in a Fermat primality test rather than a single prime. My hope is that a product of primes would improve the odds of finding the correct answer with one test.

## 2 Answers

The answer is in the affirmative. Consider $n=15$. Then $2$ and $7$ are prime and witnesses in that $$2^{14} = 16384 \equiv 4 (\text{mod } 15) \\ 7^{14} = 678223072849 \equiv 4 (\text{mod } 15).$$

However, $14^{14} \equiv 1 (\text{mod }15)$, hence $2 \cdot 7 =14$ is a liar.

$2^{220} \equiv 16 \bmod 221$, and $19^{220} \equiv 152 \bmod 221$. So $2$ and $19$ are Fermat witnesses $\bmod 221$.

But $38^{220} \equiv 1 \bmod 221$, so $38$ is a Fermat liar $\bmod 221$.