Question

Find the last three digits of the number 3×7×11×· · ·×2003. [Hint: Chinese

remainder theorem.]

Answer 1

Let  $\prod_{n=0}^{500} (4n + 3)$, then the answer is x mod 1000.

Using Chinese remainder theorem we can calculate modulo 125 and 8.

Since 125 is a divisor of x, there is the congruence for modulo 125:

$x\equiv0 mod 125.$

And for modulo 8 we have two cases : 

1) $4n-1\equiv3 mod 8$ if n even (occurs 251 times).

2) $4n-3\equiv-1 mod 8$ if n odd (occurs 250 times).

To calculate $x mod 8$ we can use $3^2=9\equiv1 mod 8.$

That is why $x\equiv3^{251}(-1)^{250}\equiv3^{251}\equiv3 mod 8.$

The last thing we need to do is to check the multiples of 125 until they are sufficient to match the above congruence.

Multiples of 125: 125, 250, 375, 500, 625, 750, 875, 1000, 1125, 1250 and so on.

The first value that matches our congruence $(x\equiv3mod8)$ is 875, because the remainder of the division 875 by 8 is equal to 3.

Answer: 875.