Note that $80 = \mathrm{lcm}(2,10,16)$. So you can write $a^{80} = (a^2)^{40} = (a^{10})^{8} = (a^{16})^5$. So,
\begin{align*}
a^{80}= (a^2)^{40} &\equiv 1^{40} = 1\pmod{3},\\
a^{80}= (a^{10})^{8} &\equiv 1^8 = 1 \pmod{11},\\
a^{80}= (a^{16})^5 &\equiv 1^5 = 1\pmod{17}.
\end{align*}
By the Chinese Remainder Theorem, the system of congruences
\begin{align*}
x&\equiv 1\pmod{3}\\
x&\equiv 1\pmod{11}\\
x&\equiv 1\pmod{17}
\end{align*}
has a unique solution modulo $3\times 11\times 17 = 561$. But both $x=1$ and $x=a^{80}$ are solutions. Since the solution is unique modulo $561$, then
the two solutions we found must be congruent. That is,
$$a^{80}\equiv 1\pmod{561}.$$
(Added. Or, more simply, as Andres points out, since $3$, $11$, and $17$ each divide $a^{80}-1$, and are pairwise relatively prime, then their product divides $a^{80}-1$).
Once you have that $a^{80}\equiv 1\pmod{561}$, then any power of $a^{80}$ is also congruent to $1$ modulo $561$. In particular,
$$a^{560} = (a^{80})^{7} \equiv 1^7 = 1 \pmod{561}$$
as desired.
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?
Best Answer
It is very likely there are infinitely many such Carmichael numbers. Consider the four polynomials: $$\begin{array}{lcl} P_1(x) & = & 6x+1 \\ P_2(x) & = & 12x+1 \\ P_3(x) & = & 18x+1 \\ P_4(x) & = & 36x^2 + 11x+1 \end{array}$$
All four polynomials have positive leading coefficient, are irreducible over integers and each of them attains at least two different prime values. Furthermore, for any prime $p$, the values of the polynomials at $x=p$ are not divisible by $p$. This implies these four polynomials satisfy the conditions of Generalized Bunyakovsky conjecture and thus there should be infinitely many values of $x$ for which all of them attain prime values simultaneously.
For each such $x$, Korselt's criterion tells us that the product $$M=P_1(x)P_2(x)P_3(x)=1296x^3+396x^2+36x+1=36xP_4(x)+1$$ is a Carmichael number. At the same time, $36x<P_4(x)$ for positive integers $x$ so the number $M$ is also of the form $Kp^1+1$ for prime $p=P_4(x)$ and $K<p$.