Remainder of $2^{125}/13$

Question

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.

Answer 1

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$

Answer 2

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. $$

Answer 3

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$.