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).
Best Answer
I begin by trying also to answer your question:
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?