Show that the following statement is false:
A composite number $n$ is a Carmichael number ⇔ for every prime $p$ which satisfies $p \mid n$ we have $(p− 1) \mid (n− 1)$.
Hint: Consider $n = pk$.
To prove the statement is false we only need one counter-example.
Consider $n = 9$. The prime factorisation is $9 = 3 \times 3$.
Let's check that the prime 3 satisfies $(p-1) \mid (n-1)$. Here this is, $2 \mid 8$, and so the condition is satisfied.
We now need to show that $9$ is not a Carmichael number. We'll go through the process even though we know 561 is the smallest Carmichael number.
Since we know 9 is composite, to show 9 is a not Carmichael number we need to show that $a^{9-1} \equiv 1 \pmod 9$ is not true for all integers $a$ where $\gcd(a,n)=1$.
If we choose $a=2$, then $\gcd(2,9)=1$ and
$$2^8 \equiv 256 \equiv 4 \not \equiv 1 \pmod 9$$
This means $9$ is not a Carmichael number.
By finding a counter-example of $n=9$ we have shown the statement is false.