Cool Modular Arithmetics.

Question

Let $a$ be the remainder when $1124^{2017}$ is divided by $2017$.

Find the value of $a^{2048}$ $(\text{mod } 45)$

Answer 1

$2017$ is prime so by Fermat's Little Theorem you can know exactly what $a \equiv 1124^{2017}\mod 2017$ is with no calculation.

Then find $\gcd(a, 45)$ and it's easy to see it is $1$ so $a$ and $45$ are relatively prime ($45$ has only $5$ and $3$ as prime factors; $a$ will not have either of those). $\phi(45)= \phi(5)\phi(3^2) = 4*(3-1)*3 = 24$

Then you have $a^{2048}=a^{85*24+8}$ and you can use Euler's theorem to solve $a^{85*24+8}\mod 45$.

[Final Hint: $1124 = 24*45 + 44$]