What is the remainder when 15^400 is divided by 1309? Can I get the procedure involved in detail please!

Hi..I got the answer but it's a really long method and I don't think its good for cat.I first calculate (15)^4 which gave me 50625.Dividing this by 1309 I got 883 as remainder.This way I kept reducing the number and finally got 1.But it's tedious and If I were you I would leave this question for the end.Would be great if someone suggests a quicker method

Hey...is it 15??

yes the answer is 1, can we separate the divisor like into its coprimes, and combine their remainders? or should we apply chinese remainder theorem?

split the 1309 into factors which are 11, 17, 7
Now find the remainder of 15^400 for each of the factors individually and rest is easy

Hi..is the answer 1??