Finding a Residue using Fermat's Theorem.

Question

I am currently working through an assignment and have almost solved the following problem.

Use Fermat's Theorem to find the residue of $2^{1000} \,\text{mod}\, 59$.

Now I have stated that $2^{58}$ is congruent to $1 \,\text{mod}\, 59$, and broken the problem up into parts, beginning with $2^{986} * 2^{14}$, and then gone further until the first part equals $1$.

The problem is that no matter how I have tried manipulating things, I get stuck with $2^{14}$and I was under the impression the answer should be between $0$ and $58$?

I have been following the answer in this question so far, but in that scenario it works out nicely with $3^3$ already being small.

Am I missing something obvious here, or am I going about this the wrong way?

Thanks.

Answer 1

You can break $2^{14} \equiv 2^{6} \cdot 2^{6} \cdot 2^{2} \equiv (5)(5)(4) \equiv 41 \pmod{59}$