Prove exponential congruence with Chinese remainder theorem

Question

How would you show that for every $n\in\Bbb{N}$

$$3^{n^4+n^2+2n+4}\equiv 21\pmod{60}.$$

As the Chinese remainder theorem is mentioned, I would start with $60=3\times4\times5$, but then how? Thank you!

Answer 1

The Chinese remainder theorem tells you that $3^{n^4+n^2+2n+4}\equiv21\pmod{60}$ if and only if $$3^{n^4+n^2+2n+4}\equiv21\pmod{q},$$ holds for all prime powers $q$ dividing $60$. You've computed $60=3\times4\times5$, so this congruence must hold for $q=3$, $q=4$ and $q=5$. Now which theorem(s) do you know that tell you when $$a^k=1\pmod{q},$$ where $q$ is a prime (power)?