Easy way to divide $2^{1000}$ by $59$

Question

What will be the remainder when $2^{1000}$ is divided by $59$? What is the easiest way to calculate this?

Answer 1

By Fermat's Little Theorem, $$2^{58}\equiv1\pmod{59}$$ $$(2^{58})^{17}\equiv1\pmod{59}$$ $$2^{986}\equiv1\pmod{59}$$ $$2^{1000}\equiv2^{14}\pmod{59}$$ $$2^{1000}\equiv16384\pmod{59}$$ $$2^{1000}\equiv41\pmod{59}$$

Thus, the remainder is $41$.