Recall that the Chinese Remainder Theorem (CRT) states that, for any given integers r, s and any two positive co-prime integers a, b there exists exactly one integer x that satisfies 0≤x<ab, x≡r(moda) and x≡s(modb). We can apply CRT here with a=125 and b=8, because 1000=125⋅8 and gcd(125,8)=1.
Because 125 is odd and 125<2019 it is clear that n≡0(mod125). To calculate n(mod8), note that 1⋅3⋅5⋅7≡1(mod8). Because n is the product of (2019+1)/2=1010 odd integers and 1010=4⋅252+2, we can split the given product as follows
n=k=0∏251(8k+1)(8k+3)(8k+5)(8k+7)⋅2017⋅2019
Therefore, n≡(1⋅3⋅5⋅7)252⋅1⋅3≡3(mod8). Alternatively, when we use the usual notation for odd factorials, (2k−1)!!=∏j=1k(2j−1), we can prove by induction on k≥1 the following table:
When
k=1 this is obvious. For the inductive step we use that
(2k+1)!!=(2k+1)(2k−1)!!. Then putting
k=1010 we have
k≡2(mod4) and so
n=(2k−1)!!≡3(mod8).
Having established that
n≡0(mod125) and
n≡3(mod8), to find
n(mod1000), we note that
n is an odd multiple of
125. We can either check the five odd multiples of
125 below
1000 to see which one is congruent to
3 (mod
8), or we solve the congruence
125k≡3(mod8). This is done by first observing that
125≡5(mod8) which gives
5k≡3(mod8), and then multiplying both sides by
5 to obtain
k≡25k≡5⋅3≡7(mod8). Hence,
n≡7⋅125≡875(mod1000), i.e. the last three digits of
n are
875.
Alternatively, we may use the uniqueness in the CRT. It would then be sufficient to check that 875≡0(mod125) and 875≡3(mod8).