Olympiad problem - last $3$ digits of $3\times7\times11\times15\times19\times23\times...\times115\times119$

Question

Can anyone helps me to solve this problem with full explanation or tricks pls

Find the last $3$ digits of $$3\times7\times11\times15\times19\times23\times...\times115\times119$$

Thanks!:)

Answer 1

Firstly, the last $3$ digits of a number is the remainder when the number is divided by $1000$.

Now, one can observe that the number is divisible by $125$, since it contains $15 = 5 \times 3$, $35 = 5 \times 7$, and $115 = 5 \times 23$.

Secondly, we want to find its remainder when divided by $8$. The product contains $30$ numbers, so the remainder is equivalent to $(3 \times (-1))^{15} = (-3)^{15} = (1+8)^7 \cdot (-3) \equiv -3 \equiv 5 \pmod 8$.

---

It is divisible by $125$ and leaves a remainder of $5$ when divided by $8$.

By the Chinese remainder theorem (aka trial and error), its remainder when divided by $1000$ is $\fbox{125}$.

Answer 2

One thing to notice is that there are at least 3 factors of $5$ in the product, so it is a multiple of $125.$ And it is odd, so the last three digits must be one of: $125, \; 375, \; 625, \; 875.$

Second, this product is $$\prod_{n=1}^{30} (4n-1).$$

If you multiply this out, every term has a lot of $4$'s in it, except the last two. The last term is $(-1)^{30}$. The second last term is

$$-\sum_{n=1}^{30} 4n = -4\frac{30\cdot 29}{2} = -1740$$

which is multiple of $8$ plus $4.$ So the product must be $5$ more than a multiple of $8$. This leaves only $125$ as the answer.

We choose to look at $125$ and $8$ because this is the prime power factorization of $1000$.