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.

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

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