Simplifying to least non-negative residue when modulo is not prime

Question

So I am attempting to simplify $3^{252} \bmod 610$ to its least non negative residue. However $610$ is not a prime modulus and I cannot split it into a product of two prime numbers so I'm quite lost on where to begin. A hint in the right direction would suffice.

Answer 1

By Euler's theorem, $3^{240}\equiv 1\bmod 610$, so $3^{252}\equiv 3^{12}\bmod 610.$

$3\equiv1\bmod2$ and $3^4\equiv1\bmod5$, so $3^{12}\equiv1\bmod 10$.

$3^5=243\equiv-1\bmod61$, so $3^{10}\equiv1\bmod61$, so $3^{12}\equiv9\bmod61$.

So $3^{252}\equiv1\bmod10$ and $3^{252}\equiv9\bmod61$.

Can you use the Chinese remainder theorem to find $3^{252}\bmod 610$?