AIME I 2026 (Problem 13)

For each nonnegative integer

r

less than 502, define

S_r=\sum_{m\ge0}\binom{10000}{502m+r},

where

\binom{10000}{n}

is defined to be 0 when

n>10,000

. That is,

S_r

is the sum of all binomial coefficients of the form

\binom{10000}{k}

for which

0\le k\le10,000

and

k-r

is a multiple of 502. Find the number of integers in the list

S_0,S_1,S_2,\ldots,S_{501}

that are multiples of the prime number 503.

S_r=\binom{10000}{r}+\binom{10000}{502+r}+\binom{10000}{502\times2+r}+\binom{10000}{502\times3+r}+\cdots+\binom{10000}{502\times19+r}

=\binom{503\times19+443}{503\times0+r}+\binom{503\times19+443}{503\times1+r-1}+\binom{503\times19+443}{503\times2+r-2}+\binom{503\times19+443}{503\times3+r-3}

+\cdots+\binom{503\times19+443}{503\times r+0}+\binom{503\times19+443}{503\times r+502}+\binom{503\times19+443}{503(r+1)+501}

+\binom{503\times19+443}{503(r+2)+500}+\cdots+\binom{503\times19+443}{503\times18+484+r}

for

0\le r\le18

\equiv\binom{19}{0}\binom{443}{r}+\binom{19}{1}\binom{443}{r-1}+\binom{19}{2}\binom{443}{r-2}

+\binom{19}{3}\binom{443}{r-3}+\cdots+\binom{19}{r}\binom{443}{0}+\binom{19}{r}\binom{443}{502}

+\binom{19}{r+1}\binom{443}{501}+\binom{19}{r+2}\binom{443}{500}+\cdots+\binom{19}{18}\binom{443}{484+r}\pmod{503}

\equiv\binom{19}{0}\binom{443}{r}+\binom{19}{1}\binom{443}{r-1}+\binom{19}{2}\binom{443}{r-2}+\cdots+\binom{19}{r}\binom{443}{0}

=\binom{462}{r}\not\equiv0\pmod{503}