Question

Find the remainder when ${300}^{1000}$ is divided by 19?___

Answer 1

This needs the application of basic remainder theorem, Euler's theorem and frequency method.
First find the remainder when 300 is divided by 19 = 15.
The problem now changes to $\frac{{15}^{1000}}{19}$.
From Euler's theorem, the Euler's number of 19 is 18 (for all prime numbers, Euler's number=N-1).

$1000=18\times 55+10$
Problem now changes to $\frac{{15}^{10}}{19}$.
$\frac{15}{19}$ gives remainder -4. So the remainder of $\frac{(-4{)}^{10}}{15}$ or $\frac{(4{)}^{10}}{15}$ needs to be found.
Now $\frac{(4{)}^2}{15}$ gives a remainder of 1.
Going by the frequency method,
$\frac{(4{)}^{10}}{15}$ will give a remainder of $\frac{(1{)}^5}{15}$, i.e 1.