Finding remainder of the big integer?

Question

The value of the expression $\mathrm{13^{99}(mod 17)}$, in the range $0$ to $16$, is_______?

---

My attempt :

Somewhere it explain as:

Note:

for remainder cycle $\mathrm{13^1mod17=13, 13^2mod17=16, 13^3mod17=4, 13^4mod17=1}$

So, the remainder cycle is $13,16,4,1$.

Therefore, $\mathrm{13^{99}mod17=13^3mod17=4}$ Answer.

Can you explain in formal way or alternative way, please?

Answer 1

$13^2\equiv-1\pmod{17}$

$13^{99}=(13^2)^{49}\cdot13\equiv(-1)^{49}\cdot13\equiv-1\cdot13\equiv-13+17\pmod{17}$

Answer 2

If you do arithmetic modulo $\;17\;$ you get

$$13=-4\;\;\text{and}\;\;(-4)^2=-1\implies$$

$$13^{99}=\left((-4)^2\right)^{49}\cdot(-4)=(-1)(-4)=4$$

Answer 3

This follows from Euler's theorem. Since $13$ is prime, you have $$13^n \equiv 13^{n \bmod \varphi(17)}\equiv 13^{n \bmod {16}} \pmod {17}$$ For $n=99$ you have $99 \bmod {16} = 3$.

Answer 4

Since 17 is prime you can use the Fermat's little theorem: $$13^{16} \equiv 1 \pmod {17}$$ $$(13^{16})^6 \equiv 13^{96} \equiv 1 \pmod {17}$$ $$13^3 \equiv 4 \pmod {17}$$ Thus $$13^{96}*13^3 \equiv 1*4 \pmod {17}$$ $$13^{99} \equiv 4 \pmod {17}$$