By Fermat's theorem:
Note that .
So:
...
COmpute 3^302 mod 5
Would this be right??
a^4=1mod5
3=8mod5
8^4=1mod5
8^4*76=1^76mod5
8^2 * 8^302=1mod5
8^2 * 8^302=-64mod5
8^302=-1mod5
8^302=4mod5
or
3^4 = 1 (mod 5) by Fermat theorems.
So (raise to the 75) both sides,
3^300 = 1 (mod 5)
Multiply 3^2 both sides,
3^302 = 3^2 = 9 = 4 (mod 5)
Well it really is the same work but you just did the unnecessary work of showing that 3 is congruent to 8 mod 5.
And this method WAS used for your problem. Go through it again. The principle is the same. From Fermat's theorem, you have your number to the power of p - 1 is congruent to 1. Raise it as close to the desired power as possible and manipulate it to get what you need.