TITLE: How would I solve $53^{1069}$ mod 54?
QUESTION [0 upvotes]: I am doing practice problems for an upcoming exam and am wondering what approach I might take to solve $53^{1069}$ mod 54. 1069 is a prime number, which means I can't factor the exponent. 
Some other similar problems that I solved used Fermat's theorem (if N is prime, then $a^{N-1} \equiv$ 1 mod N), but 54 is not prime so I'm not sure if that is correct.

REPLY [1 votes]: $53 \equiv -1 \bmod 54$ thus we can have $53^{1069} \equiv (-1)^{1069} \equiv -1 \equiv 53 \bmod 54$.
{"set_name": "stack_exchange", "score": 0, "question_id": 3390993}