Simplifying large exponents in modular arithmetic like $1007$ in $4^{1007} \pmod{5}$ How would I rigorously prove that $4^{1007} \pmod{5} = 4$ and $4^{1008} \pmod{5} = 1$?
I was simplifying a larger modular arithmetic problem ($2013^{2014} \pmod{5}$) and got it down to $4^{1007} \pmod{5}$ and am wondering if there's a general approach to dealing with large exponents like $1007$.
In general, what approaches are there to simplify large exponents like $1007$ when doing modular arithmetic?
 A: First of all, some common sense can help a lot and even without Fermat's theorem:
$$4=-1\pmod 5\implies\begin{align*} 4^{1007}&=(-1)^{1007}=-1=4\pmod 5\;,\\{}\\
\;\;4^{1008}&=(-1)^{1008}=1\pmod 5\end{align*}$$
A: Another method for this is repeated squaring.
Take $n^d \mod b$ then
find all $a^{2^k} \mod b$ for all $2^k <= d$  where $d$ is $n^d$ 
$$\begin{align}
4^2 &= 16 = 1 \\
4^4 &= (4^2)^2 = 1^2 \\
4^8 &= (4^4)^2 = 1^2 \\
&... \\
4^{512} &= 1 \\
\end{align}$$
for $4^{1007}$ we have:
$$\begin{align}
4^{1007} 
  &= 4^{512} * 4^{256} * 4^{128} * 4^{64} * 4^{32} * 4^8 * 4^4 * 4^2 * 4  \\
  &= 1 * 1 * 1 * 1 * 1 * 1 * 1 * 1 * 4 \mod 5 \\
  &= 4 \mod 5  
\end{align}$$
and for $4^{1008}$ we have:
$$\begin{align}
4^{1008}
  &= 4^{512} * 4^{256} * 4^{128} * 4^{64} * 4^{32} * 4^{16} \\
  &= 1 * 1 * 1 * 1 * 1 * 1 \\
  &= 1 \mod 5 \\
\end{align}$$
Further details:
http://www.tricki.org/article/To_work_out_powers_mod_n_use_repeated_squaring
A: Use Fermat's Theorem which tells that if $p$ is a prime and $gcd(a,p)=1$, then $a^{p-1}\equiv 1(\mod~p)$.
For further elaboration on Fermat's Theorem see http://mathworld.wolfram.com/FermatsLittleTheorem.html or any standard text in Number Theory.
A: To answer the general question, there are two handy ways of simplifying $$a^k \pmod n.$$
Method 1
We have the property of modulo arithmetic:  If $a \equiv b \pmod n$ and $c \equiv d \pmod n$, then $ac \equiv bd \pmod n$.  This has the corollary: 

If $a \equiv b \pmod n$ then $a^k \equiv b^k \pmod n$ for all $k \geq 1$.

In this case, we see $4 \equiv -1 \pmod 5$.  So $$4^{1007} \equiv (-1)^{1007} \pmod 5.$$  But we know $(-1)^{1007}=-1$ since $1007$ is odd.  So $$4^{1007} \equiv -1 \pmod 5.$$  We can then multiply both sides by $-1$ to show $$4^{1008} \equiv 1 \pmod 5.$$
Method 2
Euler's Theorem, which implies that if $\gcd(a,n)=1$, then $a^{\varphi(n)}=1 \pmod n$, where $\varphi$ is the Euler phi-function.  This has the consequence:

If $\gcd(a,n)=1$ then $$a^k \equiv a^{k \text{ mod } \varphi(n)} \pmod n$$ for all $k \geq 1$.

So, in the example, we compute $\varphi(5)=4$ (since $5$ is prime), then we know $$4^{1007} \equiv 4^{1007 \text{ mod } 4} \equiv 4^3 \equiv 4 \pmod 5.$$  We can then multiply by $4$ to show $$4^{1008} \equiv 1 \pmod 5.$$
