Shortlist 2014, N6

Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Serbia

Concepts : Théorème des restes chinois · Double comptage · Congruences, théorèmes de Fermat et d'Euler · Polynômes à coefficients entiers

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 78 (page 79 du PDF)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Let \(a_1 < a_2 < \cdots < a_n\) be pairwise coprime positive integers with \(a_1\) being prime and \(a_1 \geq 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\).

Indices : les idées clés

• Double comptage avec des poids : un segment de longueur \(\ell\) contient \(\ell - d + 1\) sous-intervalles de longueur \(d\), et avec les poids \(w(1) = 1\), \(w(d) = 2\) sinon, leur somme vaut \(\ell^2\).
• Restes chinois : le nombre d'intervalles \([x, x + d]\) sans point marqué à l'intérieur est \(f(d) = (a_1 + 1 - d) \cdots (a_n + 1 - d)\), un polynôme de degré \(n \leq a_1 - 2\).
• Sommes de puissances modulo \(p\) : pour un polynôme à coefficients entiers \(F\) de degré au plus \(p - 2\), \(\sum_{x=1}^{p} F(x) \equiv 0 \pmod p\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2014 (deux solutions et deux remarques).

Solution 1

Posons \(A = a_1 \cdots a_n\). Dans toute la solution, les intervalles sont non vides et à extrémités entières, et l'on note \(\lvert X \rvert\) la longueur d'un intervalle \(X\).

Définissons les deux familles d'intervalles suivantes :

\[\mathcal{S} = \{[x, y] : x < y \text{ sont deux points marqués consécutifs}\},\]

\[\mathcal{T} = \{[x, y] : x < y \text{ entiers}, \; 0 \leq x \leq A - 1, \text{ aucun point marqué dans } (x, y)\}.\]

On veut calculer \(\sum_{X \in \mathcal{S}} \lvert X \rvert^2\) modulo \(a_1\). Le nombre \(A\) est marqué, donc la condition \(y \leq A\) est automatique dans la définition de \(\mathcal{T}\).

Attribuons aux intervalles de \(\mathcal{T}\) des poids qui ne dépendent que de leur longueur : le poids d'un intervalle \(Y \in \mathcal{T}\) est \(w(\lvert Y \rvert)\), où

\[w(k) = \begin{cases} 1 & \text{si } k = 1, \\ 2 & \text{si } k \geq 2. \end{cases}\]

Considérons un intervalle \(X \in \mathcal{S}\) et ses sous-intervalles \(Y \in \mathcal{T}\). Clairement, \(X\) a un sous-intervalle de longueur \(\lvert X \rvert\), deux de longueur \(\lvert X \rvert - 1\), et ainsi de suite : en général, \(X\) a \(\lvert X \rvert - d + 1\) sous-intervalles de longueur \(d\) pour tout \(d = 1, 2, \ldots, \lvert X \rvert\). La somme des poids des sous-intervalles de \(X\) vaut

\[\sum_{Y \in \mathcal{T}, \, Y \subseteq X} w(\lvert Y \rvert) = \sum_{d=1}^{\lvert X \rvert} (\lvert X \rvert - d + 1) \cdot w(d) = \lvert X \rvert \cdot 1 + \big((\lvert X \rvert - 1) + (\lvert X \rvert - 2) + \cdots + 1\big) \cdot 2 = \lvert X \rvert^2.\]

Comme les intervalles de \(\mathcal{S}\) ne se chevauchent pas, chaque intervalle \(Y \in \mathcal{T}\) est contenu dans un seul intervalle \(X \in \mathcal{S}\). Donc, par double comptage,

\[\sum_{X \in \mathcal{S}} \lvert X \rvert^2 = \sum_{X \in \mathcal{S}} \Bigg(\sum_{Y \in \mathcal{T}, \, Y \subseteq X} w(\lvert Y \rvert)\Bigg) = \sum_{Y \in \mathcal{T}} w(\lvert Y \rvert). \tag{1}\]

Pour chaque \(d = 1, 2, \ldots, a_1\), comptons les intervalles de \(\mathcal{T}\) de longueur \(d\). Les multiples de \(a_1\) sont tous marqués, donc les longueurs des intervalles de \(\mathcal{S}\) et \(\mathcal{T}\) ne dépassent pas \(a_1\). Soit \(x\) un entier avec \(0 \leq x \leq A - 1\), et considérons l'intervalle \([x, x + d]\). Soient \(r_1, \ldots, r_n\) les restes de \(x\) modulo \(a_1, \ldots, a_n\). Comme \(a_1, \ldots, a_n\) sont deux à deux premiers entre eux, le nombre \(x\) est déterminé de façon unique par la suite \((r_1, \ldots, r_n)\), par le théorème des restes chinois.

Pour chaque \(i = 1, \ldots, n\), la propriété « l'intervalle \((x, x + d)\) ne contient aucun multiple de \(a_i\) » équivaut à \(r_i + d \leq a_i\), c'est-à-dire \(r_i \in \{0, 1, \ldots, a_i - d\}\) : il y a \(a_i - d + 1\) choix pour chaque \(r_i\). Le nombre de suites de restes \((r_1, \ldots, r_n)\) telles que \([x, x + d] \in \mathcal{T}\) est donc exactement \((a_1 + 1 - d) \cdots (a_n + 1 - d)\) ; notons ce produit \(f(d)\).

On peut maintenant regrouper la dernière somme de (1) selon la longueur des intervalles. Pour tout \(d = 1, \ldots, a_1\), il y a \(f(d)\) intervalles \(Y \in \mathcal{T}\) de longueur \(d\). Donc (1) se poursuit en

\[\sum_{X \in \mathcal{S}} \lvert X \rvert^2 = \sum_{Y \in \mathcal{T}} w(\lvert Y \rvert) = \sum_{d=1}^{a_1} f(d) \cdot w(d) = 2 \sum_{d=1}^{a_1} f(d) - f(1). \tag{2}\]

On termine avec le fait classique suivant.

Lemme. Si \(p\) est premier et \(F\) un polynôme à coefficients entiers de degré au plus \(p - 2\), alors \(\sum_{x=1}^{p} F(x)\) est divisible par \(p\).

Preuve. Il suffit évidemment de prouver le lemme pour les monômes \(x^k\) avec \(k \leq p - 2\). Procédons par récurrence sur \(k\). Si \(k = 0\), alors \(F = 1\) et c'est évident.

Soit \(1 \leq k \leq p - 2\), et supposons le lemme prouvé pour les degrés inférieurs. Alors

\[\begin{aligned} 0 \equiv p^{k+1} &= \sum_{x=1}^{p} \big(x^{k+1} - (x - 1)^{k+1}\big) = \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}\]

Comme \(0 < k + 1 < p\), cela prouve \(\sum_{x=1}^{p} x^k \equiv 0 \pmod p\). \(\square\)

Dans (2), en appliquant le lemme au polynôme \(f\) (de degré \(n \leq a_1 - 2\)) et au nombre premier \(a_1\), on obtient que \(\sum_{d=1}^{a_1} f(d)\) est divisible par \(a_1\). Le terme \(f(1) = a_1 \cdots a_n\) est lui aussi divisible par \(a_1\) ; ces deux faits prouvent que \(\sum_{X \in \mathcal{S}} \lvert X \rvert^2\) est divisible par \(a_1\). \(\blacksquare\)

Remarque 1. Avec des poids bien choisis, la même méthode permet de calculer d'autres expressions des longueurs des segments. Par exemple, \(w(1) = 1\) et \(w(k) = 6(k - 1)\) pour \(k \geq 2\) permettent de calculer \(\sum_{X \in \mathcal{S}} \lvert X \rvert^3\) et de prouver que cette somme est divisible par \(a_1\) si \(a_1\) est un nombre premier avec \(a_1 \geq n + 3\). Voir aussi la remarque 2 après la seconde solution.

Solution 2

Les conventions du premier paragraphe de la solution 1 restent en vigueur. On prouve l'énoncé plus général suivant.

\((\oplus)\) Soit \(p\) un nombre premier, \(p = a_1 < a_2 < \cdots < a_n\) des entiers strictement positifs deux à deux premiers entre eux, et \(d\) un entier avec \(1 \leq d \leq p - n\). On marque, sur l'intervalle \(I = [0, a_1 a_2 \cdots a_n]\), tous les entiers divisibles par au moins l'un des nombres \(a_1, \ldots, a_n\). Ces points découpent \(I\) en segments, de longueurs \(b_1, \ldots, b_k\). Alors la somme \(\sum_{i=1}^{k} \binom{b_i}{d}\) est divisible par \(p\).

En appliquant \((\oplus)\) à \(d = 1\) et \(d = 2\), et avec l'égalité \(x^2 = 2\binom{x}{2} + \binom{x}{1}\), on obtient facilement l'énoncé du problème.

Prouvons \((\oplus)\) par récurrence sur \(n\). Le cas \(n = 1\) découle du fait connu que le coefficient binomial \(\binom{p}{d}\) est divisible par \(p\) pour \(1 \leq d \leq p - 1\).

Supposons maintenant \(n \geq 2\), et l'énoncé connu pour \(n - 1\) entiers premiers entre eux et tout entier \(d \in [1, p - n + 1]\). Soient \(p = a_1 < a_2 < \cdots < a_n\) et \(d\) comme ci-dessus. Posons \(A' = \prod_{i=1}^{n-1} a_i\) et \(A = A' a_n\). Colorions en vert les points de l'axe divisibles par l'un des nombres \(a_1, \ldots, a_{n-1}\), et en rouge ceux divisibles par \(a_n\). Les points verts découpent \([0, A']\) en sous-intervalles \(J_1, J_2, \ldots, J_\ell\).

Pour translater les intervalles, on note \([a, b] + m = [a + m, b + m]\) pour \(a, b, m \in \mathbb{Z}\). Pour chaque \(i \in \{1, 2, \ldots, \ell\}\), soit \(\mathcal{F}_i\) la famille des intervalles obtenus en découpant les intervalles \(J_i, J_i + A', \ldots, J_i + (a_n - 1)A'\) par les points rouges. Il s'agit de prouver que

\[\sum_{i=1}^{\ell} \sum_{X \in \mathcal{F}_i} \binom{\lvert X \rvert}{d}\]

est divisible par \(p\).

Fixons un indice \(i\) avec \(1 \leq i \leq \ell\). Comme \(A'\) et \(a_n\) sont premiers entre eux, les nombres \(0, A', \ldots, (a_n - 1)A'\) forment un système complet de résidus modulo \(a_n\). De plus, \(\lvert J_i \rvert \leq p < a_n\), car en particulier tous les multiples de \(p\) sont verts. Chacun des intervalles \(J_i, J_i + A', \ldots, J_i + (a_n - 1)A'\) contient donc au plus un point rouge. Plus précisément, pour chaque \(j \in \{1, \ldots, \lvert J_i \rvert - 1\}\), un seul de ces intervalles contient un point rouge qui le découpe en un intervalle de longueur \(j\) suivi d'un intervalle de longueur \(\lvert J_i \rvert - j\), et les \(a_n - \lvert J_i \rvert + 1\) autres intervalles n'ont pas de point rouge à l'intérieur. Pour ces raisons, et par la formule de sommation des coefficients binomiaux,

\[\begin{aligned} \sum_{X \in \mathcal{F}_i} \binom{\lvert X \rvert}{d} &= 2\left(\binom{1}{d} + \cdots + \binom{\lvert J_i \rvert - 1}{d}\right) + (a_n - \lvert J_i \rvert + 1)\binom{\lvert J_i \rvert}{d} \\ &= 2\binom{\lvert J_i \rvert}{d + 1} + (a_n - d + 1)\binom{\lvert J_i \rvert}{d} - (d + 1)\binom{\lvert J_i \rvert}{d + 1} \\ &= (1 - d)\binom{\lvert J_i \rvert}{d + 1} + (a_n - d + 1)\binom{\lvert J_i \rvert}{d}. \end{aligned}\]

Il reste donc à prouver que

\[(1 - d)\sum_{i=1}^{\ell} \binom{\lvert J_i \rvert}{d + 1} + (a_n - d + 1)\sum_{i=1}^{\ell} \binom{\lvert J_i \rvert}{d}\]

est divisible par \(p\). Or, par l'hypothèse de récurrence, chacun des deux termes est même divisible par \(p\), puisque \(1 \leq d < d + 1 \leq p - (n - 1)\). Cela achève la preuve de \((\oplus)\), et donc la solution. \(\blacksquare\)

Remarque 2. On peut aussi prouver \((\oplus)\) par la méthode de la première solution, avec les poids \(w(x) = \binom{x - 2}{d - 2}\).