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