Proving that $a^{25} \bmod 65 = a \bmod 65$? 
Prove that for all $a \in \mathbb{Z}$ we have $$ a^{25} \bmod 65 = a
 \bmod 65. $$

We have $65 = 5 \cdot 13$, where $5$ and $13$ are prime. So I wanted to compute the first expression by using the Chinese Remainder theorem. I have to find a $x$ which satisfies the system $$ \begin{cases} x \bmod 5 = a^{25} \bmod 5 \\ x \bmod 13 = a^{25} \bmod 13 \end{cases}. $$ But how can I solve this system when I don't know what $a$ is? I tried using Fermat's little theorem for the prime number $23$, but the above equation has to hold for all $a \in \mathbb{Z}$, not only with $gcd(a,p) = 1$.
So how can we solve this problem?
 A: If $a=0$ then this is trivial, so assume $a\neq 0$.
$\mathbb{Z}_5=\mathbb{Z}/5\mathbb{Z}$ is a field, so $\mathbb{Z}_5^\times$, the group of invertible elements, is a group of $4$ elements.
In particular, we have $a^4\equiv 1\bmod 5$, so $a^{24}=(a^4)^6\equiv 1\bmod 5$, and $a^{25}\equiv a\bmod 5$.
Similarly, $\mathbb{Z}_{13}$ is a field, and its group of invertible elements has $12$ elements, so $a^{12}\equiv 1\bmod 13$, $a^{24}\equiv 1\bmod 13$, and thus $a^{25}\equiv a\bmod 13$.

Remark: You can avoid fields and use Fermat's little theorem directly:
$$a^5\equiv a\bmod 5.\tag{5.1}$$
Taking the $5$-th power, we obtain
$$a^{25}\equiv a^5\bmod 5\tag{5.2}$$
and putting $(5.1)$ and $(5.2)$ together,
$$a^{25}\equiv a\bmod 5.$$
Now for $13$:
$$a^{13}\equiv a\bmod{13}\tag{13.1}$$
Multiply by $a^{12}$:
$$a^{25}\equiv a^{13}\bmod{13}\tag{13.2}$$
put $(13.1)$ and $(13.2)$ together:
$$a^{25}\equiv a\bmod{13}.$$
A: The Chinese Remainder Theorem is rarely of any use when you're looking at variable expressions. But factoring $65$ as $5 \cdot 13$ is useful.
First, notice that there are $65$ possible combinations of $x \mod 5$ and $x \mod 13$; so each number $0$ through $64$ has a different such signature. By Fermat's little theorem, $a^5 \equiv a \mod 5$, so $a^{25} = (a^5)^5 \equiv a^5 \equiv a \mod 5$. Again by Fermat, $a^{13} \equiv a \mod 13$, so $a^{12} \equiv 1 \mod 13$ (unless $a \equiv 0 \mod 13$). Since $a^{25} = a \cdot (a^{12})^2$, either way we have $a^{25} \equiv a \mod 13$. So $a^{25}$ and $a$ have the same signature mod $5$ and $13$, and hence $a^{25} \equiv a \mod 65$.
A: Notice $\, n =  65 =  5\cdot  13 \,$ is a product of distinct primes $\rm \,p\,$ such that $\rm \ \color{#c00}{p\!-\!1\mid 25\!-\!1},\:$  thus 
Theorem $\ $  For natural numbers $\rm\:a,e,n\:$ with $\rm\:e,n>1$ 
$\qquad\rm n\:|\:a^e-a\:$ for all $\rm\:a\:\iff  n\:$ is squarefree, and prime $\rm\:p\:|\:n\,\Rightarrow\, \color{#c00}{p\!-\!1\mid e\!-\!1}$ 
Proof $\ (\Leftarrow)\ $ Hint: since a squarefree natural divides another iff all its 
prime factors do, we need only show $\rm\:p\:|\:a^e\!-\!a\:$ for each prime $\rm\:p\:|\:n,\:$ or, 
that $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1} \equiv 1\pmod p,\:$ which, since $\rm\:p\!-\!1|\:e\!-\!1,\:$ follows 
from $\rm\:a \not\equiv 0\:$ $\Rightarrow$ $\rm\: a^{p-1} \equiv 1 \pmod p,\:$ by little Fermat.
$(\Rightarrow)\ $ Not needed here, see this answer 
