2014 AMC 12B 23. The number 2017 is prime. Let . What is the remainder when S is divided by 2017?
(A) 32 (B) 684 (C) 1024 (D) 1576 (E) 2016
I was quite puzzled when I first saw this question. If the modulus we are working with is 2017, why is the “numerator” of the binomial coefficients 2014, and not 2017? Also, why does the summation go from 0 to 62? How is 62 related to 2014 and/or 2017? There doesn’t seem to be any link. I was also quite sure that the solution to the problem was not calculating 63 remainders by brute force and adding them.
The first line of attack we could try with this problem is to see if we can apply any established combinatorial identities. Unfortunately it doesn’t seem to be the case. Wikipedia claims that there is no closed formula for . The following 2 formulas are the most commonly used ones, could we use them?
The second one doesn’t seem so suitable as the “numerator” of the binomials are not constant. The first has some promise, but an application of it doesn’t seem to lead anywhere:
While the second cases looks a bit cleaner with all the “numerators” being the same, there is no simple formula to add binomials whose “tops” are the same but “bottoms” differ by 2.
The next line of attack we could try is to write out the binomials fully and simplify them as much as possible. Since we are working modulo 2017, it seems like it would be better to consider numbers (such as 2014) which are closer to 2017 as negative numbers instead: e.g. .
is simple enough. Let’s keeping going up the binomials in the sequence:
We are on to something! Notice how there was a cancellation in the fraction for ? Let’s see it for :
Following this pattern, we obtain the following:
If we can’t think of any other bright ideas, we could just add up these 63 numbers and divide by 2017, it’s certainly a lot easier than the original 63 numbers that we had to compute and add. However, noticing that is simply the sum :
Thus , the answer is (C).