Finding $4064569^{4513230} \pmod n$

Question

Can anyone help me with this? Given the prime numbers $p=1039$ and $q=4283$, $n=qp$

Find: $4064569^{4513230} \pmod n$

Background: We have learned about Fermat's Little Theorem and Chinese Reminder Theorem.

Answer 1

Hint : Reduce the base modulo $p$ and modulo $q$ and the exponent modulo $p-1$ and $q-1$ (You apparantly did not have Euler's theorem). This is enough to find the residues easily in this case.

The solution of $x\equiv a\mod p \ ,\ x\equiv b\mod q$ is unique modulo $pq$. The solution is the value $v$ with $0\le v<n$