abstract algebra - 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?

Answer

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}.$$