Find the smallest positive integer n such that
1 n , 2 n − 1 , 3 n − 2 , … , 2 0 1 7 n − 2 0 1 6 are all integers.
What are the last four digits of this number?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Nicely explained, Juan, but I think you have made an error near the end of your solution. We want n + 1 to divide 2 , 3 , 4 , … , 2 0 1 6 , 2 0 1 7 , so n + 1 should divide L C M ( 2 , 3 , 4 , … , 2 0 1 7 ) . Note that L C M ( 2 , 3 , 4 , … , 2 0 1 7 ) is not equal to 2 0 1 7 ! ; it is much less than 2 0 1 7 ! .
L C M ( 2 , 3 , … , 2 0 1 7 ) is divisible by 5 4 but not 5 5 so only its last four digits are zeroes.
In general, L C M ( a 1 , a 2 , … , a n ) = a 1 × a 2 × ⋯ × a n is not true. Can you figure out the conditions on a i for which the above equation is true?
Log in to reply
I see, Pranshu, thank you for catching my mistake. I see now that L C M ( a 1 , a 2 , … , a n ) = a 1 × a 2 × ⋯ × a n is true when the arguments are relatively prime, such as L C M ( 5 , 1 7 , 2 0 1 6 ) .
I didn't get how do you convert first m o d equation go second mod equation..
Log in to reply
The operation comes from realizing that a ≡ n ( m o d 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: 8 3 7 ≡ 7 ( m o d 1 0 ) is just as true as 8 3 7 + 1 0 ≡ 8 4 7 ≡ 7 ( m o d 1 0 )
Applying this to the problem, adding 2 to n − 1 ≡ 0 ( m o d 2 ) makes it ( n − 1 ) + 2 ≡ n + 1 ≡ 0 ( m o d 2 ) , adding 3 to n − 2 ≡ 0 ( m o d 3 ) makes it ( n − 2 ) + 3 ≡ n + 1 ≡ 0 ( m o d 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.
I didn't understand. Can you give an example?
Log in to reply
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 ( 1 n , 2 n − 1 , 3 n − 2 , … , 2 0 1 7 n − 2 0 1 6 , ) are what we use to derive the mod congruencies , which I explained to @Vishal Yadav through another comment.
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 1 0 0 = 1 .
- 18720 has 1 trailing zero. The highest power of ten it is divisible by is 1 0 1 = 1 0 .
- 6781900 has 2 trailing zeros. The highest power of ten it is divisible by is 1 0 2 = 1 0 0 .
- 95000 has 3 trailing zeros. The highest power of ten it is divisible by is 1 0 3 = 1 0 0 0 .
- 22810000 has 4 trailing zeros. The highest power of ten it is divisible by is 1 0 4 = 1 0 0 0 0 . □
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, 5 0 0 = 5 3 × 2 2 ends with 2 zeros. Combing some terms, 5 0 0 = 1 0 2 × 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 6 2 5 = 5 4 , and the greatest power of 2 in that range is 1 0 2 4 = 2 1 0 . 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.
sorry I dont get how if n+1 | 5^4 and n+1|2^10 then 10^4 divides n+1... could you please explain, thanks! :)
Log in to reply
We know that 5 4 is the greatest power of 5 that divides n + 1 and that 2 1 0 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 × 2 4 = 1 0 4
The theorem on the wiki says:
If an integer can be expressed as 2 a × 5 b × k , where k is an integer such that 2 ∤ k and 5 ∤ 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 4 0 0 0 = 5 3 × 2 5 × k , so the greatest power of 10 that divides it is 1 0 m i n ( 3 , 5 ) = 1 0 3 . Hence, 4000 has 3 trailing zeros.
Every fraction is of the type x n − ( x − 1 ) for x = 1 , 2 , 3 , . . . , 2 0 1 7 . Rewrite them as:
x n − ( x − 1 ) = x n + 1 − x = x n + 1 − x x = x n + 1 − 1
Thus, x n + 1 must be an integer for every x = 1 , 2 , 3 , . . . , 2 0 1 7 . In particular, 5 4 n + 1 and 2 4 n + 1 must be integer, so 5 4 ∗ 2 4 ∣ n + 1 → 1 0 0 0 0 ∣ n + 1 . It means that n + 1 is a number which ends with 0000. Therefore n ends with 9999.
Great! In fact, we know that the minimum value is equal to L C M ( 1 , 2 , 3 , … , 2 0 1 7 ) − 1 :)
Could you please explain why u were particular about the 5⁴ and 2⁴ values of x.
Log in to reply
The solution is 1 less than a number m which is a multiple of every number from 1 to 2017. Choosing these two numbers shows that m is a multiple of 10,000. Call this 10,000*a. Hence n=m-1 = 10,000a-1 whose final four digits are 9999.
Seeing the solution, I now see why it was put at intermediate level. I somehow managed to fool myself into solving m as the lowest multiple of all primes below 2018.
Log in to reply
But why those two numbers exactly? It seems like you could have picked any number arbitrarily in that range. Say 3^6 and 11^3.
Log in to reply
@Lamaus Glamaus – It doesn't matter that those other numbers are factors. They are but so are 16 and 625. And the lowest common multiple must also be a multiple of these two numbers - and hence a multiple of 10,000. The problem was not to find the number (which is very big) but to find the last 4 digits.
Log in to reply
@Malcolm Rich – Specifically, the reason for choosing those two numbers, is that the problem wants us to find the remainder when n is divided by 10000 (IE the last 4 digits). As such, we look at the remainder when n is divided by 16 and also by 625, and apply the chinese remainder theorem .
If the problem wanted us to find the remainder when n is divided by 3 6 × 1 1 3 , then yes we will choose to look at the remainder when n is divided by 3 6 and also by 1 1 3 .
@chetan kakarlapudi as this is the key idea ... What the number be ..N+1 Will always ends with 4zeros
I am not able to understand what you have done and what concept you have applied . You should make it more understoodable You should make it more convenient for others to understand
Log in to reply
To put it more simply: pretend for a second that it is (x-1)/1, (x-2)/2 and so on. (Therefore, x-1 = n, based on this substitution.) For these all to be integers, x needs to be a multiple of all the numbers from 1 to 2017. That means 625 has to be a factor, as does 16. 625*16=10,000, so the number has to be a multiple of 10,000 and will end in 0000.
Now go back to where we substituted x-1 for n. Whatever the number is, we need to take away 1. It will end in 9,999.
This was my reasoning when I solved it--it is similar to what Filippo did, but his reasoning is much more precise and mathematically rigorous.
Log in to reply
How do you figure that numbers 625 and 16 have to be factors?
Log in to reply
@Parth Joshi – Every number between 1 and 2017 is a factor of n+1.
Log in to reply
@Malcolm Rich – That still doesn't clear my doubt.
Log in to reply
@Parth Joshi – Both 16 and 625 are between 1 and 2017. Since every number between 1 and 2017 is a factor of n+1, then 16 and 625 are factors of n+1
I didn't understand. Can you give an example?
Notice that n = -1 (mod 1,2,3,4.....2017) so n is simply one less than the least common multiple all the natural numbers from 1 to 2017. 5^4 = 625, which is less than 2017, so the least common multiple has four zeroes at the end. Therefore, one less than the least common multiple ends in digits 9999.
Yup, I did the same. All the fractions in the question are just mere distractions.
I didn't understand. Can you give an example?
Let's say the last 4 digits are XXXX. Let's look at the unit digit. For the number : n-9/10 the last digit has to be a zero if we subtract 9. So the unit digit is 9. There is no other way this would get satisfied. For n-99/100 the 10th digit has to be 9 for the division to result into an integer. Same goes for the 100th and 1000th digit. Hence XXXX = 9999
Since by dividing the number with any number upto 2017 it leaves a remainder –1 . Thus The number is (2017!—1)
Fine observation, @Anand Raj , but keep in mind that the question asks for the smallest positive integer n . While 2 0 1 7 ! − 1 does satisfy the conditions, it is not the smallest. I made the same mistake earlier, but, as @Pranshu Gaba explained,
Note that L C M ( 2 , 3 , 4 , … , 2 0 1 7 ) is not equal to 2 0 1 7 ! ; it is much less than 2 0 1 7 ! . L C M ( 2 , 3 , … , 2 0 1 7 ) is divisible by 5 4 but not 5 5 so only its last four digits are zeroes. In general, L C M ( a 1 , a 2 , … , a n ) = a 1 × a 2 × ⋯ × a n is not true. Can you figure out the conditions on a i for which the above equation is true?
Problem Loading...
Note Loading...
Set Loading...
Given that 1 n , 2 n − 1 , 3 n − 2 , … , 2 0 1 7 n − 2 0 1 6
Are all integers, we know that:
n − 1 ≡ 0 ( m o d 2 ) , n − 2 ≡ 0 ( m o d 3 ) , … , n − 2 0 1 6 ≡ 0 ( m o d 2 0 1 7 ) .
And, because we know that
a ≡ a + b ( m o d b ) , n + 1 ≡ 0 ( m o d 2 ) , n + 1 ≡ 0 ( m o d 3 ) , … , n + 1 ≡ 0 ( m o d 2 0 1 7 ) .
Meaning 2 , 3 , … , 2 0 1 7 must divide n + 1
2 , 3 , … , 2 0 1 7 ∣ n + 1 .
Considering that we only need the last 4 digits, the problem becomes much easier if we know that n + 1 ends with at least 4 zeroes. These trailing zeroes can be found by looking for the greatest power of 10 that divides n + 1 .
Knowing that every integer between 2 and 2017 divides n + 1 reveals that n + 1 must be a multiple of 6 2 5 = 5 4 and a multiple of 1 0 2 4 = 2 1 0 . We can then express n + 1 as
n + 1 = 5 4 ⋅ 2 1 0 ⋅ k = 1 0 4 ⋅ 2 6 ⋅ k
Where k represents the other factors n + 1 . Therefore, 1 0 4 is the greatest power of 10 that divides n + 1 , so its last 4 digits are 0000.
Subtracting one from that gives the last 4 digits of n , which are 9 9 9 9