Question

Find the remainder when ${400}^{1000}$ is divided by 17?

• A. 0
• B. 1
• C. -1
• D. 2

Answer 1

The correct option is B

1

This needs the application of basic remainder, Euler's theorem and frequency.

Step 1 - The remainder when 400 is divided by 17 is 9.

The problem changes to $\frac{9^{1000}}{17}$.

From Euler's theorem, the Euler's number of 17 is 16.

$1000=16k+8$

Problem now changes to $\frac{9^8}{17}$.

Going by frequency method, $\frac{9^4}{17}$ gives remainder -1. So $\frac{9^8}{17}$ will give remainder 1.

Alternate Solution:

We know that $9^2=81\Rightarrow (81{)}^{500}=(-4{)}^{500}={16}^{250}=(-1{)}^{250}=1$