# Can someone teach me how to solve the following modular calculation?

The question is: solve $43^{159}$ mod $660$. I tried this one using Fermat Theorem, but it doesn't work since $660$ is not a prime. I also tried Euler's theorem, then I get a fact that $43^{\phi(660)}=43^{160} ≡ 1$ mod $660$, but I stuck at here! Can someone help me solve this question? Thanks!

Hint: use that $$43^4\equiv 1 \mod 660$$ and $$159=39\cdot 4+3$$
Since you know that $43^{160}\equiv 1$ and $43$ has an inverse (because it is coprime to $660$), you can multiply both sides by this inverse and conclude that $43^{159}\equiv 43^{-1}$.
\begin{align} 43^{159} % &\equiv 43^{1 + 2 + 4 + 8 + 16 + 128} \\ % &\equiv 43^1 \times 43^2 \times 43^4 \times 43^8 \times 43^{16} \times 43^{128} \\ % &\equiv 43 \times 529 \times 1 \times 1 \times 1 \times 1 \\ % &\equiv 307 & \pmod {660} % \end{align}
To compute $43^{2^{k+1}}$, first compute $43^{2^k}$ then square it and take the remainder mod 660.