A Carmichael number is a composite number $n$ which satisfies the modular arithmetic congruence relation $$a^{n-1} \equiv 1 \pmod n$$
$\forall a \in \mathbb Z_n$ such that $\gcd(a, n) = 1$
Wiki says
Carmichael numbers are important because they pass the Fermat primality test but are not actually prime. Since Carmichael numbers exist, this primality test cannot be relied upon to prove the primality of a number, although it can still be used to prove a number is composite. This makes tests based on Fermat's Little Theorem risky.
Suppose we are using Fermat's Test
to check the primality of the number n
. Does the above paragraphs signifies that Cardinality of the Fermat's liar set $|L(n)|$ would be more in case of Carmichael numbers as compared to other composite numbers. As more number of random a's will be selected which will pass the Fermat's Test as compared to other composite numbers. Please explain.. Am I assuming something wrong.
Your question is worded very vaguely, but it's true in a fairly broad sense. Let $\lambda(n)$ be the Carmichael $\lambda$-function (that is, the exponent of the group $(\mathbb Z/n\mathbb Z)^\times)$. If $n$ is composite and not Carmichael, then $\lambda(n) \nmid n-1$.
Let's assume $n$ is odd for simplicity. Then $\lambda(n) = \text{lcm}_{p^r \| n} \phi(p^r)$, where the notation $p^r \| n$ means that $r$ is the highest power of $p$ dividing $n$. Since $\lambda(n) \nmid n-1$, it means there is some prime power $p^r$ dividing $n$ such that $\phi(p^r) \nmid n-1$.
Now, let $d = \phi(p^r) / \gcd(\phi(p^r), n-1)$. Since by assumption, the denominator is a proper divisor of $\phi(p^r)$, $d \ge 2$. If $g$ is any primitive root modulo $p^r$, then $x = g^k$ satisfies $x^{n-1} \equiv 1 \pmod{p^r}$ iff $d \mid k$.
In other words, exactly $1$-in-$d$ reduced residues mod $p^r$ satisfy $x^{n-1} \equiv 1 \pmod{p^r}$. Since that is a necessary condition to be a Fermat liar, at most $1/d$ of the reduced residues mod $n$ are Fermat liars: $|L(n)| \le \tfrac12 \phi(n)$. By contrast, Carmichael numbers have a liar set $L(n)$ which is equal to the entire set of reduced residues, so that $|L(n)| = \phi(n)$. In a relative sense, Carmichael numbers always have at least twice as many liars as non-Carmichael numbers.
Typically, the liar set is much smaller, but there certainly do exist "near-Carmichael" numbers which are non-Carmichael but for which $\phi(n) / |L(n)|$ is still pretty small (for instance $n=91$, which achieves the lower bound of $2$). Even for these numbers you have a better than 50% chance that a random $a$ will succeed as a compositeness witness.
But for Carmichael numbers it is essentially hopeless to use a Fermat test to prove compositeness: you'd need to choose an $a$ which is not relatively prime to $n$, and if you could do that you'd already have a factorization of $n$ (it's very unlikely to happen randomly unless your $n$ has small prime factors, in which case why would you need to test $n$ for primality?).