number theory - Computing $22^{201} mod (30)$

I am having trouble, I tried using the fact that the $gcd(30, 22) = 2$ but I have been stuck here for a bit now.

$22^{201} \equiv x \mod (30)$

$22^{201} \equiv 22*22^{200} mod (30)$

How can I proceed?

Answer

We have $22^2=484\equiv 4\pmod{30}$
Then $4^3\equiv 4\pmod{30}$ and this means $22^6\equiv 4\pmod{30}$ and $201=33\times 6+3$ so $22^{201}=(22^6)^{33}+22^3$. This gives

$$22^{201}\equiv 4^{33}\times 22^3\pmod{30}$$ Using the above $4^{33}\equiv 4^{11}\equiv (4^3)^{3}\times 4^2\equiv 4$ and $22^3\equiv4\times22\equiv 28\pmod{30}$ and we can conclude that $$22^{201}\equiv 4\times 28\equiv -8\equiv 22 \pmod{30}$$