Fermat's little theorem and modular arithmetic Below I have the answer to the question solve: $23^{119} \ \mathrm{mod} \ 5$.
We have $119 = 29\cdot4 + 3$.
$23^{119} \ \mathrm{mod} \ 5 
\\= (23^4)^{29}\cdot 23^3 \ \mathrm{mod} \ 5 
\\
= 1 \cdot 23^3 \ \mathrm{mod} \ 5
\\
= 23^3 \ \mathrm{mod} \ 5 
\\
= 3^3 \ \mathrm{mod} \ 5 
\\
= 27 \ \mathrm{mod} \ 5 
\\
= 2 \ \mathrm{mod} \ 5.$
I can follow the problem up to the point when we say that $23^3\ \mathrm{mod} \ 5 = 3^3 \ \mathrm{mod} \ 5$. I'm able to solve the problem by manually cubing $27$ but I don't understand how to make the logical jump from $23^3 \ \mathrm{mod} \ 5 = 3^3 \ \mathrm{mod} \ 5$.

$23 = 3 + 5(4)$, so \begin{align*}
23 &\cong 3 \pmod{5}  \\
23^2 \cong 23 \cdot 23 &\cong 3 \cdot 3 \cong 3^2 \pmod{5}  \\
    &\vdots \\
23^{k} \cong 23^{k-1} \cdot 23 &\cong 3^{k-1} \cdot 3 \cong 3^{k} \pmod{5}, 
\end{align*}
for any integer $k \geq 1$.  (Actually true for any integer $k$.)
