Compute the least positive residue of $3^{83} \pmod {3600}$

Question

Compute the least positive residue of $3^{83} \pmod {3600}$.

The group $\Bbb Z_{3600}$ is not cyclic. $3$ is not coprime to $3600$. So I did't know how to compute the congruence without calculator.

Answer 1

Hint:

Use the Chinese remainder theorem: $$\mathbf Z/3600\mathbf Z\simeq\mathbf Z/16\mathbf Z\times\mathbf Z/9\mathbf Z\times \mathbf Z/25\mathbf Z$$ and compute $3^{83}\mod 16, 9,25$

Note $3^2$, hence $3^{83}\equiv 0\mod 9$.

On the other hand(s), $3$ has order $4$ modulo $16$ and $25$, hence $\;3^{83}\equiv 3^3 \equiv\begin{cases}11&\bmod16,\\2&\bmod 25.\end{cases}$

There remains to solve the system of linear congruences $$\begin{cases}x\equiv11\mod16,\\x\equiv2\mod25,\\x\equiv 0\mod 9,\end{cases}$$