Fermat primality test $\gcd$ condition and carmichael numbers Consider the following quote (I read similar thing in a couple of sources but this one illustrates the issue I'm having):

By Fermat's Theorem if $n$ is prime, then for any $a$ we have $a^{n-1} = 1 \pmod{n}$. This suggests the Fermat test for a prime: pick a random $a \in \{1,...,n-1\}$ and see if $a^{n-1} = 1 \pmod{n}$. If not, then $n$ must be composite.
However we may still get equality even when $n$ is not prime. For example, take $n = 561 = 3\times 11\times 17$. By the Chinese Remainder Theorem ... (Some explanation)
Thus no matter what $a$ we pick, $561$ always passes the Fermat test despite being composite so long as $a$ is coprime to $n$. Such numbers are called Carmichael numbers, and it turns out there are infinitely many of them.

So according to the author, no matter what $a \in \{1,...,n-1\}$ we choose, 561 will pass the test. But this is not true e.g:
$$
\begin{align}
3^{560} &\not\equiv 1 \pmod{561} \\
6^{560} &\not\equiv 1 \pmod{561} \\
9^{560} &\not\equiv 1 \pmod{561} \\
&...
\end{align}
$$
and there are many $a \in \{1,...,n-1\}$ such that $a^{560} \not\equiv 1 \pmod{561}$.
Why would we exclude $a$ such that $\gcd(a, n) = 1$ when the test works well without such condition? If we know that $\gcd(a, n) \not= 1$, we already know that $n$ is not prime, thus the test is pointless.
The best source I read so far, sadly forget it, states that if $n$ is composite, then 50% of $a \in \{1,...,n-1\}$ will not satisfy $a^{n-1} \equiv 1 \pmod{n}$. Unless it's Carmichael numbers, i.e. there are less than 50%. Which seams true in my experiences (and this is properly the reason why the probability of not being prime gets lower by $1/2$ on each iteration).
 A: This occurs because for Carmichael numbers like $N$ we have that, by the Chinese remainder theorem, $\mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/p_1\mathbb{Z} \times \mathbb{Z}/p_2\mathbb{Z} \times \dots \times \mathbb{Z}/p_n\mathbb{Z}$ where the $p_i$ are its prime factors, and because for all these primes we have that $p-1|N-1$ we know that any element of this product ring raised to the $N-1$ is going to be itself again just by the fact that this obviously works factor by factor. So actually the percentage of numbers that give false positives are a rather large percentage of these numbers, in fact all of them coprime to $N$...
A: I begin by trying also to answer your question:

Why would we exclude $a$ such that $\gcd(a, n) = 1$ when the test works well without such condition? If we know that $\gcd(a, n) \not= 1$, we already that $n$ is not prime, thus the test is pointless.

The answer is that we are not excluding those $a$, but the chances of randomly getting a Fermat witness $a$ such that $\gcd(a,n)>1$ may be extremely low. At least it can easily be too low to help us in the task of primality testing.

On with my more verbose rant.
I am not an expert on primality testing, but I think $561$ is too small to truly bring to light the risks of primality testing by crude Little Fermat. After all, $3$ is a small number, and you are likely to hit a multiple of three sooner rather than later. But what if you stumble upon a Carmichael number with only relatively large prime factors (for the purposes of crypto we are talking 100+ digit prime number candidates after all).
For example, by Chernik's result if $6k+1,12k+1$ and $18k+1$ are all primes, then their product $n$ is a Carmichael number. If here all those three primes have about 40 digits, then the probability that any given Fermat witness says "Possible prime" is $1-10^{-40}$ or thereabouts - not good when the number to be tested is actually composite!
But, if you use a slightly more sophisticated witness based primality testing, such as Rabin-Miller, then you never have this problem. Each (R-M) witness yelling "Possible prime!" lowers the odds of your candidate still being a composite by a known minimum factor (IIRC the factor is four - but do check your sources on Rabin-Miller). 
So the point is that due to the existence of Carmichael numbers we need to use something other than basic Little Fermat to get something like 99.99% certainty of the candidate being a prime with a reasonable amount of testing
(when 8 R-M witnesses, each cutting the chance of a false positive by a factor of four, will do it).
If the number to be tested would be a Carmichael number, then I'm not aware of any number $\epsilon>0$ such that each witness would lower the probability of a false positive by $(1-\epsilon)$. Furthermore (see the Wikipedia page I linked to earlier), there are quite a few Carmichael numbers in a given range. True, they form a tiny fraction, but when Rabin-Miller gives us the kind of a guarantee that Fermat cannot with the same computational complexity, why use Little Fermat?
A: I believe you got confused. Also in Fermat's little theorem you must put the condition $\gcd(a,p)=1$, otherwise if $p\mid a$ then 
$$
a^{p-1}\equiv 0 \mod{p}\;.
$$
Of course also in it's generalization, Euler's theorem, only if $\gcd(a,n)=1$ the you can say
$$
a^{\varphi(n)}\equiv 1 \mod n\;.
$$
I suggest you to look also at this link, https://en.wikipedia.org/wiki/Carmichael_function: you have to understand we are interested in "the exponent of the multiplicative group of integers modulo n".
Last but not least: if you want to check if $n$ is prime or not and you find out that $\gcd(a,n)>1$ for a certain $a<n$, you already know that $n$ is not prime, no more tests needed...
