Finding the remainder of a linear congruence

Question

Okay so say I have $314^{420} \equiv r \pmod{1001}$ and I have to find what the remainder is, $r$ in this case. I know you could compute it by $gcd(314^{420}, 1001)$ and using EEA. But the numbers are too large for this case.

I also know that 1001 is a product of 3 prime numbers which was a hint that was pointed out to me. So $1001 = 7 * 11 * 13$. But I'm not sure how that can help me out. Any ideas?

Answer 1

HINT:

As you have pointed out $1001=7\cdot11\cdot13$

Using Fermat's Little Theorem $\displaystyle314^6\equiv1\pmod7$ as $(314,7)=(6,7)=1$

$\displaystyle\implies314^{420}=(314^6)^{70}\equiv1$

Similarly, for the rest two cases

Now, lcm$(7,11,13)=?$

Formally we can use Carmichael Function, $\displaystyle\lambda(420)=60$