Los tres últimos dígitos de $3\times7\times11\times15\times \cdots \times 2003$

Question

Cómo puedo encontrar los tres últimos dígitos de $n$

$$n=3\times7\times11\times15\times \cdots \times 2003?$$

Answer 1

Dejemos que $x=\prod_{n=0}^{500}(4n+3)$ entonces la respuesta es $x \mod 1000$ .

Por el teorema chino del resto basta con calcular el módulo $125$ y $8$ .

Pero $125 $ es un divisor de $x$ , por lo que para el módulo $125$ tenemos la congruencia:

$$x\equiv 0 \mod 125.$$

Para el módulo $8$ hay dos casos : $4n-1 \equiv 3 \mod 8$ para $n$ incluso y $4n-3 \equiv -1 \mod 8$ para $n$ impar. El primer caso se produce $251$ veces, la segunda ocurre $250$ tiempos. Utilizamos $3^2 = 9\equiv 1 \mod 8$ para calcular $x \mod 8$ :

$$x \equiv 3^{251}(-1)^{250} \equiv 3^{251} \equiv 3 \mod 8.$$

Así que sólo tenemos que comprobar los múltiplos de $125$ hasta que se cumpla la congruencia anterior. La respuesta es

$875$

Answer 2

def f(i)=3*(3+4)*.....(3+i*4) mod 1000. Se encuentra f(13)=125, f(14)=375, f(15)=625, f(16)=875. Ahora f(17)=f(16)*(3+(16+1) 4)=f(16) (64+7)=875*7=125 mod 1000. Del mismo modo, f(18)=375, f(19)=625, f(20)=875. Así, a partir de f(13), hay un período de 125, 375, 625, 875 y tenemos f(2003)=875.