Fermat's Little Theorem when the exponent is less than the $p - 1$ F.L.T. tells us:
$$a^{p-1} \equiv 1 \mod p$$
In all the cases I have seen, we are able to break down a larger exponent such that it will contain $a^{p-1}$. Like examples 1 - 7 here.
But how would we handle an example where the exponent is smaller than $p-1$?
Ex:
$$9^9 \mod 31 $$
What I am thinking is:
$$9^9 = (3^2)^{9} = 3^{18}$$
$$3^{18} \mod 31$$
try squaring it: 
$$3^{36} = 3^{30}3^6 \mod 31$$
$$= 1* 3^6 \mod 31$$
take the square root:
$$3^3 \mod 31$$$$ 27 \mod 31 \neq 4 \mod 31$$
Which is wrong!!
Is there a way of manipulating $9^9$ in the example above?
Thanks!

$9^9\equiv3^{18}\equiv(3^3)^6\equiv(-4)^6\equiv(-64)^2\equiv(-2)^2\equiv4\pmod{31}$
