IMO Shortlist

Let $A = a_{1} \cdots a_{n}$. Throughout the solution, all intervals will be nonempty and have integer end-points. For any interval $X$, the length of $X$ will be denoted by $|X|$.

Define the following two families of intervals:
$$\begin{aligned} \mathcal{S} & = \{[x, y]: x < y \text{ are consecutive marked points}\} \\ \mathcal{T} & = \{[x, y]: x < y \text{ are integers, } 0 \leqslant x \leqslant A-1, \text{ and no point is marked in } (x, y)\} \end{aligned}$$
We are interested in computing $\sum_{X \in \mathcal{S}} |X|^{2}$ modulo $a_{1}$.

Note that the number $A$ is marked, so in the definition of $\mathcal{T}$ the condition $y \leqslant A$ is enforced without explicitly prescribing it.

Assign weights to the intervals in $\mathcal{T}$, depending only on their lengths. The weight of an arbitrary interval $Y \in \mathcal{T}$ will be $w(|Y|)$, where
$$w(k) = \begin{cases} 1 & \text{ if } k = 1, \\ 2 & \text{ if } k \geqslant 2. \end{cases}$$

Consider an arbitrary interval $X \in \mathcal{S}$ and its sub-intervals $Y \in \mathcal{T}$. Clearly, $X$ has one sub-interval of length $|X|$, two sub-intervals of length $|X|-1$ and so on; in general $X$ has $|X|-d+1$ sub-intervals of length $d$ for every $d = 1, 2, \ldots, |X|$. The sum of the weights of the sub-intervals of $X$ is
$$\sum_{Y \in \mathcal{T}, Y \subseteq X} w(|Y|) = \sum_{d=1}^{|X|} (|X|-d+1) \cdot w(d) = |X| \cdot 1 + ((|X|-1)+(|X|-2)+\cdots+1) \cdot 2 = |X|^{2}.$$
Since the intervals in $\mathcal{S}$ are non-overlapping, every interval $Y \in \mathcal{T}$ is a sub-interval of a single interval $X \in \mathcal{S}$. Therefore,
$$\begin{equation*} \sum_{X \in \mathcal{S}} |X|^{2} = \sum_{X \in \mathcal{S}} \left( \sum_{Y \in \mathcal{T}, Y \subseteq X} w(|Y|) \right) = \sum_{Y \in \mathcal{T}} w(|Y|). \tag{1} \end{equation*}$$

For every $d = 1, 2, \ldots, a_{1}$, we count how many intervals in $\mathcal{T}$ are of length $d$. Notice that the multiples of $a_{1}$ are all marked, so the lengths of the intervals in $\mathcal{S}$ and $\mathcal{T}$ cannot exceed $a_{1}$. Let $x$ be an arbitrary integer with $0 \leqslant x \leqslant A-1$ and consider the interval $[x, x+d]$. Let $r_{1}, \ldots, r_{n}$ be the remainders of $x$ modulo $a_{1}, \ldots, a_{n}$, respectively. Since $a_{1}, \ldots, a_{n}$ are pairwise coprime, the number $x$ is uniquely identified by the sequence $(r_{1}, \ldots, r_{n})$, due to the Chinese remainder theorem.

For every $i = 1, \ldots, n$, the property that the interval $(x, x+d)$ does not contain any multiple of $a_{i}$ is equivalent with $r_{i} + d \leqslant a_{i}$, i.e. $r_{i} \in \{0, 1, \ldots, a_{i} - d\}$, so there are $a_{i} - d + 1$ choices for the number $r_{i}$ for each $i$. Therefore, the number of the remainder sequences $(r_{1}, \ldots, r_{n})$ that satisfy $[x, x+d] \in \mathcal{T}$ is precisely $(a_{1} + 1 - d) \cdots (a_{n} + 1 - d)$. Denote this product by $f(d)$.

Now we can group the last sum in (1) by length of the intervals. As we have seen, for every $d = 1, \ldots, a_{1}$ there are $f(d)$ intervals $Y \in \mathcal{T}$ with $|Y| = d$. Therefore, (1) can be continued as
$$\begin{equation*} \sum_{X \in \mathcal{S}} |X|^{2} = \sum_{Y \in \mathcal{T}} w(|Y|) = \sum_{d=1}^{a_{1}} f(d) \cdot w(d) = 2 \sum_{d=1}^{a_{1}} f(d) - f(1). \tag{2} \end{equation*}$$

Having the formula (2), the solution can be finished using the following well-known fact:

Lemma. If $p$ is a prime, $F(x)$ is a polynomial with integer coefficients, and $\deg F \leqslant p-2$, then $\sum_{x=1}^{p} F(x)$ is divisible by $p$.

Proof. Obviously, it is sufficient to prove the lemma for monomials of the form $x^{k}$ with $k \leqslant p-2$. Apply induction on $k$. If $k=0$ then $F=1$, and the statement is trivial.

Let $1 \leqslant k \leqslant p-2$, and assume that the lemma is proved for all lower degrees. Then
$$\begin{aligned} 0 & \equiv p^{k+1} = \sum_{x=1}^{p} \left( x^{k+1} - (x-1)^{k+1} \right) = \sum_{x=1}^{p} \left( \sum_{\ell=0}^{k} (-1)^{k-\ell} \binom{k+1}{\ell} x^{\ell} \right) \\ & = (k+1) \sum_{x=1}^{p} x^{k} + \sum_{\ell=0}^{k-1} (-1)^{k-\ell} \binom{k+1}{\ell} \sum_{x=1}^{p} x^{\ell} \equiv (k+1) \sum_{x=1}^{p} x^{k} \pmod{p} \end{aligned}$$
Since $0 < k+1 < p$, this proves $\sum_{x=1}^{p} x^{k} \equiv 0 \pmod{p}$.

In (2), by applying the lemma to the polynomial $f$ and the prime $a_{1}$, we obtain that $\sum_{d=1}^{a_{1}} f(d)$ is divisible by $a_{1}$. The term $f(1) = a_{1} \cdots a_{n}$ is also divisible by $a_{1}$; these two facts together prove that $\sum_{X \in \mathcal{S}} |X|^{2}$ is divisible by $a_{1}$.

The conventions from the first paragraph of the first solution are still in force. We shall prove the following more general statement:

(⊞) Let $p$ denote a prime number, let $p = a_{1} < a_{2} < \cdots < a_{n}$ be $n$ pairwise coprime positive integers, and let $d$ be an integer with $1 \leqslant d \leqslant p-n$. Mark all integers that are divisible by at least one of the numbers $a_{1}, \ldots, a_{n}$ on the interval $I = [0, a_{1} a_{2} \cdots a_{n}]$ of the real line. These points split $I$ into a number of smaller segments, say of lengths $b_{1}, \ldots, b_{k}$. Then the sum $\sum_{i=1}^{k} \binom{b_{i}}{d}$ is divisible by $p$.

Applying $(\boxplus)$ to $d=1$ and $d=2$ and using the equation $x^{2} = 2 \binom{x}{2} + \binom{x}{1}$, one easily gets the statement of the problem.

To prove $(\boxplus)$ itself, we argue by induction on $n$. The base case $n=1$ follows from the known fact that the binomial coefficient $\binom{p}{d}$ is divisible by $p$ whenever $1 \leqslant d \leqslant p-1$.

Let us now assume that $n \geqslant 2$, and that the statement is known whenever $n-1$ rather than $n$ coprime integers are given together with some integer $d \in [1, p-n+1]$. Suppose that the numbers $p = a_{1} < a_{2} < \cdots < a_{n}$ and $d$ are as above. Write $A' = \prod_{i=1}^{n-1} a_{i}$ and $A = A' a_{n}$. Mark the points on the real axis divisible by one of the numbers $a_{1}, \ldots, a_{n-1}$ green and those divisible by $a_{n}$ red. The green points divide $[0, A']$ into certain sub-intervals, say $J_{1}, J_{2}, \ldots, J_{\ell}$.

To translate intervals we use the notation $[a, b] + m = [a + m, b + m]$ whenever $a, b, m \in \mathbb{Z}$.

For each $i \in \{1, 2, \ldots, \ell\}$ let $\mathcal{F}_{i}$ be the family of intervals into which the red points partition the intervals $J_{i}, J_{i} + A', \ldots, J_{i} + (a_{n} - 1) A'$. We are to prove that
$$\sum_{i=1}^{\ell} \sum_{X \in \mathcal{F}_{i}} \binom{|X|}{d}$$
is divisible by $p$.

Let us fix any index $i$ with $1 \leqslant i \leqslant \ell$ for a while. Since the numbers $A'$ and $a_{n}$ are coprime by hypothesis, the numbers $0, A', \ldots, (a_{n} - 1) A'$ form a complete system of residues modulo $a_{n}$. Moreover, we have $|J_{i}| \leqslant p < a_{n}$, as in particular all multiples of $p$ are green. So each of the intervals $J_{i}, J_{i} + A', \ldots, J_{i} + (a_{n} - 1) A'$ contains at most one red point. More precisely, for each $j \in \{1, \ldots, |J_{i}| - 1\}$ there is exactly one amongst those intervals containing a red point splitting it into an interval of length $j$ followed by an interval of length $|J_{i}| - j$, while the remaining $a_{n} - |J_{i}| + 1$ such intervals have no red points in their interiors. For these reasons
$$\begin{aligned} \sum_{X \in \mathcal{F}_{i}} \binom{|X|}{d} & = 2 \left( \binom{1}{d} + \cdots + \binom{|J_{i}| - 1}{d} \right) + (a_{n} - |J_{i}| + 1) \binom{|J_{i}|}{d} \\ & = 2 \binom{|J_{i}|}{d+1} + (a_{n} - d + 1) \binom{|J_{i}|}{d} - (d+1) \binom{|J_{i}|}{d+1} \\ & = (1 - d) \binom{|J_{i}|}{d+1} + (a_{n} - d + 1) \binom{|J_{i}|}{d} \end{aligned}$$
So it remains to prove that
$$(1 - d) \sum_{i=1}^{\ell} \binom{|J_{i}|}{d+1} + (a_{n} - d + 1) \sum_{i=1}^{\ell} \binom{|J_{i}|}{d}$$
is divisible by $p$. By the induction hypothesis, however, it is even true that both summands are divisible by $p$, for $1 \leqslant d < d+1 \leqslant p - (n-1)$. This completes the proof of $(\boxplus)$ and hence the solution of the problem.