How to calculate $3^{45357} \mod 5$? I wrote some code, here is what it gives:
\begin{align*}
3^0 \mod 5 = 1 \\
3^1 \mod 5 = 3 \\
3^2 \mod 5 = 4 \\
3^3 \mod 5 = 2 \\\\
3^4 \mod 5 = 1 \\
3^5 \mod 5 = 3 \\
3^6 \mod 5 = 4 \\
3^7 \mod 5 = 2 \\\\
3^8 \mod 5 = 1 \\ 
3^9 \mod 5 = 3 \\ 
3^{10} \mod 5 = 4 \\
3^{11} \mod 5 = 2 \\\\
3^{12} \mod 5 = 1 \\
3^{13} \mod 5 = 3 \\
...
\end{align*}
As I see, there's a period $1, 3, 4, 2$. And intuitively, it's easy to predict that $3^{45357} \mod 5 = 3$. Unfortunately, I'm almost unfamilar with modular math. Could you give me strict analytic explaination of this thing?

Since you say you are unfamiliar with modular arithmetic, here is an alternative proof. Your exponent $45357$ has form $\rm\:4n+1\:$ and your small table of values all satisfy $\rm\: mod\ 5\!:\ 3^{4n+1}\! \equiv 3,\:$ i.e. $\rm\:5\mid 3^{4n+1}\!-3 = 3(3^{4n}-1).\:$ This is true since $\rm\:5\cdot 16 = 3^4-1\:|\:3^{4n}\!-1\ $ by $\rm\:x-1\:|\:x^n-1$.
