For each nonnegative integer r less than 502, define
Sr=m≥0∑(502m+r10,000),
where (n10,000) is defined to be 0 when n>10,000. That is, Sr is the sum of all binomial coefficients of the form (k10,000) for which 0≤k≤10,000 and k−r is a multiple of 502. Find the number of integers in the list S0,S1,S2,…,S501 that are multiples of the prime number 503.
Announcement
Random Math Together Program - Free for USA(J)MO Qualifiers
Our together program brings together high-achieving students nationwide for team-based problem solving and to prepare for competitions such as HMMT, PUMaC, and more.
Eligibility: USA(J)MO qualifiers • Spots limited
Let P(x)=(1+x)10000. Note that
P(x)=m≥0∑(m10000)xm
Therefore,
P(x)≡r=0∑501Srxr(modx502−1)
By Fermat's Little Theorem, a502−1≡0(mod503), so Lagrange's Theorem says that
x502−1≡a=1∏502(x−a)
Therefore, for some polynomials Q(x),R(x),
P(x)=(1+x)10000=Q(x)(x502−1)+r=0∑501Srxr=Q(x)(503R(x)+a=1∏502(x−a))+r=0∑501Srxr
Taking this modulo 503, we get (as 502∤10000)
(1+x)10000≡(1+x)10000(mod502)≡(1+x)462(mod503)
Thus, if we substitute x=1,2,…,502, we get that
S(x)=r=0∑501Srxr−(1+x)462≡0(mod503)
This means by Lagrange's Theorem, since degS=501 has 502 roots, S is identically 0. Thus, S(x)≡(1+x)462(mod503).
As 503 is prime, this means that the only coefficients that are zero are (n462) for n>462. There are 501−462=039 such numbers.
The problems on this page are the property of the MAA's American Mathematics Competitions