AIME 2026 I · 第 13 题

Solution 1

Consider polynomials in $\mathbb F_{503}[x]$, that is, polynomials with integer coefficients taken modulo $503$. When viewed as functions $\mathbb F_{503}^\times \to \mathbb F_{503}$ (note that we have removed $0$ from the domain), it turns out that every such polynomial is equivalent to a unique polynomial of degree at most $501$. For example, $x^{502}$ is equivalent to $1$ by Fermat's little theorem. This equivalent polynomial with smaller coefficients can always be constructed by simply taking all exponents modulo $502$. The uniqueness of the reduced polynomial can be proven by using a finite field Fourier transform: If we expand any polynomial $p(x)$ of degree at most $501$,

$$p(x) = a_0 + a_1x + \cdots + a_{501}x^{501},$$ then

$$a_k \equiv -\sum_{i=1}^{502} i^{-k} p(i) \pmod{503}.$$ This lets us determine the coefficients of $p(x)$ exactly by evaluating it on $i = 1, 2, \dots, 502$, so the polynomial must be unique.

The problem statement tells us the $S_r$ are the coefficients of the reduction of $(1 + x)^{10,000}$:

$$(1 + x)^{10,000} \equiv \sum_{r = 0}^{501} S_r x^r \pmod{x^{502} - 1}.$$ We can use Fermat's little theorem to reduce $(1 + x)^{10,000}$ in a different way. For all $x \in \{1, 2, \dots, 502\}$, we can evaluate that $(1 + x)^{10,000} \equiv (1 + x)^{462} \pmod{503}$. Because reductions are unique, this means that $(1 + x)^{462}$ is the reduction we seek. Equating coefficients,

$$\sum_{r = 0}^{501} S_r x^r \equiv (1 + x)^{462} \pmod{503},$$ we get that $S_r \equiv \binom{462}{r} \pmod{503}$. Because $503$ is prime and $462$ is less than $503$, none of the binomial coefficients $\binom{462}{0}, \binom{462}{1}, \dots, \binom{462}{462}$ are equivalent to zero. So, $S_r$ is zero exactly when $r > 462$, i.e., $r \in \{463, 464, \dots, 501\}$. There are $501 - 463 + 1 = \boxed{039}$ such $r$. ~Gray_Wolf

Solution 2 ~ Jesse Zhang (FUNKCCP)

Let $p = 503$. Since $p$ is a prime number, the field $\mathbb{F}_p$ is a finite field of order $p$. Let $N = 10,000$ and $d = 502$. Observe that $d = p - 1$. The problem asks for the number of indices $r \in \{0, 1, \dots, d-1\}$ such that $S_r \equiv 0 \pmod{p}$.

The sum $S_r$ corresponds to the sum of every $d$-th coefficient of the binomial expansion of $(1+x)^N$. Specifically, consider the polynomial $P(x) = (1+x)^N$ in the polynomial ring $\mathbb{F}_p[x]$. By the binomial theorem,

$$P(x) = \sum_{k=0}^N \binom{N}{k} x^k.$$ To isolate the coefficients where the exponent $k$ satisfies $k \equiv r \pmod{d}$, we analyze the polynomial modulo $x^d - 1$. In the quotient ring $\mathbb{F}_p[x] / \langle x^d - 1 \rangle$, we have the identity $x^d = 1$, which implies $x^k = x^{k \pmod d}$. Consequently, the reduction of $P(x)$ is given by

$$P(x) \pmod{x^d - 1} = \sum_{r=0}^{d-1} \left( \sum_{m \ge 0} \binom{N}{dm+r} \right) x^r = \sum_{r=0}^{d-1} S_r x^r.$$ We proceed to compute the explicit form of $(1+x)^N \pmod{x^d - 1}$. The polynomial $x^d - 1 = x^{p-1} - 1$ splits completely in $\mathbb{F}_p$, and its roots are exactly the non-zero elements of $\mathbb{F}_p$, denoted $\mathbb{F}_p^\times = \{1, 2, \dots, p-1\}$. Let $\alpha \in \mathbb{F}_p^\times$ be any such root. By Fermat's Little Theorem, for any $\alpha \neq 0$, we have $\alpha^{p-1} = 1$.

We evaluate the polynomial $(1+x)^N$ at an arbitrary root $\alpha$ of $x^d - 1$. First, we express $N$ in terms of $d$:

$$10,000 = 19 \times 502 + 462.$$ Thus, $N = 19d + 462$. Then, the value of the polynomial at $x = \alpha$ is:

$$(1+\alpha)^N = (1+\alpha)^{19d + 462} = \left[ (1+\alpha)^d \right]^{19} (1+\alpha)^{462}.$$ We distinguish two cases for $\alpha$:

   $\bullet$ Case 1: $\alpha \neq -1$.
   Then $1+\alpha \in \mathbb{F}_p^\times$. Since the order of the multiplicative group is $d = p-1$, we have $(1+\alpha)^d = 1$. The expression simplifies to:
   

$
(1+\alpha)^N = 1^{19} \cdot (1+\alpha)^{462} = (1+\alpha)^{462}.
$
   $\bullet$ Case 2: $\alpha = -1$.
   Then $1+\alpha = 0$. The left side becomes $0^N = 0$ (since $N \ge 1$). The term $(1+\alpha)^{462} = 0^{462} = 0$. Thus, the equality $(1+\alpha)^N = (1+\alpha)^{462}$ holds strictly.

In both cases, $(1+\alpha)^N = (1+\alpha)^{462}$ for all roots $\alpha$ of $x^d - 1$. Let $Q(x) = (1+x)^{462}$. Since the polynomials $\sum S_r x^r$ and $Q(x)$ agree on all $d$ distinct roots of $x^d - 1$, and the degree of $Q(x)$ is $462$, which is strictly less than $d=502$, Lagrange interpolation implies that these polynomials are identical in $\mathbb{F}_p[x]$.

Therefore, equating the coefficients of $x^r$:

$$S_r \equiv \binom{462}{r} \pmod{503}.$$ We seek the number of integers $r \in \{0, 1, \dots, 501\}$ such that $S_r \equiv 0 \pmod{503}$. The binomial coefficient $\binom{n}{k}$ modulo a prime $p$ is zero if and only if $k > n$ (assuming $n < p$). Here, $n = 462$.

$\bullet$ For $0 \le r \le 462$, $\binom{462}{r} \not\equiv 0 \pmod{503}$.
$\bullet$ For $463 \le r \le 501$, $\binom{462}{r} = 0$, so $S_r \equiv 0 \pmod{503}$.

The values of $r$ satisfying the condition are exactly the integers in the range $[463, 501]$. The count is:

$$501 - 463 + 1 = 39.$$

The number of integers in the list $S_0, S_1, \dots, S_{501}$ that are multiples of $503$ is $39$.