Shortlist 2025, N1

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

Concepts : Congruences, théorèmes de Fermat et d'Euler · Principe des tiroirs

Solution officielle : Shortlist officielle 2025 (avec solutions), section N1 (livret PDF)

Énoncé

Let \(n\) and \(k\) be positive integers such that \(n < k < 2n\). Suppose \(a_1, a_2, \ldots, a_k\) are positive integers such that \(2^{a_1} + 2^{a_2} + \cdots + 2^{a_k}\) is divisible by \(2^n - 1\).

Show that at least three of \(a_1, a_2, \ldots, a_k\) have the same remainder when divided by \(n\).

Indices : les idées clés

• Congruences : \(2^{a+n} \equiv 2^a \pmod{2^n - 1}\), donc seuls les restes des \(a_j\) modulo \(n\) comptent, et \(2^0, \ldots, 2^{n-1}\) sont distincts modulo \(2^n - 1\).
• Encadrement : si aucun reste n'apparaît trois fois, la somme est comprise strictement entre \(0\) et \(2(2^n - 1)\), donc égale à \(2^n - 1\).
• Écriture en base 2 : \(c_0 + 2c_1 + \cdots + 2^{n-1}c_{n-1} = 2^n - 1\) avec \(c_i \leq 2\) force \(c_i = 1\) pour tout \(i\), donc \(k = n\).
• Principe des tiroirs (solution 3) : en faisant tourner les restes, la somme des \(n\) valeurs \(f(t)\) vaut \(k(2^n - 1) < 2n(2^n - 1)\), donc l'une d'elles vaut exactement \(2^n - 1\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (trois solutions et une remarque).

Solution 1

Comme \(2^{a+n} \equiv 2^a \pmod{2^n - 1}\) (congruences), les hypothèses et la conclusion du problème sont inchangées si l'on remplace chaque \(a_j\) par un autre entier positif ou nul congru à \(a_j\) modulo \(n\). On peut donc supposer que chaque \(a_j\) appartient à \(\{0, 1, \ldots, n-1\}\), et il suffit de montrer que trois des \(a_j\) sont égaux.

Supposons par l'absurde que trois des \(a_1, \ldots, a_k\) ne soient jamais égaux. Alors

\[0 < 2^{a_1} + 2^{a_2} + \cdots + 2^{a_k} \leq 2(1 + 2 + \cdots + 2^{n-1}) = 2(2^n - 1). \tag{1}\]

Si la seconde inégalité était une égalité, chaque élément de \(\{0, \ldots, n-1\}\) apparaîtrait deux fois parmi \(a_1, \ldots, a_k\), ce qui contredit \(k < 2n\). Les deux inégalités de (1) sont donc strictes. Comme \(2^n - 1\) divise \(2^{a_1} + \cdots + 2^{a_k}\), on a alors

\[2^{a_1} + 2^{a_2} + \cdots + 2^{a_k} = 2^n - 1. \tag{2}\]

Pour \(i \in \{0, \ldots, n-1\}\), notons \(c_i\) le nombre de \(a_j\) égaux à \(i\). Alors \(c_0 + \cdots + c_{n-1} = k\), et par hypothèse tous les \(c_i\) sont \(\leq 2\). L'équation (2) devient

\[c_0 2^0 + c_1 2^1 + \cdots + c_{n-1} 2^{n-1} = 2^n - 1. \tag{3}\]

Montrons par récurrence forte que \(c_i = 1\) pour tout \(i\). Comme \(2^n - 1\) est impair, l'équation (3) modulo \(2\) montre que \(c_0\) est impair ; comme \(0 \leq c_0 \leq 2\), \(c_0 = 1\). Supposons \(c_0 = \cdots = c_{s-1} = 1\) pour un certain \(1 \leq s \leq n-1\). Les \(s\) premiers termes de (3) ont pour somme \(2^s - 1\), et la réduction modulo \(2^{s+1}\) donne

\[2^s - 1 + c_s 2^s \equiv -1 \pmod{2^{s+1}}, \quad \text{donc} \quad 2^{s+1} \mid 2^s(1 + c_s).\]

Ainsi \(c_s\) est impair, et comme \(0 \leq c_s \leq 2\), \(c_s = 1\). Par récurrence, tous les \(c_i\) valent \(1\).

Par conséquent, chaque \(i \in \{0, \ldots, n-1\}\) est égal à exactement un des \(a_j\), et \(k = c_0 + \cdots + c_{n-1} = n\), ce qui contredit \(k > n\). Donc trois des \(a_1, \ldots, a_k\) sont égaux, c'est-à-dire que trois des \(a_j\) initiaux ont le même reste modulo \(n\). \(\blacksquare\)

Solution 2

Remarquons d'abord que, pour des entiers \(a, b \geq 0\), on a \(2^a \equiv 2^b \pmod{2^n - 1}\) si et seulement si \(a \equiv b \pmod n\). En effet, si \(a = jn + b\) avec \(j \in \mathbb{Z}\), alors \(2^a = (2^n)^j \cdot 2^b \equiv 2^b \pmod{2^n - 1}\) ; et \(2^0, 2^1, \ldots, 2^{n-1}\) sont distincts modulo \(2^n - 1\).

Supposons par l'absurde que, pour chaque \(i \in \{0, \ldots, n-1\}\), il y ait au plus deux indices \(j\) tels que \(a_j \equiv i \pmod n\). Pour \(r = 0, 1, 2\), notons \(B_r\) l'ensemble des \(i \in \{0, \ldots, n-1\}\) tels qu'exactement \(r\) des \(a_j\) vérifient \(a_j \equiv i \pmod n\) (ou, de façon équivalente, \(2^{a_j} \equiv 2^i \pmod{2^n - 1}\)), et \(b_r = |B_r|\).

Les \(B_r\) forment une partition de \(\{0, \ldots, n-1\}\), donc \(b_0 + b_1 + b_2 = n\). Chaque \(a_j\) est compté dans exactement un \(B_r\), et \(B_r\) compte \(r b_r\) des \(a_j\), donc \(b_1 + 2b_2 = k\). En soustrayant, \(b_2 - b_0 = k - n\), donc d'après les hypothèses, \(0 < b_2 - b_0 < n\).

La condition \(2^{a_1} + \cdots + 2^{a_k} \equiv 0 \pmod{2^n - 1}\) équivaut alors à

\[\sum_{i \in B_1} 2^i + \sum_{i \in B_2} 2 \cdot 2^i \equiv 0 \pmod{2^n - 1}. \tag{4}\]

D'autre part, comme les \(B_r\) forment une partition de \(\{0, \ldots, n-1\}\),

\[\sum_{i \in B_0} 2^i + \sum_{i \in B_1} 2^i + \sum_{i \in B_2} 2^i = 2^0 + \cdots + 2^{n-1} \equiv 0 \pmod{2^n - 1}. \tag{5}\]

En soustrayant (4) de (5), on obtient

\[\sum_{i \in B_0} 2^i \equiv \sum_{i \in B_2} 2^i \pmod{2^n - 1}. \tag{6}\]

Comme \(B_0\) et \(B_2\) sont des parties de \(\{0, \ldots, n-1\}\), chacune des deux sommes de (6) est comprise entre \(0\) et \(2^0 + \cdots + 2^{n-1} = 2^n - 1\). Les deux sommes sont donc égales, ou bien valent \(0\) et \(2^n - 1\) dans un certain ordre.

Si l'une vaut \(0\) et l'autre \(2^n - 1\), alors \(B_0\) et \(B_2\) sont \(\varnothing\) et \(\{0, \ldots, n-1\}\) dans un certain ordre, donc \(b_2 - b_0 = \pm n\), ce qui contredit \(0 < b_2 - b_0 < n\). Les deux sommes sont donc égales. Elles fournissent alors deux écritures en base 2 du même entier, donc \(B_0 = B_2\). Comme \(B_0\) et \(B_2\) sont disjoints, ils sont vides, d'où \(b_0 = b_2 = 0\), ce qui contredit \(b_2 - b_0 > 0\).

Donc trois des \(a_1, \ldots, a_k\) sont congrus modulo \(n\). \(\blacksquare\)

Solution 3

Notons \(\langle a \rangle_n\) le reste de la division de \(a\) par \(n\), c'est-à-dire l'élément de \(\{0, \ldots, n-1\}\) congru à \(a\) modulo \(n\). Comme dans la solution 2, \(2^a \equiv 2^b \pmod{2^n - 1}\) si et seulement si \(a \equiv b \pmod n\) ; en particulier \(2^{\langle a \rangle_n} \equiv 2^a \pmod{2^n - 1}\).

Pour un entier \(t \geq 0\), posons

\[f(t) = 2^{\langle a_1 + t \rangle_n} + 2^{\langle a_2 + t \rangle_n} + \cdots + 2^{\langle a_k + t \rangle_n},\]

de sorte que \(f(t) \equiv 2^t(2^{a_1} + \cdots + 2^{a_k}) \equiv 0 \pmod{2^n - 1}\). Quand \(t\) parcourt \(\{0, 1, \ldots, n-1\}\), \(\langle a_i + t \rangle_n\) parcourt ce même ensemble, donc

\[\sum_{t=0}^{n-1} 2^{\langle a_i + t \rangle_n} = 2^0 + 2^1 + \cdots + 2^{n-1} = 2^n - 1.\]

On a donc

\[\sum_{t=0}^{n-1} f(t) = \sum_{t=0}^{n-1} \left( 2^{\langle a_1 + t \rangle_n} + \cdots + 2^{\langle a_k + t \rangle_n} \right) = k(2^n - 1).\]

Chaque \(f(t)\) est un multiple strictement positif de \(2^n - 1\), et \(k < 2n\) : par le principe des tiroirs, il existe \(t \in \{0, \ldots, n-1\}\) tel que \(f(t) = 2^n - 1\) (sinon la somme serait au moins \(2n(2^n - 1)\)). Pour ce \(t\) et pour chaque \(i \in \{0, \ldots, n-1\}\), notons \(c_i\) le nombre de \(a_j\) tels que \(\langle a_j + t \rangle_n = i\). Alors \(c_0 + \cdots + c_{n-1} = k\) et

\[f(t) = c_0 2^0 + c_1 2^1 + \cdots + c_{n-1} 2^{n-1} = 2^n - 1. \tag{7}\]

On conclut alors comme dans la solution 1 : si tous les \(c_i\) étaient \(\leq 2\) (c'est-à-dire si aucun reste modulo \(n\) n'apparaissait trois fois parmi les \(a_j\)), la récurrence de la solution 1 donnerait \(c_i = 1\) pour tout \(i\), donc \(k = n\), contradiction. \(\blacksquare\)

Remarques

Remarque 1. Dans la solution 1, la récurrence forte peut aussi se faire en retranchant les \(s\) premiers termes du membre de gauche de (3) puis en divisant par \(2^s\). Ces \(s\) termes ont pour somme \(2^s - 1\), ce qui donne

\[c_s + c_{s+1} 2^1 + \cdots + c_{n-1} 2^{n-s-1} = 2^{n-s} - 1.\]

Comme \(n - s \geq 1\), le membre de droite est impair ; en raisonnant modulo \(2\), on obtient \(c_s = 1\).