<s>[INST] Show that $a^{25} \pmod{88}$ is congruent with $ a^{5} \pmod {88}.$ 
Show that $a^{25} \pmod{88}$ is congruent with $ a^{5} \pmod {88}.$

I have proved it in the case that $\gcd(88,a)=1$, but in the other case , I don't know it. Any ideas?
 [/INST] Note that $88=11 \cdot 8$, so $\Bbb Z _{88} \simeq \Bbb Z _8 \times \Bbb Z _{11}$. Therefore, you must show that $a^{25} = a^5$ in both $\Bbb Z _8$ and $\Bbb Z _{11}$. We shall use Euler's theorem: in $\Bbb Z _n$, we have $a^{\varphi (n)} = 1$, where $\varphi$ is Euler's function. Note that $\varphi(8)=4$ and $\varphi (11)=10$.
In $\Bbb Z _{11}$, every $a \ne 0$ is coprime to $11$, so $a^{10} = a^{\varphi (11)} = 1$, so $a^{25} = a^{20+5} = (a^{10})^2 a^5 = a^5$.
In $\Bbb Z _8$, if $\gcd (a, 8) = 1$, then $a^4 = a^{\varphi (8)} = 1$, so $a^{25} = a^{24+1} = (a^4)^6 a = a$; on the other hand, $a^5 = a^{4+1} = a^4 a=a$, so $a^{25}=a^5 \mod 8$.
If $\gcd(a, 8) >1$ then $2|a$, say $a=2b$. Then $a^{25} = 2^{25} b^{25} =0$, because $8 | 2^{25}$. Similarly, $a^5 = 2^5 b^5 = 0$, so again $a^{25} = a^5$.
The last case to examine is $a=0$, but this is trivial.
</s>