Finding remainder when $5^{99}$ is divided by $13$

Question

I have to find the remainder when $5^{99}$ is divided by $13$ without using modular arithmetic. I have to use Binomial Theorem only. Here's my attempt.

---

My Attempt $$\begin{aligned}5^{99}=125^{33}&=(117+8)^{33}\\ &=\sum_{k=0}^{33}{33\choose k} (117)^{33-k}(8)^{k}\end{aligned}$$

So the answer will be same remainder as obtained when $8^{33}$ is divided by $13$ which would be the same when $5^{11}$ is divided by $13$ which we get by writing $8^{33}$ as $(507+5)^{11}$.

---

I am not sure on how to proceed from here. Any hints would be appreciated. Thanks

Answer 1

Hint: $$5^{99} = 5(25)^{49} = 5(26-1)^{49} $$

Answer 2

Hint: $5^2\equiv -1 \bmod 13$

So $5^{98}\equiv (5^2)^{49}\equiv ?? \bmod 13$

Then $5^{99} \equiv ??? \bmod 13$

Answer 3

$5^4=625=13\cdot48+1$, and $5^3=13\cdot9+8$.

So $5^{99}=5^{4\cdot24+3}=\left(13\cdot48+1\right)^{24}\cdot\left(13\cdot9+8\right)$.

It follows from the above equation and from the binomial theorem, that the remainder is 8.