Consider an arbitrary sequence $\mathbf{a}$ of pairwise coprime integers $a_1<a_2<\dots<a_k$ where $a_1=p$ is prime. Take the interval $[0;a_1a_2\dots a_k]$, and mark all the points inside the interval divisible by at least one of the numbers $a_1,\dots,a_k$. Define $L(\mathbf{a})$ to be the sequence of the resulting small segments, i.e. the list $[x_0;x_1],[x_1;x_2],\dots,[x_{K-1},x_K]$ where $0=x_0<x_1<x_2<\dots<x_{K-1}<x_K=a_1\dots a_k$ are the dividing points. Furthermore, let $$S_t(\mathbf{a})=\sum_{\sigma\in L(\mathbf{a})} |\sigma|^t$$ be the sum of the $t$-th powers of the segments in $L(\mathbf{a})$. Now begin from the sequence in the problem statement, and define $\mathbf{a}_k$ to be the sequence $(a_1,a_2,\dots,a_k)$ for any $1\le k\le n$. Our objective is to obtain a recursion for $S_t(\mathbf{a}_k)$ modulo $p$. To produce a recursion, start from the interval $I=[0;a_1a_2\dots a_{k-1}]$, and extend it to the interval $I'=[0;a_1a_2\dots a_{k-1}a_k]$, which contains $a_k$ copies of the former. Let's first mark all numbers divisible by at least one of $a_1,a_2,\dots,a_{k-1}$ in $I'$. They divide the original segment $I$ into the segments of $L(\mathbf{a}_{k-1})$, and the segments that $I'$ is divided into form $a_k$ copies of those in $L(\mathbf{a}_{k-1})$, namely every $\sigma\in L(\mathbf{a}_{k-1})$ can be assigned a sequence $T(\sigma)$ of $a_k$ different subsegments in $I'$, namely $\sigma$ and its translates by $+(a_1\dots a_{k-1}),+2(a_1\dots a_{k-1}),\dots,+(a_k-1)(a_1\dots a_{k-1})$. (These groups of $a_k$ segments thus tile $I'$.) The idea is that if we now mark all the numbers divisible by $a_k$, then the newly marked points inside $T(\sigma)$ are such that for any $1\le \ell \le |\sigma|-1$, there is exactly one segment of $T(\sigma)$ divided into bits of length $\ell$ and then $|\sigma|-\ell$. To see this, firstly note that as all the points in $I'$ divisible by $a_1$ are already marked, we have $|\sigma|\le a_1<a_k$, hence there is at most one newly marked point in any segment of length $\sigma$. Now our claim is an immediate consequence of the fact that the numbers $0,(a_1\dots a_{k-1}),2(a_1\dots a_{k-1}),\dots,(a_k-1)(a_1\dots a_{k-1})$ form a complete residue system modulo $a_k$ (due to $a_1\dots a_{k-1}$ being relatively prime to $a_k$). Hence we obtain $$S_t(\mathbf{a}_k)=\sum_{\sigma\in L(\mathbf{a}_k)}|\sigma|^t=\sum_{\sigma\in L(\mathbf{a}_{k-1})}\left[a_k\cdot |\sigma|^t+\sum_{\ell=1}^{|\sigma|-1}(\ell^t+(|\sigma|-\ell)^t-|\sigma|^t)\right].$$ Let's now evaluate the sum $\sum_{\ell=1}^{x-1}(\ell^t+(x-\ell)^t-x^t)=-x^t(x-1)+2\sum_{\ell=1}^{x-1}\ell^t$. Pascal's identity implies that for $t+1<p$, this sum can be expressed modulo $p$ as a polynomial in $x$ with degree at most $t+1$ AND constant coefficient $0$. So let's proceed to fix $t\le p-2$ and $2\le k\le n$, and write the sum in the big bracket in the form $$a_k\cdot x^t+\sum_{\ell=1}^{x-1}(\ell^t+(x-\ell)^t-x^t)\equiv c_{t+1}x^{t+1}+c_tx^t+\dots+c_1x\pmod p$$ to show that $$S_t(\mathbf{a}_k)\equiv \underbrace{ \sum_{\sigma\in L(\mathbf{a}_{k-1})}(c_{t+1}|\sigma|^{t+1}+c_t|\sigma|^t+\dots+c_1|\sigma|) }_{c_{t+1}S_{t+1}(\mathbf{a}_{k-1})+c_{t}S_{t}(\mathbf{a}_{k-1})+\dots+c_{1}S_{1}(\mathbf{a}_{k-1})}\pmod p.$$ Therefore if $S_r(\mathbf{a}_{k-1})$ is $\equiv 0\pmod p$ for $r=1,2,\dots,t+1$, then $S_t(\mathbf{a}_k)$ will be divisible by $p$ as well. Trivially, $S_t(\mathbf{a}_1)\equiv 0\pmod p$ for positive integer $t$. However, we only know that $S_t(\mathbf{a}_2)\equiv 0\pmod p$ for $t=1,2,\dots,n$, since when we expressed $S_t(\mathbf{a}_2)$, we could only consider the polynomial when $t\le p-2$, where $p\ge n+2$. After that, we can induct and show that for $2\le k\le n$, $S_t(\mathbf{a}_k)\equiv 0\pmod p$ for $t=1,2,\dots,n+2-k$. In the special case $k=n$, we get just what we needed, that $S_2(\mathbf{a}_n)\equiv 0\pmod p$.

I think the following is a bit more direct than the above. Consider intervals of length strictly less than $a_1$ (so just ignore those of length $a_1$) Let $S = \{a_1, a_2, \cdots, a_n\}.$ We count intervals in the following way: Let the numbers in the subset $S_1 \subset S$ divide the left endpoint and the numbers in the subset $S_2 \subset S$ divide the right endpoint. Note that $S_1, S_2$ are disjoint. Let $S'$ be the set of numbers in $S$ but not in $S_1$ or $S_2$. Also force that the set $S'$ divides nothing on the interval, including boundaries. Let $f(S_1, S_2, x)$ be the number of intervals of length $x$ satisfying this property. Then clearly we want the sum \[ \sum_{(S_1, S_2), |S_1 \cap S_2| = 0} \sum_{x = 1}^{a_1-1} x^2 f(S_1, S_2, x). \] By the Chinese Remainder Theorem, $f(S_1, S_2, x) = \prod_{a_j \in S'} (a_j-x-1).$ Therefore, $x^2 f(S_1, S_2, x)$ is a polynomial of degree at most $n$ (since $|S'| \le n-2$). Therefore, $\sum_{x = 1}^{a_1-1} x^2 f(S_1, S_2, x) = 0.$ (just by using existence of primitive roots $\pmod{p}.$) So our whole sum is $0$ and we are done.

This solution seems too easy, so perhaps I have messed up somwehere. If not, then in my opinion this problem is not very difficult. Let $p = a_1$. We consider colors $2, 3, \dots, n$ and for each $i > 2$ color each marked point by all the colors $i$ such that $a_i$ divides it (hence some points, like $a_2a_3$, will have multiple colors). Now for ostentatious terminology. We consider the $a_2a_3 \dots a_n$ intervals of the form $[cp, cp+p]$ and call them blocks. For each block $B$, its phenotype is the set of $r \le n-1$ colors which appear in it (including at endpoints, and also note each color appears either zero or one times). Now, this partitions $B$ into sub-intervals (possibly empty) and hence induces a splitting $p = x_1 + \dots + x_r$ (where $x_i \ge 0$, from left to right). The genotype of the $B$ is the data of $(x_1, \dots, x_r)$ and the value of $B$ is $\sum_{i=1}^r x_i^2$. We claim that the sum of values of all blocks of a fixed phenotype is $0 \pmod p$. Indeed, by repeated application of the Chinese Remainder Theorem, we can deduce that each genotype appears an equal number of times. Hence, the sum of the values of these blocks is divisible by \begin{align*} \sum_{x_1 + \dots + x_r = p} \left( x_1^2 + \dots + x_r^2 \right) &= r \sum_{x_1 + \dots + x_r = p} x_1^2 \\ &= r \sum_{t=1}^{p-1} \sum_{x_2 + \dots + x_r = p-t} t^2 \\ &= r \sum_{t=1}^{p-1} t^2 \binom{p-t+r-2}{r-2} \\ &\equiv \frac{r}{(r-2)!} \sum_{t=1}^{p-1} t^2(1-t)(2-t)\dots(r-2-t) \pmod p \end{align*} In terms of $t$, the above polynomial has degree $r$. But, since $\sum_{t=1}^{p-1} t^s \equiv 0 \pmod p$ for any $1 \le s < p-1$, it follows that the above sum vanishes modulo $p$, which proves the claim and hence solves the problem. All this is motivated by just considering the $n=2$ and $n=3$ cases.

It's well-known that the sum $S(n)=\displaystyle\sum_{i=1}^{n} i^k$ is a polynomial in terms of $n$ and of degree $k+1$. We first show that if $k<p-1$ for some prime $p$, then the coefficients of each term in the polynomial, when written in lowest (i.e. irreducible) form, has denominator relatively prime to $p$. Indeed, consider the values $S(0), S(1), S(2), \cdots , S(k+1)$. Since the polynomial is of degree $k+1$, it is uniquely determined based on the previous $k+2$ values by Lagrange's Interpolation theorem. By Lagrange's Interpolation theorem again this polynomial is actually \[\displaystyle\sum_{i=0}^{k+1} S(i)\displaystyle\prod_{j\in [0, k+1]\backslash \{i\}}\frac{x-j}{i-j}.\]With $|i-j|\le k+1<p$ (and $i\neq j$ so it cannot be zero either), we know that the denominator can never be divisible by $p$. Now we turn to the problem, and notice that each segment is no longer than $a_1$. We prove, by inducting on $n\ge 2$, that the there exists a polynomial $P_n$ with degree at most $n-2$ such that its coefficients are rational with denominator relatively prime to $a_1$, and the number of segments with length $i$ (for $i=1, 2, \cdots , a_1-1$) is $P_n(i)$. The case with $n=1$ is not applicable here: obviously $a_1^2$ is the sum of square of the single segment and is divisible by $a_1$. For $n=2$, observe that for each $k\in [0, a_1-1]$, from the fact that $a_1$ and $a_2$ are coprime we have $\{k, a_1+k, 2a_1+k, \cdots , (a_2-1)a_1+k\}$ as complete residue. This means for each $k$, considering the replicated "supersegment" $[0, a_1], [a_1, 2a_1], \cdots , [(a_2-1)a_1, a_2a_1]$, exactly one of them have a cut at $k$. Moreover, each segment has at most one cut sine $a_2>a_1$. Therefore after the cut by $a_2$ we have one segment of each of $(1, a_1-1)$, $(2, a_1-2)$, $\cdots$, $(a_1-1, 1)$ and the rest uncut. This means $P_2(0)=P_2(1)=\cdots P_2(a_1-1)=2$, a constant polynomial of degree 0. To proceed with our inductive steps, let say we have $P_{n-1}(i)$ segments of length $i<a_1$, and $x$ segments of length $a_1$. Considering the replication of each segment by $a_n$ times, we, again (by similar logic as above) know that the $a_2$ segments will be 'cut' distributed into $(1, i-1), (2, i-2), \cdots , (i-1, 1)$ and the rest uncut. Therefore, we know that the number of segment of length $i$ for $i<a_1$ is: $(a_2-(i-1))P_{n-1}(i)+2(P_{n-1}(i+1)+\cdots +P_{n-1}(a_1-1)+x)$. Observe that, $(a_2-(i-1))P_{n-1}(i)$ is a polynomial of degree $\deg(P_{n-1})+1$, and this is the same for the sum $P_{n-1}(i+1)+\cdots +P_{n-1}(a_1-1)$ (think of it as "sum to $a_1-1$" minus "sum to $i-1$" and the result follows), and $2x$ is a constant across the $i$'s. Moreover, from the fact that $P_{n-1}$ has coefficients with denominator not divisible by $a_1$, this is the same for $P_n$ with degree $n-2\le a_1-4$, as proven above. Now we can finish the proof. Now consider $\displaystyle\sum_{i=1}^{a_1-1}i^2P_n(i)$. This, together with the segments of length $a_1$, is the sume of square we want (the segments of length $a_1$ can be ignored, though, since the length itself is divisible by $a_1$). Letting $P_n(i)=b_{n-2}i^{n-2}+\cdots +b_0i^0$ we have $\displaystyle\sum_{i=1}^{a_1-1}i^2P_n(i)$ $\displaystyle\sum_{i=1}^{a_1-1}b_{n-2}i^n+\cdots +b_0i^2$. Rearranging the terms gives $\displaystyle\sum_{i=0}^{n-2}b_i(1^{i+2}+2^{i+2}+\cdots +(a_1-1)^{i+2})$ Now again $b_i$ are rational numbers with denominator not divisible by $a_1$, so it suffices to show that $1^{i+2}+2^{i+2}+\cdots +(a_1-1)^{i+2}$ is divisible by $a_1$ for $i+2\le a_1-2$. Denoting $g$ as the primitive root of $a_1$ we have $1^{i+2}+2^{i+2}+\cdots +(a_1-1)^{i+2}$ $\equiv g^0+g^{1(i+2)}+\cdots +g^{(a_1-2)(i+2)}$ $=\frac{g^{(a_1-1)(i+2)}-1}{g^{i+2}-1}$ $\pmod{a_1}$. By the definition of primitive root and the fact that $i+2\le a_1-2$ we have $g^{i+2}\not\equiv 1\pmod{a_1}$ while $g^{(a_1-1)(i+2)}\equiv 1\pmod{a_1}$ by Fermat's Little theorem. Hence the sum is itself divisible by $a_1$. Q.E.D.

Please check my proof Looks like my solution has a ~95 % chance of being a fakesolve anyway, because at only one point it implicitly uses $a_1 \geq n+2$

Kayak wrote: Now, we count the number of tuples with score $k$ in this way: In a good tuple $(b_1, \cdots, b_n)$ with score $k$, there are $i$ numbers $b_{j_1}, \cdots, b_{j_i}$, which are identically zero, with $1 \leq i \leq n - 1$, there are $m$ numbers $b_{n_1}, \cdots, b_{n_m}$ which have value $k$ with $1 \leq m \leq n - i$ , and the remaining $n-i-m$ numbers $b_{d_1}, \cdots, b_{d_q}$ has value $k < b_{d_j} < a_{d_j}$. So, it's easy to see that $$ \text{ Number of tuples with score k} := F(k) = \sum_{i = 1}^{n-1} \sum_{m = 1}^{n-i} \binom{n}{i} \binom{n-i}{m} g_{i+m}(k)$$, where $g_{i+m}(k)$ is the coefficient of $x^{n-i-m}$ in $\prod (x-(a_i-1-k))$. I think the counting here is a little wrong. After you fix some of them to be zero and some of them to be $k$, the remaining won't have $g_{i+m}(k)$ ways to happen since you will have to keep track of which indices $i$ have already been fixed (more possibilities when larger indices are not fixed) but $g_{i+m}(k)$ ignores that (it actually counts all possibilities I believe). It should be ok once you split up the sum to the different cases though. Quote: We finally get $$S = \sum_{\text{All good tuples} N_i} Score[N_i]^2 \equiv \sum_{k = 1}^{a_1-1} F(k) k^ 2 = \sum_{k = 1}^{a_1-1} \sum_{i=0}^{n-2} c_i k^{i+2}$$$$ = \sum_{i = 0}^{n-2} c_i [\sum_{k=1}^{a_1-1} k^{i+2}] \equiv 0 \mod a_1$$, as desired, where the last conclusion is just a five second consequence of primitive roots. You should not have changed the summation index from $n-2$ to $a_1 - 1$. Since your terms are actually $k^{i+2}$, this gives us an exponent of $a_1+1$ if you use $a_1-1$ and the sum can no longer be claimed to be zero (the claim only works if the exponent is $\leq p-2$.)

Ooops my counting was wrong. Thanks a lot, fattypiggy for pointing that out ! 1. So the counting can be fixed in this way: For $2 \leq m \leq n$, let $g(m)$ be the number of ways to fill up a $m$-tuple with either $0$ or $k$, and containing atleast one $0$ and one $k$. Let $h_m(k)$ be the number of good $n$-tuples with score $k$ of which there are total of $m$ elements which are either $0$ or $k$. So, $$\displaystyle h_m(k) = \sum_{\text{all possible slots with lenght n-m}} g(m) * (\text{Number of ways we can fill the n-m slots with} \; \; k<b_i<a_i)$$$$ = g(m) * \sum_{\text{All possible n-m distnict elements}\; \; a_i, a_j, \cdots, a_q \text{from the set} \; \; \{ a_1, \cdots, a_n\} }(a_i-1-k)(a_j-1-k) \cdots (a_q-1-k)$$$$ = g(m) * (\text{Coefficient of} \; \; x^{n-m} \; \; \text{in} \; \; \prod (x-(a_i-1-k))$$$$ = g(m) * \text{A integral polynomial of degree n-m}$$. So, $$F(k) = \sum_{m = 2}^{n} h_m(k) = \text{ An integral polynomial of degree n-2}$$, and the proof can be continued from here. . 2. Sorry, but I don't quite get the problem about changing index, as the exponent is $i$ (not $k$), and $i$ is summed from $i = 0$ to $i = n-2$. I mean, if we let $f(i):= \sum_{k=1}^{a_1-1} k^{i+2}$, then isn't $f(i) \equiv 0 \mod a_1$ for all $0 \leq i \leq n - 2 \leq a_1 - 4$ ?

Oops I read the sum wrongly, you are right.

Does this work? hajimbrak wrote: Let $a_1 < a_2 < \cdots <a_n$ be pairwise coprime positive integers with $a_1$ being prime and $a_1 \ge n + 2$. On the segment $I = [0, a_1 a_2 \cdots a_n ]$ of the real line, mark all integers that are divisible by at least one of the numbers $a_1 , \ldots , a_n$ . These points split $I$ into a number of smaller segments. Prove that the sum of the squares of the lengths of these segments is divisible by $a_1$. Proposed by Serbia Note that each number $x \in [0,a_1a_2\dots a_n]$ can be expressed as a modular system $x \equiv m_i \pmod{a_i}$ for all $1 \le i \le n$. Now consider an interval of length $\ell$. Working mod $a_1$, it is nice enough to let $1 \le \ell \le a_1-1$, otherwise a multiple of $a_1$ barges in. Suppose $A$ is the set of these numbers that divide the left end, while $B$ is the set of those that divide the right end. Let $C$ be the set of these numbers not in $A$ or $B$. Accounting for the modular system of the farthest point (each residue mod elements of $C$ being at least $\ell$), we see that the sum we want is $$\sum_{|A \cap B|=0} \sum^{a_1-1}_{\ell=1} \ell^2\prod_{j \in C} (a_j-\ell-1).$$Consider it as $\sum^{a_1-1}_{i =0} f(i) \pmod{a_1}$ with $f \in \mathbb{Z}[x]$ being a polynomial of degree $\le 2+(n-2)<a_1-1$. Since $a_1$ is prime, primitive roots finish the rest.

Solved with naman12. Define $a_1=p$. Note that every interval has length at most $p$, so we must have that if $x$ is the length of an interval, then $1\leq x\leq p$. However, we can discard $x=p$ as that is a useless number (modulo $p$), so we only consider $1\leq x\leq p-1$. Fix some $x$. We aim to count the intervals of length $x$. Let this number be $f(x)$. Suppose the interval of length $x$ was $[a,a+x]$. Consider the partition of the set \[[n]=\{1,2,\ldots,n\}\]into $C,D,E$ such that we have the following congruences: $a\equiv 0\pmod{a_c}\quad\forall c\in C$ $a\equiv -x\pmod{a_d}\quad\forall d\in D$ $a\equiv -b_e\pmod{a_e}\quad\forall e\in E$ Note that $E$ is an arbitrary subset of $[n]$ with cardinality at most $n-2$ (because $C,D$ are nonempty). Note that as we have no multiples of $a_e$ for $e\in E$ inside the interval $[a,a+x]$, we have \[x<b_e\leq a_e-1\implies x+1\leq b_e\leq a_e-1\]Thus, we get there are $a_e-x-1$ such values of $b_e$, so thus for each fixed $x$ and $E$, we have \[\prod_{e\in E}(a_e-x-1)\]such intervals. Summing over all $E$, we get \[f(x)=\sum_{\substack{E\subset [n]\\|E|\leq n-2}}(2^{n-|E|}-2)\prod_{e\in E}(a_e-x-1)\]where the $2^{n-|E|}-2$ were the number of ways to count $C,D$ such that they are both nonempty. Note that $f(x)$ has degree at most $n-2$. We shall use this said fact later. Thus, our sum overall is congruent to modulo $p$ \[\sum_{1\leq x\leq p-1} x^2\sum_{\substack{E\subset [n]\\|E|\leq n-2}}(2^{n-|E|}-2)\prod_{e\in E}(a_e-x-1)\]Now, by switching the order of the sums, we get \[\sum_{\substack{E\subset [n]\\|E|\leq n-2}}(2^{n-|E|}-2)\sum_{1\leq x\leq p-1} x^2\prod_{e\in E}(a_e-x-1)\]Note that \[x^2\prod_{e\in E}(a_e-x-1)\]is a polynomial in $x$ degree at most $n\leq p-2$. Using the fact that \[\sum_{j=1}^{p-1}j^k\equiv 0\pmod p\]for $1\leq k\leq p-2$, we get that \[x^2\prod_{e\in E}(a_e-x-1)\equiv 0\pmod{p}\]which completes the proof of the problem.

Remark: Great problem. I loved the double counting idea, and the expression vanishing modulo $a_1$ just felt so satisfying! We may consider all intervals' sizes modulo $a_i$ so that the size of each interval is $\in [0, a_1 - 1]$. This problem will be solved by counting how many minimal intervals there are of each size $x$ from $0 \to a_1 - 1$. Consider all minimal intervals of size $\ell$ for some fixed $\ell \in [0, a_1 - 1]$. We wish to count how many there are. Take an arbitrary interval $[t, t + \ell]$. The set $S$ of all $a_i$ that divide $t$ must be disjoint from the set $T$ of all $a_i$ that divide $t + \ell$ since $\ell <$ all $a_i$. Let the set of remaining $a_i$ not in $S$ or $T$ be $R$. Clearly no number in our interval $[t, t + \ell]$ is divisible by an element in $R$ else this interval is not minimal. Given $S$, $T$, and $\ell$, I claim that there are\[\prod_{a_k \in R} (a_k - \ell - 1)\]intervals of size $\ell$ having left bound divisors set $S$ and right bound divisors set $T$. We count how many possible left bounds there are. Clearly the left bound is already decided modulo $a_i$ in $S$ and modulo $a_j$ in $T$. It remains to count possible remainders modulo $a_k$ in $R$. If we let $b$ be the left bound, we cannot have any number in $[b, b + \ell]$ divisible by $a_k$. Hence, among the $a_k$ possible residues, $\ell + 1$ of them are bad, hence a total of $a_k - \ell - 1$ possible residues modulo $a_k$ for all $a_k \in R$. So indeed, for fixed $S, T, \ell$, the number of intervals is\[\prod_{a_k \in R} (a_k - \ell - 1)\]as desired. It remains to evaluate the sum over all $\ell : 1 \to a_1 - 1$ and disjoint nonempty $S, T$. That is,\[\sum_{|S \cap T| = \emptyset} \sum_{\ell = 1}^{a_1 - 1} \left(\ell^2 \prod_{a_k \in R} (a_k - \ell - 1)\right)\]modulo $a_1$. I claim that for each $S, T$, the expression\[\sum_{\ell = 1}^{a_1 - 1} \left(\ell^2 \prod_{a_k \in R} (a_k - \ell - 1)\right)\]vanishes modulo $a_1$. Indeed, since $S, T$ are nonempty, $|R| \leq n - 2$, so\[\ell^2 \prod_{a_k \in R} (a_k - \ell - 1)\]is a polynomial in $\ell$ with degree at most $n$. Furthermore, note that $\sum_{x = 1}^{p-1} {x^k} \equiv 0 \pmod p$ for all primes $p$ and $x$ relatively prime to $p$, where $k \in [1, p-2]$. This can be proven by primitive roots: let $g$ be a primitive root modulo $p$ with order $p-1$. Then, the sum can be written as\[g^k + g^{2k} + \ldots + g^{(p-1)k} = g^k\left(\frac{g^{(p-1)k} - 1}{g^k - 1}\right) \equiv 0 \pmod p\]where we used geometric series formula and the fact that the order of $g$ modulo $p$ is $p-1$. So indeed, as we sum this polynomial $\ell^2 \prod_{a_k \in R} (a_k - \ell - 1)$ across all $\ell$ from $1 \to a_1 - 1$, we can apply this primitive roots property to make the expression $0$ modulo $a_1$. As we sum over all nonempty $|S \cap T| = \emptyset$, we are just summing zeroes modulo $a_1$, so our final result is $0$ modulo $a_1$, as desired. $\blacksquare$ Note: A minimal interval is an interval that does not contain any part of another interval except for possible the endpoints. Clearly, summing the squares of the sizes of the minimal intervals is what we want since we do not wish to deal with overlaps.

Somehow I spent >50% of solving time figuring out why my key claim implies the problem. Say a number is $\emph{special}$ if it is divisible by one of $a_1,a_2,\dots,a_n.$ Fix a subset $S$ of $\{a_1,a_2,\dots,a_n\}$ and an integer $1\le d\le a_1-1.$ $\textbf{Key Claim: }$ The number of pairs of consecutive numbers $x,y$ such that (1) $y-x=d$, (2) $a\mid x$ or $a\mid y$ for all $a\in S,$ and (3) no special numbers are between $x$ and $y$ is $$(2^{|S|}-2)\prod_{a\not\in S}(a-d-1).$$$\emph{Proof: }$ Since no $a\in S$ can divide both $x$ and $y,$ there are exactly $2^{|S|}-2$ ways to choose which elements divide $x$ and which divide $y.$ Then, the residues of $x,y$ modulo each elements of $S$ is fixed. Now consider some $a\not\in S.$ Since there can be no number divisible by $a$ between $x$ and $y,$ there are exactly $a-d-1$ possible residues choices; namely, $$x\equiv 1,y\equiv d+1,$$$$x\equiv 2,y\equiv d+2,$$$$\vdots$$$$x\equiv a-d-1,y\equiv a-1.$$Multiplying over all $a\not\in S$ yields the desired expression. $\blacksquare$ Now define $f(i,k)$ as the $(n-i)$th symmetric sum of $a_1-k,a_2-k,\dots,a_n-k.$ Using the above claim, the sum of the squares of the lengths of the segments is \begin{align*} \sum_{d=1}^{a_1-1}\sum_{i=2}^{n}(d^{2}(2^i-2)f(i,d+1)) &= \sum_{i=2}^{n}\left[(2^i-2)\sum_{d=1}^{a_1-1}(d^{2}f(i,d+1))\right] \end{align*}Since $d^{2}f(i,d+1)$ is a polynomial expression in $d,$ with degree less than $a_1-1,$ we get a remainder of $0$ when we sum over all residues. This implies the desired conclusion.

Lemma. Suppose $P(x)$ is a polynomial with degree less than $n$, then $$\sum_{i=1}^{a_1}iP(i)\equiv 0\pmod{a_1}$$Proof. This is a simple consequence of the fact that $$a_1|1^k+2^k+...+a_1^k$$For every $k=1,2,...,a_1-2$. Hence, letting $P(n)=b_0+b_1x+...+b_{n-1}x^{n-1}$ we have $$\sum_{i=1}^{a_1}iP(i)\equiv \sum_{j=0}^{n-1}\sum_{i=1}^{a_1} b_ji^{j+1}\equiv \sum_{j=0}^{n-1}0\equiv 0\pmod{a_1}$$$\blacksquare$ Now consider everything modulo $a=a_1a_2...a_n$, (that is, regarding $0$ and $a_1a_2...a_n$ as the same number). Define $$S=\{(x_1,x_2,...,x_n):0\leq x_i\leq a+i-1\}$$By Chinese remainder theorem, every integer in $\mathbb Z/a\mathbb Z$ bijectively corresponds to an element in $S$, call the corresponding element its coordinates. Notice that a point is marked if and only if its coordinates have some zero entries. Now, for each $0\leq j\leq a-1$, define $I(j)$ to be the length of interval containing it (in particular, if $j$ is in two intervals (which means it is a marked point) then $I(j)$ denotes the total length of the two intervals. Suppose the marked points are $c_0,c_1,c_2,...,c_m$ and the intervals are $I_k=[c_{k-1},c_k]$, then $$T\overset{\text{def}}{=}\sum_{k=1}^m|I_k|^2=\sum_{k=1}^k(c_k-c_{k-1})|I_k|=\sum_{j=0}^{a-1}I(j)\hspace{30pt}(1)$$Now for every integer $0\leq j\leq a-1$, suppose $d(j)=(d_1,d_2,...,d_n)$ is its coordinates. Then $d(j+k)=(d_1+k,d_2+k,...,d_n+k)$, therefore, there are $$f(j)=\underset{1\leq i\leq n,d_i\neq 0}{\min}d_i$$numbers between $j$ and the previous marked number. Similarly, there are $$g(j)=\underset{1\leq i\leq n,d_i\neq 0}{\min}a_i-d_i$$numbers between $j$ and the next marked number, therefore $I(j)=f(j)+g(j)$. Notice that $f(j)=g(-j)$, hence $$\sum_{j=0}^{a-1}f(j)=\sum_{j=0}^{a-1}g(j)$$Now from $(1)$ we have $$T=\sum_{k=1}^m|I_k|^2=\sum_{j=0}^{a-1}I(j)=2\sum_{j=0}^{a-1}f(j)\hspace{30pt}(2)$$obviously $f(j)\leq a_1-1$, now for each $0\leq x\leq a_1-1$, there are exactly (the ones without $1,2,...,p-1$ minus the ones without $1,2,...,p$.) $$P(x)\overset{\text{def}}{=}\prod_{i=1}^n(a_i-x+1)-\prod_{i=1}^n(a_i-x)$$numbers $0\leq j\leq a-1$ such that $f(j)=x$, therefore, each $x$ contributes $xP(x)$ to $T$. Notice that $P(x)$ is a polynomial with degree $n-1$, hence by the lemma, we have $$T=\sum_{x=1}^{a_1}xP(x)\equiv 0\pmod a_1$$as desired.

Ignore this.

got carried lmao We split each interval of length $p=a_i$ into different "phenotypes." We split phenotypes based on the kinds of multiples of $\{a_i\}_{i\geq 2}$ that appear. Note that an interval with a multiple of $a_2$ and $a_3$ is different from an interval with a multiple of $a_2a_3$. We claim that the sum over each phenotype is 0 mod $p$. By CRT, if the phenotype has $r$ distinct values, then the sum over this phenotype is a multiple of \begin{align*} \sum_{x_1+x_2+\cdots x_r = p, x_i\geq 1} x_1^2+\cdots x_r^2 &= r\cdot \sum_{x_1+x_2+\cdots x_r = p} x_1^2\\ &= r\cdot \sum_{t\geq 1} \sum_{x_2+\cdots x_r=p-t} t^2\\ &= r\cdot \sum_{t\geq 1} t^2 \cdot \binom{p-t-1}{r-2} \end{align*}Note that the degree of the expression with respect to $t$ is at most $2+r-2 = r+1 \leq (n-1) +1 =n$. Thus, $\deg \leq n \leq a_i-2$. Thus, since the sum of a polynomial with degree $\leq p-2$ mod $p$ is 0, this expression is 0, and we're done.

Let $S=\{a_1,a_2 \dots ,a_n\}.$ Take any segment $s.$ Let $S_{s,1}$ be the set of all integers $\in S$ dividing the left endpoint, and $S_{s,2}$ be the set of all integers $\in S$ dividing the right endpoint. Then for any $a_ i \in S \setminus (S_{s,1} \cup S_{s,2}),$ the residue of the left endpoint is between $1$ and $a_i - x - 1$ inclusive if $x$ is the length of $s.$ Furthermore, because of CRT, each of these residue combinations corresponds with exactly one left endpoint satisfying them that is valid. This allows us to precisely enumerate the number of segments with some length $x$ and a fixed $S_{s,1}$ and $S_{s,2}$ as $$\prod_{a_i \in S \setminus (S_{s,1} \cup S_{s,2})} (a_i - x-1)$$and our original sum can be written as $$\sum_{S_{1}, S_{2}} \sum_{x=1}^{a_1-1} x^2 \prod_{a_i \in S \setminus (S_{1} \cup S_{2})} (a_i - x-1) \pmod{a_1},$$where we sum over all $S_1,S_2 \in S$ where $S_1, S_2 \ne \emptyset$ and $S_{1} \cap S_{2} = \emptyset.$ Recall the following well known lemma. Lemma. For a given prime $p,$ the sum $1^k+2^k+ \dots (p-1)^k \equiv 0 \pmod{p}$ unless $(p-1) \mid k.$ Our sum can just be split into a sum of summations of this form because any particular $x$ in the summation is raised to the power of at most $2 + (n-2) < a_1-1$ so we're done.

Let $P_i(m)$ be the sequence of polynomials defined by $P_1(m) = m^2, P_{i+1}(m) = (m+1)P_i(m)-2\sum_{k = 0}^{m}P_i(m)$. Notice $P_i(m)$ is an integer-valued polynomial of degree $i+1$. Thus since $a_i \geq n+2 > n+1$, all of the $P_i(m)$ for $1 \leq i \leq n$ when summed over segments on a line with a single segment of length $a_1$ is $\equiv 0$ since they are generated from ${m \choose k}$ for $1 \leq k \leq n+1$ (and $P_i(0) = 0$). It is easy to see that we can induct that $P_1(m), P_2(m), \ldots, P_{n+1-i}(m) \equiv 0$ when summed over all segments on the segments generated by $a_1, a_2, \ldots, a_i$, for all $i$ up to $n$ so we are done.

First, note that by the Chinese remainder theorem, we can treat each number from $0$ to $a_1a_2\cdots a_n$ as a vector $(r_1,r_2,\cdots,r_n)$, where $r_i$ is its residue mod $a_i$. Now, define the polynomial \[P(x)=(a_1-x)(a_2-x)\cdots(a_n-x)\] Claim: Let $1 \le k \le a_1$.The number of intervals with length $\geq k$ is $P(k-1)-P(k)$. Proof: Count the starting points of the intervals. Note that each coordinate in the vector $(r_1,r_2,\cdots,r_n)$ cannot be from $-1,-2,\ldots -(k-1)$. Hence, choosing each residue, we have \[(a_1-k+1)(a_2-k+1)\cdots(a_n-k+1)=P(k-1)\]ways to get a starting point. However, starting point must have at least one coordinate which is $0$, so we subtract those with no coordinates in $0,-1,\ldots -(k-1)$, which is $P(k)$, proving the claim. Thus, we have \[\text{sum of squares of intervals}= \sum_{k=1}^{a_1} (2k-1)[P(k-1)-P(k)]=P(0)+2\sum_{k=1}^{a_1} P(k)\]This is because in the left sum, each interval of length $k$ is counted $1+3+\cdots+2k-1=k^2$ times. The second inequality is simply grouping $P(k)$ terms together. Also, if we are considering mod $a_1$, we can ignore the $P(0)$ term as it is divisible by $a_1$. Now, we are done as $P(x)$ is a polynomial of degree at most $a_1-2$, so $\sum_{k=1}^{a_1} P(k) \equiv 0 \mod a_1$ due to the well-known fact that $\sum_{i=1}^{p} i^m \equiv 0 \mod p$ for all primes $p$ and integers $0 \le m < p-1$.

Nice problem. Let $p = a_{1}$ be a prime. Since $p = a_{1} < a_{i}$ for all $1 < i \leq n$, each segment length is less than $p$. For $1 \leq k \leq p - 1 $, let $f(k)$ be the number of segment that has length $k$. Now consider the following claim: Claim: $f$ is a polynomial. Proof. Let $[a , a + k]$ be a segment of length $k$. Then there are indices $i , j$ such that $a \equiv 0 (a_{i}) , a \equiv -k (a_{j})$, and for all $s \neq i , j$ we have $a \not\equiv -1,..., -(k - 1) (a_{s})$ . Let $S(i , j)$ be the set of integer in range $0 \leq x \leq a_{1}a_{2} .... a_{n} - k$ such that $x \equiv 0 (a_{i}) , x \equiv -k (a_{j})$, and for all $s \neq i , j$, $x \not\equiv -1,..., -(k - 1) (a_{s})$. Then $f(k) = |S(1 , 2) \cup S(1 , 3) \cup ... \cup S(n - 1 , n)|$. By inclusion exclusion principle, we have $S(1 , 2) \cup S(1 , 3) \cup ... \cup S(n - 1 , n)$ = $\sum_{1 \leq i , j \leq n} S(i , j) - \sum_{1 \leq i , j , k , l \leq n} S(i , j) \cap S(k , l) + ... $. By Chinese remainder theorem it's not hard to see that there exists $g(x) \in \mathbb{Z}[x]$ such that $|S(i_{1} , j_{1}) \cap S(i_{2} , j_{2}) \cap ... \cap S(i_{m} , j_{m})| = g(k)$ and deg $g \leq n - 2$. Thus $f$ is a polynomial of degree most $n - 2$. $\blacksquare$ It's enough to prove that $p \mid \sum_{1 \leq k \leq p - 1} f(k)k^2$ and since deg $f(k)k^2 \leq n < p - 1$ it's well known that $p \mid \sum_{1 \leq k \leq p - 1} f(k)k^2$. This completes proof. $\blacksquare$

is this right? Fix $a_1=p$. We will prove the general fact that for any integer $k \geq 1$, if $n \leq p-k$ then sum of the $k$-th powers of the intervals formed is divisible by $p$. The base case of $n=1$ is trivial. Now suppose this is true for all $k$ (satisfying the inequality) for $n-1$ variables. When we add the $n$-th variable, namely $a_n$, we glue together $a_n$ "copies" of the previous segment $I'$ and then add in the multiples of $a_n$ to form $I$. Since $a_n$ is coprime with $a_1\ldots a_{n-1}$, each interval in $I'$ gets split into two exactly once in every possible way somewhere—i.e. an interval of length $4$ will get split into $3$ and $1$ once, $2$ and $2$ once, and $1$ and $3$ once. Suppose that the lengths of the intervals in $I'$ are $x_1,\ldots,x_m$. By inductive hypothesis, it suffices to show that the change in the sum of the $k$-th powers is divisible by $p$. This change is given by $$\sum_{i=1}^m\sum_{j=1}^{x_i-1} (x_i^k-j^k-(x_i-j)^k).$$For fixed $x_i$, the individual term we are summing over $j$ is an integer polynomial in $j$ with degree $k$ with constant term $0$, hence its partial sum will equal $p(x_i)/(k+1)!$, where $p$ is a fixed (depending only on $k$) integer polynomial with degree $k+1$ and constant term $0$. Note that $k \leq p-n \leq p-2 \implies p \nmid (k+1)!$, so if $p(x)=p_{k+1}x^{k+1}+\cdots+p_1x$ it suffices to show that $p$ divides $$\sum_{i=1}^m p(x_i)=\sum_{i=1}^m\sum_{j=0}^{k+1} p_jx_i^j=\sum_{j=1}^{k+1}\sum_{i=1}^m p_ix_i^j.$$Since $n \leq p-k \implies (n-1) \leq p-(k+1)$, by inductive hypothesis it follows that for any $1 \leq j \leq k+1$ we have $p \mid \sum_{i=1}^m x_i^j$, hence $p$ certainly divides the above summation as well. $\blacksquare$

Let us count the number of intervals whose length is exactly $x$, where $1\le x\le a_1-1$. While there do exist intervals of length $a_1$, we do not care about them because we only care about the sum of squares of interval lengths $\pmod {a_1}$. Each interval must contain a starting point and an ending point. Call those integers $I_S$ and $I_E$, respectively. Let $S$ be the set of all primes $a_i$ that divide $I_S$ and $E$ be the set of all primes $a_i$ that divide $I_E$. If $a_i\in S\cap E$ then $a_i\mid x<a_i$, which is a contradiction. Thus, $S$ and $E$ are disjoint. Let the set of primes $a_i$ in neither $S$ nor $E$ be $N$. $~$ Now, we are ready to begin counting. Consider $I_S$. Given the values of $S$ and $E$, we know exactly the value of $I_S\pmod {a_i}$ for any $a_i\in S\cup E$. For any $a_i\in N$, we know $x+1$ values $\pmod a_i$ which $I_S$ cannot be, namely $0,-1,-2,\dots,-x$. Thus, there are $a_i-x-1$ values that it can take. By the Chinese Remainder Theorem, the total number of possible values of $I_S$, and thus the total number of intervals is \[\prod_{p\in N}{p-x-1}\]And so the sum of squares of these is $x^2\prod_{p\in N}{p-x-1}$. Note that this can be represented as a polynomial in $x$: \[a_kx^k+a_{k-1}x^{k-1}+\dots+a_1x+a_0\]By primitive roots, since $k\le n<a_1-1$, by primitive roots the sum of that polynomial over $1$, $2$, $\dots$, $a_1-1$ is equal to $0$. We are done.

Love how all the little random conditions on $a_1$ all come together at the end I don't think this is particularly easy for N6 actually; there are a lot of things you can do which don't work, and part of the difficulty is having the confidence to see that you can actually compute according to the labels $m$. We will split $I$ into intervals of the form $(ia_1, (i+1)a_1)$ for $0 \leq i \leq a_2a_3\cdots a_n - 1$. In particular, assign to every interval $I_1$ a label $m = \mathcal F(I_1)$ which corresponds to the number of positive integers in $\{a_2, a_3, \dots, a_n\}$ which have a multiple in $I_1$. (Observe that every such number has at most one multiple.) I claim that the sum of the squares of the distances across all intervals with label $m$ for some fixed $m$ is a multiple of $a_1$, which will imply the problem statement. To see this, set $|S| = m$ to be that set for one such interval $I_1$. Let $0 \leq r_i \leq a_1 - 1$ for $1 \leq i \leq m$ be the remainders when $(i+1)a_1$ is divided by each of the elements of $S$. We may sort $r_1 \leq r_2 \leq \cdots \leq r_m$, and the desired sum $$\mathcal S(I_1) = r_1^2 + (r_2-r_2)^2 + \cdots + (r_m - r_{m-1})^2 + (a_1 - r_m)^2.$$For simplification, let $d_1 = r_1$, $d_i = a_i - a_{i-1}$ for $2 \leq i \leq m$, and $d_{m+1} = a_1 - r_m$. Now we compute across all $I_1$ with $\mathcal F(I_1) = m$, noting that these $\mathcal S(I_1)$'s cover all possible valid combinations of the $a_i$: \begin{align*} \sum_{\mathcal F(I_1) = m} \mathcal S(I_1) &= \sum_{d_1+\cdots+d_{m+1} = a_1} d_i^2 \\ &= \sum_{k = 1}^{a_1} k^2 {m+a_1 - k \choose m} \\ &\equiv (-1)^m \sum_{k=1}^{a_1} \frac{k^2(k-1)(k-2)\cdots(k-m)}{m!} \\ &\equiv \frac{(-1)^m}{m+1} \sum_{k=1}^{a_1} k \cdot {k \choose m+1} \\ &\equiv \frac{(-1)^m}{m+1} \sum_{k=1}^{a_1} (k+1){k \choose m+1} - \sum_{k=1}^{a_1} {k \choose m+1} \\ &\equiv \frac{(-1)^m}{m+1} \left(\frac 1{m+2} \sum_{k=1}^{a_1} {k+1 \choose m+2} - \sum_{k=1}^{a_1} {k \choose m + 1}\right) \\ &\equiv \frac{(-1)^m}{m+1} \left(\frac 1{m+2}{a_1 + 2 \choose m+3} - {a_1 + 1 \choose m+2}\right). \end{align*}Here all congruences are modulo $a_1$. By invoking $a_1$ prime and $a_1 + 2 \geq n + 4 > m+3$ (and similarly $a_1 + 1 > m+2$), we may conclude that both terms in the parentheses are multiples of $a_1$. Thus the original sum is a multiple of $a_1$, as needed.

Fix some $p = a_1, a_2, \ldots, a_n$ satisfying the problem conditions. For any positive integer $k\le a_1 a_2 \cdots a_n$, let $f(k)$ be the minimal "remainder" that is left when $k$ is divided by each of $a_1, a_2,\ldots, a_n$, where any time $a_i \mid k$, the "remainder" when $k$ is divided by $a_i$ is $a_i$, not zero. Furthermore, let $S$ be the set of positive integers at most $a_1 \cdot a_2 \cdots a_n$ that are divisible by at least one of $a_1, a_2, \ldots, a_n$. Note that $f(k)$ is the length of the segment ending at $k$. We are asked to prove that $\sum_{k\in S} f(k)^2 \equiv 0 \pmod p$, where $f(k) \le p$ for each $k$ (as the remainder when $k$ divided by $a_1$ can't exceed $p$). For each positive integer $1 \le m < p$, we now compute the number of positive integers $k\in S$ with $f(k) = m$. Consider $k$ with $f(k) = m$. Notice that any choice of the remainders of $k$ modulo $a_1, a_2, \ldots, a_n$ gives a unique value of $k$. Fix some $k$ and let the "remainder" of $k$ divided by $a_i$ be $r_i$ (where $r_i = a_i$ if $a_i\mid k$). The statement $f(k) = m$ and $k\in S$ is equivalent to $r_i \ge m$ for each $i$, there exists some $i$ with $r_i = a_i$, and there exists some $i$ with $r_i = m$ (since $a_1 > m$, these two $i$'s cannot overlap). Firstly, the number of $(r_i)$ with only the condition that $r_i \ge m$ is $\prod_{i=1}^n (a_i - (m-1))$. The number of $(r_i)$ with $r_i \ge m$ and $r_i < a_i$ for all $i$ is $\prod_{i=1}^n (a_i - m)$. The number of $(r_i)$ with $r_i > m$ for all $i$ is also $\prod_{i=1}^n (a_i - m)$. The number of $(r_i)$ with $r_i > m$ and $r_i < a_i$ for all $i$ is $\prod_{i=1}^n (a_i - (m + 1))$. Hence, we see that the number of $(r_i)$ with $r_i \ge m$ for all $i$ not satisfying our conditions is $2 \prod_{i=1}^n (a_i - m) - \prod_{i=1}^n (a_i - (m+1))$, hence the number of $(r_i)$ satisfying our conditions is\[ Y(m) = \prod_{i=1}^n (a_i - (m-1)) - 2\prod_{i=1}^n (a_i - m) + \prod_{i=1}^n (a_i - (m+1)) \]Since a sequence $(r_i)$ uniquely determines $k$, that is also the number of $k$ with $f(k) = m$. Let $S(t)$ denote the symmetric sum defined by the sum of all products of $t$ distinct numbers in $\{a_1, a_2, \ldots, a_n\}$ and $g(m) = \prod_{i=1}^n (a_i - m)$. We have that $\prod_{i=1}^n (a_i - b) = \sum_{u=0}^n S(u) \cdot (-b)^{n - u}$ and\[ Y(m) = g(m-1) - 2g(m) + g(m+1)\]Notice that if $f(k) = p$, then $f(k)^2\equiv 0\pmod p$ so\[ \sum_{k\in S} f(k)^2 \equiv \sum_{m=1}^{p-1} m^2 \cdot Y(m) = \sum_{m=1}^{p-1} (m^2 g(m-1) - 2m^2 g(m) + m^2 g(m+1)) \pmod p \]We can in fact change the endpoints of the sum to $0$ and $p$ as $p\mid m^2 g(m-1) - 2m^2 g(m) + m^2 g(m+1)$ for $m \in \{0,p\}$. Summing the above equation over all $0\le m\le p$ gives\[ \sum_{k\in S} f(k)^2 \equiv g(0) + 2(g(1) + g(2) + \cdots + g(p-1) ) + g(p) \]since $(m+1)^2 - 2m^2 + (m-1)^2 = 2$. We have that $g(b) = \sum_{u=0}^n S(u) \cdot (-b)^{n - u}$ and 'therefore $g(0) = g(p) \equiv S(n) \equiv 0 \pmod p$ (since $a_1 \mid S(n)$). Now notice that\[ \sum_{b=1}^{p-1} g(b) = \sum_{u=0}^n S(u)\left ( \sum_{b=1}^{p-1} (-b)^{n-u} \right) \equiv \sum_{u=0}^n S(u) \left( \sum_{b=1}^{p-1} b^{n-u} \right) \pmod p \]It's well known that for each positive integer $k$ and prime $p$ with $p-1\nmid k $ that\[ \sum_{i=1}^{p-1} i^k \equiv 0\pmod p \]Since any positive integer $k \le n$ satisfies $p-1 \nmid k$ as $p-1 \ge n + 1 > k$. Hence for each $u < n$, $ \sum_{b=1}^{p-1} b^{n-u} \equiv 0\pmod p$. Hence the equation above becomes\[ \sum_{b=1}^{p-1} g(b) \equiv \sum_{u=0}^{n-1} S(u) \cdot 0 + S(n) \left( \sum_{b=1}^{p-1} b^0 \right) \pmod p \equiv 0\pmod p\]since $S(n) \equiv 0\pmod p$. Hence\[ \sum_{k\in S} f(k)^2 \equiv g(0) + 2\sum_{b=1}^{p-1} g(b) + g(p) \equiv 0 + 2\cdot 0 + 0 \equiv 0\pmod p,\]as desired.

By the Chinese Remainder Theorem, we can represent each element of the interval \([0, a_1a_2\cdots a_n - 1]\) as a vector \((r_1, r_2, \ldots, r_n)\), where \(0 \leq r_i \leq a_i - 1\) for all \(i = 1, 2, \ldots, n\). For each \(d\), with \(1 \leq d \leq a_1\), the number of intervals of length at least \(d\) will be \(P(d-1) - P(d)\), where \[ P(X) := (a_1 - X)(a_2 - X)\cdots (a_n - X). \]This follows from the fact that we have \(P(d-1)\) ways to choose the residues such that \(0 \leq r_i \leq a_i - d\) to get numbers suitable as the left endpoint of each interval. Furthermore, we need to exclude the \(P(d)\) numbers such that none of the residues is zero. It follows that the sum of the squares of the lengths of the intervals is \[ \sum_{i=1}^{a_1} (2i - 1)(P(i-1) - P(i)) = P(0) - (2a_1 - 1)P(a_1) + \sum_{i=1}^{a_1} 2P(i). \]Since \(P\) has degree at most \(a_1- 2\), the final expression is divisible by \(a_1\).