Question

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

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

Answer 1

The correct option is A 3

Option (a)

$\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}\ast 2^4}{13}=\frac{2^4}{13}=\frac{16}{13}$, hence remainder is 3.

Approach 2-Using Fermat theorem & Euler’s number

$\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 of 13= 12

From fermat theorem, $\frac{\text{N(Euler's number of Xn)}}{\text{X}}$(REMAINDER) =1
Hence $\frac{{11}^{\left(996\right)}}{13}$ Remainder=1 (as 996 is a multiple of the Euler’s number of 13=12)

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

From frequency method, $\frac{11}{13}$ (rem) = 11

$\frac{{11}^2}{13}$ (rem) = 4, $\frac{{11}^3}{13}$ (rem) =5, $\frac{{11}^4}{13}$ (rem) =3 .answer is 3