Question

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

• A. 3
• B. 4
• C. 11
• D. 8

Answer 1

The correct option is A 3

$\frac{2000}{13}$ gives remainder 11, now ${11}^{1000}={121}^{500}$

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

We know that $\frac{2^{12}}{13}$ has a remainder 1. Hence, $\frac{2^{1000}}{13}=\frac{(2^{12}{)}^{83}\times 2^4}{13}=\frac{2^4}{13}=\frac{16}{13}$, hence remainder is 3.

Alternate Approach - Using Euler's Theorem

$\frac{{2000}^{1000}}{13}\left(\text{remainder}\right)=\frac{{11}^{1000}}{13}$ (remainder)

Euler’s number of a prime number is one less than that number. Hence, Euler’s number for 13 = 12

From Euler's Theorem, remainder of $\frac{N^{Eule{r}^{\prime }sNumber}}{X}$ = 1 (if N and X are co-prime)

Hence $\frac{{11}^{996}}{13}$ has remainder =1 (as 996 is a multiple of 12, Euler’s number of 13)

The question can be changed to $1\times \frac{{11}^4}{13}$.

Remainder of $\frac{14641}{13}$ = 3. $\therefore$ Answer is 3.