I need to calculate $7^{2012} \mod {13}$ by hand using exponentiation by squaring, but I cant seem to figure it out.
I started with this but I don't know for sure if its correct or where it's going.
\begin{align} (7^2)^{1006} &\equiv 49^{1006} \pmod {13} \\ (10^2)^{503} &\equiv 100^{503} \pmod {13} \end{align}
Looks good so far. Continuing, we find that: \begin{align*} 100^{503} \pmod {13} &\equiv 9^{503} \pmod {13} \\ &\equiv 81^{251} \cdot 9 \pmod {13} \\ &\equiv 3^{251} \cdot 9 \pmod {13} \\ &\equiv 9^{125} \cdot 3 \cdot 9 \pmod {13} \\ &\equiv 81^{62} \cdot 9 \cdot 1 \pmod {13} & \text{since $3 \cdot 9 = 27 = 2\cdot 13 + 1$}\\ &\equiv 3^{62} \cdot 9 \pmod {13} \\ &\equiv 9^{31} \cdot 9 \equiv 9^{32} \pmod {13} \\ &\equiv 81^{16} \pmod {13} \\ &\equiv 3^{16} \equiv 9^{8} \equiv 3^{4} \pmod {13} \\ &\equiv 9^2 \equiv 81 \equiv 3\pmod {13} \\ \end{align*}