What is the remainder when $13^{1000}$ divided by $19$

$\begin{aligned} 13^{1000} & \equiv 13^{1000 \color{#3D99F6}\bmod \phi(19)} \text{ (mod 19)} & \small \color{#3D99F6} \text{Since }\gcd(13,19) = 1\text{, Euler's theorem applies.} \\ & \equiv 13^{1000 \color{#3D99F6}\bmod 18} \text{ (mod 19)} & \small \color{#3D99F6} \text{Euler's tottient function }\phi(19) = 18 \\ & \equiv 13^{10} \text{ (mod 19)} \\ & \equiv (19-6)^{10} \text{ (mod 19)} \\ & \equiv 6^{10} \text{ (mod 19)} \\ & \equiv 2^{10}\cdot 3^{10} \text{ (mod 19)} \\ & \equiv 2^5\cdot 2^5\cdot 9^5 \text{ (mod 19)} \\ & \equiv 32\cdot18^5 \text{ (mod 19)} \\ & \equiv 13\cdot (19-1)^5 \text{ (mod 19)} \\ & \equiv -13 \text{ (mod 19)} \\ & \equiv \boxed 6 \text{ (mod 19)} \end{aligned}$