Fermat's Prime test proof: Why does $\mathbb{Z}_n \setminus \mathbb{Z}_n^*$ consists of Fermat witnesses?

Question

In a lecture I attended, we had a proof that if $n$ is a composite number, but not a Carmichael number, then it holds that the count of Fermat witnesses to the compositeness of $n$ in the set $\{1, \dots, n-1\}$ is at least $\frac{n}{2}$. As part of the proof (this was left as an exercise to the reader) it was was used that if we define $\mathbb{Z}_n^* = \{a \in \{1, \dots, n-1\} | gcd(a,n) =1 \}$ and then use that $\mathbb{Z_n} \setminus \mathbb{Z}_n^*$ consists of Fermat witnesses. Why is this the case (and does it only hold if $n$ is not a carmichael number)?

Answer 1

Say $d=\gcd(a,n)$. Then $d\mid n$, so $n \mid a^{n-1}-1$ means $d\mid a^{n-1}-1$,

but $d=\gcd(a,n)$ also means $d|a$, so $d|a^{n-1}$; all this means $d|1$, i.e., $d=1$.

Thus, if $\gcd(a,n)>1$ then $n\nmid a^{n-1}-1$.

I.e., if $a\not\in\mathbb Z_n^*$, then $a$ is a Fermat witness to the compositeness of $n$.

I think that's what you wanted to be shown.

This all holds whether or not $n$ is a Carmichael number.

If $n$ is a Carmichael number, then no element of $\mathbb Z_n^*$ is a witness to the compositeness of $n$.

Answer 2

This is true regardless of whether $n$ is a Carmichael number.

$\mathbb{Z}_n^*$ is always well-defined. It consists of all non-witnesses. It is always a subgroup of the numbers relatively prime to $n$. Therefore the size of that set divides the set of numbers that are relatively prime to $n$.

So far so good.

Where Carmichael numbers enter in is that $n$ is a Carmichael number, if and only if $\mathbb{Z}_n^*$ contains all numbers that are relatively prime to $n$.