Understanding Carmichael Number 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.
 A: 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?).
A: I made this things visible to me with a spreadsheet-like "fermat-test" viewer - a small program written in delphi. One can scroll horizontally through the increasing numbers $n$ to be tested, and vertically through the increasing bases $b$ to be used. Together this gave a very nice intuition for me.
Here is the first picture; one can select to show only the odd numbers $n$:

Looking vertically on the columns, one can nicely see, how at the primes the fermat-test using any base $b \lt n$ results in the residual 1 . At the number $n=15$ which is not prime we see various residuals - but for the base $b=4$ it is a pseudo-prime, as well as to base $b=11$. The number $n=27$ seems to be not pseudoprime for any base (except $b=26$ but bases $b=n-1$ play obviously a special role anyway).
But we see also, that we need only the first fermat-test, that to base $b=2$ to have a definite distinction in that small numbers $n$.                 

Next picture shows the neighbourhood of the first base-2 pseudoprime $n=341$:       
 
We see, that already the base $b=3$ would detect to compositeness, and the ratio of compositeness-detecting bases to pseudoprime-bases is about 4 to 1.           

In the next picture only pseudoprimes to base 2 and carmichael-numbers are shown; the first carmichael-number being $n=561$. Guess the next one...              
 
 
If you like you can play with that program, I can put it on my webspace if someone likes it.
