Proving that $a^{25} \bmod 65 = a \bmod 65$?

Question

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 1

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

Answer 2

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

Answer 3

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