Shortlist 2021, N3

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

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Équations diophantiennes : factorisation et encadrement

Solution officielle : Shortlist officielle 2021 (avec solutions), p. 70 (page 70 du PDF)

Énoncé

Find all positive integers \(n\) with the following property: the \(k\) positive divisors of \(n\) have a permutation \((d_1, d_2, \ldots, d_k)\) such that for every \(i = 1, 2, \ldots, k\), the number \(d_1 + \cdots + d_i\) is a perfect square.

Indices : les idées clés

• Différence de carrés : en notant \(d_1 + \cdots + d_i = s_i^2\), on a \(d_i = (s_i - s_{i-1})(s_i + s_{i-1}) \geq 2i - 1\).
• Divisibilité : le facteur \(s_{i+1} + i\) est lui-même un diviseur de \(n\), donc apparaît dans la liste, ce qui le place à un rang précis ; à la fin, \(n - 2 \mid 2\).
• Équations diophantiennes : la factorisation et l'encadrement forcent, par récurrence, \(s_i = i\) et \(d_i = 2i - 1\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (une solution).

Réponse : \(n = 1\) et \(n = 3\).

Solution

Pour \(i = 1, 2, \ldots, k\), posons \(d_1 + \cdots + d_i = s_i^2\) (avec \(s_i > 0\)), et \(s_0 = 0\). Évidemment \(0 = s_0 < s_1 < s_2 < \cdots < s_k\), donc

\[s_i \geq i \quad \text{et} \quad d_i = s_i^2 - s_{i-1}^2 = (s_i + s_{i-1})(s_i - s_{i-1}) \geq s_i + s_{i-1} \geq 2i - 1. \tag{1}\]

Le nombre \(1\) est l'un des diviseurs \(d_1, \ldots, d_k\), mais, comme \(d_i \geq 2i - 1\), la seule possibilité est \(d_1 = 1\).

Considérons maintenant \(d_2\) et \(s_2 \geq 2\). Par définition, \(d_2 = s_2^2 - 1 = (s_2 - 1)(s_2 + 1)\), donc \(s_2 - 1\) et \(s_2 + 1\) sont des diviseurs de \(n\). En particulier, il existe un indice \(j\) tel que \(d_j = s_2 + 1\). Or

\[s_2 + s_1 = s_2 + 1 = d_j \geq s_j + s_{j-1} ; \tag{2}\]

comme la suite \(s_0 < s_1 < \cdots < s_k\) est croissante, l'indice \(j\) ne peut pas dépasser \(2\). Donc les diviseurs \(s_2 - 1\) et \(s_2 + 1\) figurent parmi \(d_1\) et \(d_2\). Ainsi \(s_2 - 1 = d_1 = 1\) et \(s_2 + 1 = d_2\) ; donc \(s_2 = 2\) et \(d_2 = 3\).

On peut répéter ce procédé en général.

Affirmation. \(d_i = 2i - 1\) et \(s_i = i\) pour \(i = 1, 2, \ldots, k\).

Preuve. Par récurrence sur \(i\). C'est démontré pour \(i = 1, 2\). Supposons déjà établi \(d_1 = 1\), \(d_2 = 3\), ..., \(d_i = 2i - 1\) (donc \(s_i = i\)), et considérons le diviseur suivant :

\[d_{i+1} = s_{i+1}^2 - s_i^2 = s_{i+1}^2 - i^2 = (s_{i+1} - i)(s_{i+1} + i).\]

Le nombre \(s_{i+1} + i\) est un diviseur de \(n\), donc il existe un indice \(j\) tel que \(d_j = s_{i+1} + i\). Comme pour (2), d'après (1),

\[s_{i+1} + s_i = s_{i+1} + i = d_j \geq s_j + s_{j-1} ; \tag{3}\]

la croissance de \((s_m)\) impose, avec (3), \(j \leq i + 1\). D'autre part, \(d_j = s_{i+1} + i > 2i > d_i > d_{i-1} > \cdots > d_1\), donc \(j \leq i\) est impossible. La seule possibilité est \(j = i + 1\). Ainsi

\[s_{i+1} + i = d_{i+1} = s_{i+1}^2 - i^2, \quad \text{soit} \quad s_{i+1}^2 - s_{i+1} = i(i+1).\]

En résolvant cette équation (la fonction \(x \mapsto x^2 - x\) est strictement croissante sur les entiers positifs), on obtient \(s_{i+1} = i + 1\) et \(d_{i+1} = 2i + 1\), ce qui achève la preuve. \(\square\)

Ainsi, les diviseurs positifs de \(n\) sont \(1, 3, 5, \ldots, n - 2, n\). Le plus grand diviseur est \(d_k = 2k - 1 = n\), donc \(n\) est impair. Si \(k \geq 2\), le deuxième plus grand diviseur est \(d_{k-1} = n - 2\) ; alors \(n - 2\) divise \(n = (n - 2) + 2\), donc \(n - 2\) divise \(2\). Par conséquent \(n = 1\) ou \(n = 3\).

Réciproquement, \(n = 1\) et \(n = 3\) conviennent : pour \(n = 1\), \(k = 1\) et \(d_1 = 1^2\) ; pour \(n = 3\), \(k = 2\), \(d_1 = 1^2\) et \(d_1 + d_2 = 1 + 3 = 2^2\). \(\blacksquare\)