Remainder of $2^{125}/13$ Remainder of $2^{125}/13$
According to Microsoft Excel, the answer is 6

I was expecting a shorter pattern with remainders such as 3,6,12,...
How to go about doing this simply?
I thought of something like
$$2^{125} = (26-24)^{125}$$
$$2^{125} = (28-26)^{125}$$
Those don't seem to help.
 A: This problem can be solved with modular arithmetic.
By Fermat's little theorem $2^{12}\equiv 1 \bmod 13$
Therefore $2^{125}=(2^{12})^{10}\times 2^5\equiv 1\times 32\equiv 6  \bmod 13$
A: In a little different way than the given answer, there is this rule for $n\in\mathbb{N}$, $a\in \mathbb{Z}_n^*$ and $b\in \mathbb{Z}_n$:
  $$ a^b\bmod n \equiv a^{b\bmod \varphi(n)}\mod n, $$
where $\varphi$ indicates Euler's totient function. Here we have that $2$ and $13$ are coprime, thus $2\in  \mathbb{Z}_{13}^*$ (since $13$ is a prime, every element of $\mathbb{Z}_{13} \setminus \{0\}$ is invertible) and this gives
  $$ 2^{125 \bmod 12} \equiv 2^5 \equiv 6 \mod 13. $$
A: The trick is to look for a power of $2$ that is close to a multiple of 13. Starting with $2$, $4$, $8$, etc. you find that $64 = 2^8$ is exactly one less than $65 = 5\times 13$. In mod notation, $$2^6 \equiv -1 \bmod 13.$$
Now exponentiate both sides to get the largest exponent you can below $125$:
$$(2^6)^{20} \equiv (-1)^{20} \bmod 13$$
so that $$2^{120} \equiv 1 \bmod 13.$$ Finally multiply both sides by $2^5$ to get $$2^{125} \equiv 32 \bmod 13$$ and work out by hand that the remainder you get when you divide $32$ by $13$ is $6$.
