Integers

I see, Pranshu, thank you for catching my mistake. I see now that $LCM(a_1, a_2, \ldots , a_n) = a_1 \times a_2 \times \cdots \times a_n$ is true when the arguments are relatively prime, such as $LCM(5, 17, 2016)$ .

The operation comes from realizing that $a \equiv n \pmod{b}$ remains true even if you add or subtract the base to either side. For example, adding 10 to any integer will not change the units digit: $837 \equiv 7 \pmod{10}$ is just as true as $837 + 10 \equiv 847 \equiv 7 \pmod{10}$

Applying this to the problem, adding 2 to $n - 1 \equiv 0 \pmod{2}$ makes it $(n - 1) + 2 \equiv n + 1 \equiv 0 \pmod{2}$ , adding 3 to $n - 2 \equiv 0 \pmod{3}$ makes it $(n - 2) + 3 \equiv n + 1 \equiv 0 \pmod{3}$ , and so on.

There are many more properties like these on the wiki page on modular arithmetic. I hope this clears that up a little bit, but feel free to ask any more questions.

Sure! The first step is figuring out that $n+1$ divides all of the integers from 2 to 2017. The first set of fractions given in the problem ( $\frac{n}{1},\ \ \frac{n-1}{2},\ \ \frac{n-2}{3},\ \ldots,\ \ \frac{n-2016}{2017},$ ) are what we use to derive the mod congruencies , which I explained to @Vishal Yadav through another comment.

• Basically, if you want the last 2 digits of a number, you would mod by 100. For instance $1296 \mod 100 = 96$ . If you were to add or subtract 100 to the original number, the answer is still the same.
• If you want to find if a number is even or odd, you might mod by 2. $4 \mod 2 = 0,\ 71 \mod 2 = 1,\ 72 \mod 2 = 0$ . But, if we add or subtract 2 to this number, its parity remains the same: 4 + 2 is still even, 71 + 2 is still odd, and 72 + 2 is still even.
• From this we find that $a \equiv a + b \pmod{b}$ . In the problem, this nicely provides us with $n + 1 \equiv 0 \pmod{2},\ \ n + 1 \equiv 0 \pmod{3},\ \ldots,\ \ n + 1 \equiv 0 \pmod{2017}$ , and when a number is equivalent to 0 when modded by some base, it is divisible by that base. Thus, we get that $n+1$ divides all of the integers from 2 to 2017.

After that, we take a bit of a gamble. We need the last 4 digits of $n + 1$ . So, we need to consider the possibility that those digits might all be zeros, which we can prove. For a number to have trailing zeroes , it must be divisible by some power of 10. As the wiki explains:

• 123 has 0 trailing zeros and is not divisible by 10. The highest power of ten it is divisible by is $10^0=1.$
• 18720 has 1 trailing zero. The highest power of ten it is divisible by is $10^1=10.$
• 6781900 has 2 trailing zeros. The highest power of ten it is divisible by is $10^2=100.$
• 95000 has 3 trailing zeros. The highest power of ten it is divisible by is $10^3=1000.$
• 22810000 has 4 trailing zeros. The highest power of ten it is divisible by is $10^4=10000.$ $_\square$

A simple trick to finding these 10s is to simply look for 5s and 2s, since 10s are made up of 5s and 2s. What we don't want is stray 5s or 2s. For example, $500 = 5^3 \times 2^2$ ends with 2 zeros. Combing some terms, $500 = 10^2 \times 5$ . Notice that we a stray 5 there. So, what we really need is the smallest of the two powers of 5 and 2. The smaller one in this case is $2^2$ , so 500 ends with 2 zeros.

Back to the problem, let's look for 5s and 2s that divide n + 1. Here we can do this by inspection, because we already have that n + 1 is divisible by any integer between 2 and 2017. The greatest power of 5 in that range is $625 = 5^{4}$ , and the greatest power of 2 in that range is $1024 = 2^{10}$ . So, as we just saw, n + 1 must end in 4 zeroes. Subtract one from that for the answer, 9999.

I hope this made it easier to understand. If you're curious to learn more, there's a couple of links I left in the solution here that lead to the wiki. I'm more than happy to clear up any more doubts you might have.

We know that $5^4$ is the greatest power of 5 that divides $n + 1$ and that $2^{10}$ is the greatest power of 2 that divides $n + 1$ . So, the greatest power of 10 that we can get by combining those two is $5^4 \times 2^4 = 10^4$

The theorem on the wiki says:

If an integer can be expressed as $2^a \times 5^b \times k$ , where $k$ is an integer such that $2 \nmid k$ and $5 \nmid k,$ then the number of trailing zeros that integer has is $\min(a,b).$

To give another example, if we wanted the number of trailing zeros in 4000, we could get that $4000 = 5^3 \times 2^5 \times k$ , so the greatest power of 10 that divides it is $10^{min(3,5)} = 10^3$ . Hence, 4000 has 3 trailing zeros.