Question

What is the remainder of ${2000}^{1000}$ divided by $13$?

Answer 1

Determine the remainder of ${2000}^{1000}$ by $13$.

When $\frac{2000}{13}$ gives remainder $11$.

Now, ${11}^{1000}={121}^{500}$.

Also, $\frac{121}{13}$ gives remainder $4$.

Thus, we have to find the remainder of $\frac{4^{500}}{13}=\frac{2^{1000}}{13}$.

We know that $\frac{2^{12}}{13}$ gives remainder $1$.

So, apply the above result to find the remainder of the given number:

$$\begin{gathered} \frac{2^{1000}}{13}=\frac{{\left(2^{12}\right)}^{83}\times 2^4}{13} \\ \Rightarrow \frac{2^{1000}}{13}=\frac{2^4}{13} \\ \Rightarrow \frac{2^{1000}}{13}=\frac{16}{13} \end{gathered}$$

And, $\frac{16}{13}$ gives remainder $3$.

Hence, the required remainder is $3$.