Maths Olympiad Prep

Library / /273 of 462

Number theory Difficulty 6.0 National Olympiad Prove it Ireland

Determine the last (rightmost) three decimal digits of nn where:
n=1×3×5×7××2019. n = 1 \times 3 \times 5 \times 7 \times \dots \times 2019.

Solution

Recall that the Chinese Remainder Theorem (CRT) states that, for any given integers rr, ss and any two positive co-prime integers aa, bb there exists exactly one integer xx that satisfies 0x<ab0 \le x < ab, xr(moda)x \equiv r \pmod a and xs(modb)x \equiv s \pmod b. We can apply CRT here with a=125a = 125 and b=8b = 8, because 1000=12581000 = 125 \cdot 8 and gcd(125,8)=1\text{gcd}(125, 8) = 1.
Because 125125 is odd and 125<2019125 < 2019 it is clear that n0(mod125)n \equiv 0 \pmod{125}. To calculate n(mod8)n \pmod 8, note that 13571(mod8)1 \cdot 3 \cdot 5 \cdot 7 \equiv 1 \pmod 8. Because nn is the product of (2019+1)/2=1010(2019+1)/2 = 1010 odd integers and 1010=4252+21010 = 4 \cdot 252 + 2, we can split the given product as follows
n=k=0251(8k+1)(8k+3)(8k+5)(8k+7)20172019 n = \prod_{k=0}^{251} (8k + 1)(8k + 3)(8k + 5)(8k + 7) \cdot 2017 \cdot 2019
Therefore, n(1357)252133(mod8)n \equiv (1 \cdot 3 \cdot 5 \cdot 7)^{252} \cdot 1 \cdot 3 \equiv 3 \pmod 8. Alternatively, when we use the usual notation for odd factorials, (2k1)!!=j=1k(2j1)(2k-1)!! = \prod_{j=1}^k (2j-1), we can prove by induction on k1k \ge 1 the following table:

kk (mod 4)0123
(2k1)!!(2k - 1)!! (mod 8)1137

When k=1k=1 this is obvious. For the inductive step we use that (2k+1)!!=(2k+1)(2k1)!!(2k+1)!! = (2k+1)(2k-1)!!. Then putting k=1010k=1010 we have k2(mod4)k \equiv 2 \pmod 4 and so n=(2k1)!!3(mod8)n = (2k-1)!! \equiv 3 \pmod 8.
Having established that n0(mod125)n \equiv 0 \pmod{125} and n3(mod8)n \equiv 3 \pmod 8, to find n(mod1000)n \pmod{1000}, we note that nn is an odd multiple of 125125. We can either check the five odd multiples of 125125 below 10001000 to see which one is congruent to 33 (mod 88), or we solve the congruence 125k3(mod8)125k \equiv 3 \pmod 8. This is done by first observing that 1255(mod8)125 \equiv 5 \pmod 8 which gives 5k3(mod8)5k \equiv 3 \pmod 8, and then multiplying both sides by 55 to obtain k25k537(mod8)k \equiv 25k \equiv 5 \cdot 3 \equiv 7 \pmod 8. Hence, n7125875(mod1000)n \equiv 7 \cdot 125 \equiv 875 \pmod{1000}, i.e. the last three digits of nn are 875875.

Alternatively, we may use the uniqueness in the CRT. It would then be sufficient to check that 8750(mod125)875 \equiv 0 \pmod{125} and 8753(mod8)875 \equiv 3 \pmod 8.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.