Prove that for any positive integer $a,$ $a^{561} \equiv a \pmod{561}.$
All I got so far is by Fermat's Little Theorem,
$a^{3} \equiv a \pmod{3}$
$a^{11} \equiv a \pmod{11}$
$a^{17} \equiv a \pmod {17}$
Is there a way to use the Chinese Remainder Theorem on this problem?
On
Alternative approach.
Tool: $s | (bc)$ and $s$ relatively prime to $b$ implies that $s | c.$
Let $c \equiv (a^{(561)} - a).$
It is assumed that $3 | c, \;11 | c, \;17 | c.$
$3 | c \;\Rightarrow\; \exists k_1 \,\in \,\mathbb{Z} \;\ni c = 3 \times k_1.$
Using the tool, this means that since $11$ is relatively prime
to $3,$
and since $11 | c = 3 \times k_1,$
then $11 | k_1.$
This means that $\exists k_2 \,\in \,\mathbb{Z} \;\ni k_1 = 11 \times k_2.$
Similarly, since $17 | c = (3 \times 11) \times k_2 = 33 \times k_2,$
and since $17$ is relatively prime to $33,$
$17 | k_2$.
This means that $\exists k_3 \,\in \,\mathbb{Z} \;\ni k_2 = 17 \times k_3.$
Thus,
$c = (3 \times k_1) = (3 \times 11 \times k_2)$
$= (3 \times 11 \times 17 \times k_3) = 561 \times k_3.$
Thus, $561 | c.$
Here is a proof by induction that $a^{17+16n}\equiv a\bmod 17$.
Base case: $a^{17}\equiv a\bmod 17$ (Fermat's little theorem).
Inductive step: assume $a^{17+16(n-1)}\equiv a\bmod17$.
Then $a^{17+16n}\equiv a^{16}a^{17+16(n-1)}\equiv a^{16}a=a^{17}\equiv a\bmod17.\square$
Similarly, $a^{11+10n}\equiv a\bmod11$ and $a^{3+2n}\equiv a\bmod3$.
Therefore, $a^{561}\equiv a\bmod 3, 11, $ and $17$,
so by the Chinese remainder theorem $a^{561}\equiv a\pmod {3\times11\times17=561}$.