Maths Olympiad Prep

Library / /416 of 462

Number theory Difficulty 7.1 National Olympiad, round 2 Prove it Ireland

Find the number of zeros in which the decimal expansion of the integer 2007!2007! ends. Also find its last non-zero digit.

Solution

For each positive integer kk, we let F(k)F(k) denote the number of positive integers less than or equal to 20072007 which are divisible by kk. Clearly, F(k)=2007kF(k) = \lfloor \frac{2007}{k} \rfloor, the integer part of the rational number 2007k\frac{2007}{k}.
Because 55>20075^5 > 2007, the exponent of 55 in the decimal expansion of 2007!2007! is equal to
F(5)+F(52)+F(53)+F(54). F(5) + F(5^2) + F(5^3) + F(5^4).
An easy calculation gives F(5)=401F(5) = 401, F(25)=80F(25) = 80, F(125)=16F(125) = 16 and F(625)=3F(625) = 3, hence the exponent of 55 in the decimal expansion of 2007!2007! is equal to 500500.

On the other hand, there are 10031003 even numbers among the positive integers less than 20072007 which implies that the exponent of 22 in the decimal expansion of 2007!2007! is at least 10031003. This proves that 1050010^{500} divides 2007!2007!, but 1050110^{501} does not divide 2007!2007!. The decimal expansion of 2007!2007! ends in 500500 zeros.

The idea for the calculation of the digit directly in front of these 500500 zeros is the following. We calculate modulo 1010 the product of all odd factors in the product 2007!2007!, discarding those which are divisible by 55. The product of all even factors is equal to 1003!×210031003! \times 2^{1003} and we calculate modulo 1010 the product of all those factors in 1003!1003! which are co-prime to 55. From the factors not considered so far, we split off the factor 55 and proceed as before. After repeating this procedure a few times we obtain 2007!=n×21003×55002007! = n \times 2^{1003} \times 5^{500}. The calculation gives the value of nn modulo 1010.
The calculations modulo 1010 simplify if we take into account that for each integer kk we have
(10k+1)(10k+3)(10k+7)(10k+9)1mod10(1) (10k + 1)(10k + 3)(10k + 7)(10k + 9) \equiv -1 \quad \mod 10 \quad (1)
and
i=1i59(10k+i)6mod10.(2) \prod_{\substack{i=1 \\ i \neq 5}}^{9} (10k + i) \equiv -6 \quad \mod 10. \quad (2)
Moreover, (6)m(1)m6mod10(-6)^m \equiv (-1)^m 6 \quad \mod 10.

The product of all odd numbers 1,3,...,19991, 3, ..., 1999, co-prime to 55, consists of 200200 products as in (1), so this contributes (1)2001mod10(-1)^{200} \equiv 1 \mod 10. We also have 2001×2003×20071mod102001 \times 2003 \times 2007 \equiv 1 \mod 10. As seen above, there are F(5)=401F(5) = 401 positive integers below 20072007 which are divisible by 55. Exactly 201201 of them are odd. Hence, the product of all positive odd numbers below 20072007 is equal to
M1×5201×401!!, M_1 \times 5^{201} \times 401!!,
where M11mod10M_1 \equiv 1 \mod 10 and 401!!401!! denotes the product of all positive odd integers less or equal to 401401.
Similarly, 401!!=M2×540×79!!401!! = M_2 \times 5^{40} \times 79!! with M2(1)401mod10M_2 \equiv (-1)^{40} \equiv 1 \mod 10. In the next step we get 79!!=M3×58×15!!79!! = M_3 \times 5^8 \times 15!! with M3(1)81mod10M_3 \equiv (-1)^8 \equiv 1 \mod 10. Finally,
15!!=1×3×5×7×9×11×13×15=M4×52 15!! = 1 \times 3 \times 5 \times 7 \times 9 \times 11 \times 13 \times 15 = M_4 \times 5^2
with M41mod10M_4 \equiv 1 \mod 10. Altogether we obtained so far
2007!!=M×5251 2007!! = M \times 5^{251}
with MM1M2M3M41mod10M \equiv M_1 M_2 M_3 M_4 \equiv 1 \mod 10.

To deal with the product of all even factors in 2007!2007!, which is equal to 1003!×210031003! \times 2^{1003}, we study 1003!1003!. This product contains 100100 products as in (2), which contributes (1)10066mod10(-1)^{1006} \equiv 6 \mod 10. In addition, we have to consider 1001×1002×10036mod101001 \times 1002 \times 1003 \equiv 6 \mod 10. The number of factors in 1003!1003! which are divisible by 55 is equal to 200200 so that
1003!=N1×5200×200! 1003! = N_1 \times 5^{200} \times 200!
with N16(mod10)N_1 \equiv 6 \pmod{10}.
Similarly, 200!=N2×540×40!200! = N_2 \times 5^{40} \times 40! with N2(1)2066(mod10)N_2 \equiv (-1)^{206} \equiv 6 \pmod{10}. Next, we obtain 40!=N3×58×8!40! = N_3 \times 5^8 \times 8! with N3(1)466(mod10)N_3 \equiv (-1)^{46} \equiv 6 \pmod{10}. Finally, 8!=N4×58! = N_4 \times 5 with N4=2×3×4×(4)×(3)×(2)6(mod10)N_4 = 2 \times 3 \times 4 \times (-4) \times (-3) \times (-2) \equiv -6 \pmod{10}. Therefore,
1003!=N×5249 1003! = N \times 5^{249}
with NN1N2N3N46(mod10)N \equiv N_1 N_2 N_3 N_4 \equiv -6 \pmod{10}. We obtain
2007!=M×N×5500×21003=M×N×2503×10500 2007! = M \times N \times 5^{500} \times 2^{1003} = M \times N \times 2^{503} \times 10^{500}
and we know M×N64(mod10)M \times N \equiv -6 \equiv 4 \pmod{10}. It remains to find 25038(mod10)2^{503} \equiv 8 \pmod{10}, which is easily seen from 246(mod10)2^4 \equiv 6 \pmod{10}. We conclude that

M ×N×25034×82(mod10).\times N \times 2^{503} \equiv 4 \times 8 \equiv 2 \pmod{10}.

Therefore, the last non-zero digit of 2007!2007! is equal to 22.

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.