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?

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.$$

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*}$$

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.

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