Fermat's little theorem and solving system of congruences The question: 

The number $561$ factors as $3 \cdot 11 \cdot 17$. First use Fermat's little theorem to prove that $$a^{561} \equiv a \pmod 3 \\ a^{561} \equiv a\pmod {11} \\ a^{561} \equiv a\pmod {17}$$ for every value of $a$. Then explain why these three congruences imply that $a^{561} \equiv a (\mod 561)$ for every value of $a$.

My attempt:
$$
a^2 = 
\left\{ 
\begin{array}{c}
1 (\mod 3) \quad \text{if} \quad 3 \mid a\\
0 (\mod 3) \quad \text{if} \quad 3 \nmid a\\ 
\end{array}
\right.
\\[3ex]
a^{10} = 
\left\{ 
\begin{array}{c}
1 (\mod 11) \quad \text{if} \quad 11 \mid a\\
0 (\mod 11) \quad \text{if} \quad 11 \nmid a\\ 
\end{array}
\right. 
\\[3ex]
a^{16} = 
\left\{ 
\begin{array}{c}
1 (\mod 17) \quad \text{if} \quad 17 \mid a\\
0 (\mod 17) \quad \text{if} \quad 17 \nmid a\\ 
\end{array}
\right. 
$$
I'm really not sure where to go from here. The fact that $561 = 3\cdot 11 \cdot 17$ must fit in somehow, but beyond that I don't know.
 A: Presumably you can see that 
$$a^{k} \equiv 
\left\{ 
\begin{array}{c}
1 \bmod p \quad \text{ if } p \nmid a\\
0 \bmod p \quad \text{ if } p \mid a\\ 
\end{array}
\right. $$
immediately gives $a^{k+1} \equiv a \bmod p$ and indeed $a^{nk+1} \equiv a \bmod p$
The key next step is to examine the factors of $561-1=560$. 
$560 = 2^4\cdot5\cdot7$
And in particular,  note
$\begin{align}
2 &\mid 560 \\
10 &\mid 560 \\
16 &\mid 560\end{align}$
Once you have demonstrated the three asserted equivalences to the individual primes, the result for the composite value follows immediately from "simple" equal values in the Chinese Remainder Theorem: given $b,c,$ coprime:
$\left .\begin{align}x\equiv a \bmod b \\x\equiv a \bmod c \end{align}\right\}\implies x\equiv a \bmod bc$

Of interest: $561$ is the smallest Carmichael number
A: Apply the easy direction $(\Leftarrow)$ below, using $\,p_i\!-1 = 2,10,16\mid 560 = e\!-\!1\,$
Theorem $ $ (Korselt's Carmichael Criterion) $\ $ For  $\rm\:1 < e,n\in \Bbb N\:$ we have
$$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^e\!-a\ \iff\  n\ \ is\ \  squarefree,\ \  and \ \ p\!-\!1\mid e\!-\!1\ \, for\  all \ primes\ \ p\mid n$$
Proof $\ \ (\Leftarrow)\ \ $ Since a squarefree natural divides another iff all its 
prime factors do, we need only show $\rm\: p\mid a^e\!-\!a\:$ for each prime $\rm\:p\mid n,\:$ i.e. that $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1}\equiv 1\ \ ( mod\ p),\:$ which, since $\rm\:p\!-\!1\mid e\!-1,\:$ follows from $\rm\:a \not\equiv 0\:\Rightarrow\: \color{#c00}{a^{p-1} \equiv 1}\ \ ( mod\ p),\:$ by little Fermat, i.e. 
$$\rm e\!-\!1 = k(p\!-\!1)\,\Rightarrow\, a^{\large e-1} \equiv (\color{#c00}{a^{\large p-1}})^{\large k}\equiv \color{#c00}1^{\large k}\equiv 1\qquad\qquad $$
$(\Rightarrow)\ \ $ Given that $\rm\: n\mid a^e\!-\!a\:$ for all $\rm\:a\in\Bbb Z,\:$ we must show 
$$\rm (1)\ \  n\,\ is\ squarefree,\quad  and\quad  (2)\ \  p\mid n\:\Rightarrow\: p\!-\!1\mid e\!-\!1$$ 
$(1)\ \ $ If $\rm\,n\,$ isn't squarefree then
$\rm\,1\neq a^2\!\mid n\mid a^e\!-\!a \Rightarrow\:  a^2\mid a\:\Rightarrow\Leftarrow$ $\rm\: (note\ \ e>1\: \Rightarrow\: a^2\mid a^e)$
$(2)\ \ $ Let $\rm\ a\ $ be a generator of the multiplicative group of $\rm\:\Bbb Z/p.\:$
Thus $\rm\ a\ $ has order $\rm\:p\!-\!1.\:$ Now  $\rm\:p\mid n\mid a\,(a^{e-1}\!-\!1)\:$  but $\rm\:p\nmid a,\:$ thus $\rm\: a^{e-1}\!\equiv 1\,\ ( mod\ p),\:$ therefore $\rm\:e\!-\!1\:$ must be divisible by $\rm\:p\!-\!1,\:$ 
the order of $\rm\,\ a\,\ (mod\ p).\quad$  QED 
