Shortlist 2023, N1¶

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

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Récurrence et constructions récursives · Valuations p-adiques et lemme LTE

Solution officielle : Shortlist officielle 2023 (avec solutions), p. 81 (page 83 du PDF)

Problème 1 de l'OIM 2023

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2023, où il était le problème 1 (jour 1).

Énoncé¶

Determine all positive, composite integers \(n\) that satisfy the following property: if the positive divisors of \(n\) are \(1 = d_1 < d_2 < \cdots < d_k = n\), then \(d_i\) divides \(d_{i+1} + d_{i+2}\) for every \(1 \leq i \leq k - 2\).

Indices : les idées clés

Diviseurs complémentaires : \(d_i \, d_{k+1-i} = n\), ce qui permet de lire la condition « par le haut » sur les grands diviseurs.
Divisibilité, PGCD et algorithme d'Euclide : \(\gcd(p, p+1) = 1\) (solution 1), et la chaîne \(d_i \mid d_{i+1}\) (solutions 2 et 3).
Récurrence sur l'indice \(i\) (solutions 2 et 3) : on propage \(p \mid d_i\) ou \(d_i \mid d_{i+1}\) de proche en proche.
Valuations p-adiques (solution 4) : comparer \(v_p\) des deux membres donne la contradiction.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2023 (quatre solutions).

Réponse. Les entiers cherchés sont exactement les puissances de nombres premiers \(n = p^r\) avec \(r \geq 2\).

Solution 1¶

Les puissances de premiers conviennent. Si \(n = p^r\) avec \(r \geq 2\), les diviseurs sont \(d_i = p^{i-1}\) pour \(1 \leq i \leq k = r+1\), et clairement \(p^{i-1} \mid p^i + p^{i+1}\).

Le livret écrit « \(1 \geq i \geq k\) » ; il faut lire \(1 \leq i \leq k\).

Ce sont les seules. Supposons que \(n\) vérifie la condition et possède deux diviseurs premiers distincts. Soient \(p < q\) les deux plus petits diviseurs premiers de \(n\). Il existe un entier \(j \geq 1\) tel que

\[d_1 = 1,\ d_2 = p,\ \ldots,\ d_j = p^{j-1},\ d_{j+1} = p^j,\ d_{j+2} = q.\]

Comme \(d_i \, d_{k+1-i} = n\), les plus grands diviseurs sont

\[d_{k-j-1} = \frac{n}{q},\quad d_{k-j} = \frac{n}{p^j},\quad d_{k-j+1} = \frac{n}{p^{j-1}},\quad \ldots,\quad d_{k-1} = \frac{n}{p},\quad d_k = n.\]

La condition appliquée à \(i = k-j-1\) donne

\[\frac{n}{q} \;\Big|\; d_{k-j} + d_{k-j+1} = \frac{n}{p^j} + \frac{n}{p^{j-1}} = \frac{n}{p^j}(p+1). \tag{1}\]

En multipliant par \(\frac{p^j q}{n}\), on obtient \(p^j \mid q(p+1)\), donc \(p \mid q(p+1)\). C'est absurde, car \(\gcd(p, p+1) = 1\) et \(p \neq q\) sont premiers. \(\blacksquare\)

Solution 2¶

Comme \(d_i \, d_{k+1-i} = n\), on a l'équivalence

\[d_{k-i-1} \mid d_{k-i} + d_{k-i+1} \iff \frac{n}{d_{i+2}} \;\Big|\; \frac{n}{d_{i+1}} + \frac{n}{d_i}.\]

En multipliant par \(d_i d_{i+1} d_{i+2}\) et en simplifiant par \(n\), on obtient \(d_i d_{i+1} \mid d_i d_{i+2} + d_{i+1} d_{i+2}\), d'où

\[d_i \mid d_{i+1} d_{i+2}. \tag{2}\]

Par ailleurs, la condition de l'énoncé donne \(d_i \mid d_{i+1}(d_{i+1} + d_{i+2}) = d_{i+1}^2 + d_{i+1} d_{i+2}\). Avec (2), on obtient

\[d_i \mid d_{i+1}^2 \quad \text{pour tout } 1 \leq i \leq k-2.\]

Soit \(d_2 = p\) le plus petit diviseur premier de \(n\). Montrons par récurrence que \(p \mid d_i\) pour \(2 \leq i \leq k-1\). C'est clair pour \(i = 2\). Si \(p \mid d_j\) avec \(2 \leq j \leq k-2\), alors \(p \mid d_j \mid d_{j+1}^2\), donc \(p \mid d_{j+1}\) car \(p\) est premier.

Ainsi \(n\) est une puissance de \(p\) : sinon un autre premier \(q\) diviserait \(n\), serait l'un des \(d_i\) avec \(i \leq k-1\), et l'on aurait \(p \mid q\), ce qui est absurde. Enfin, les puissances de premiers conviennent (solution 1). \(\blacksquare\)

Solution 3¶

Affirmation. \(d_i \mid d_{i+1}\) pour tout \(1 \leq i \leq k-1\).

Preuve. Par récurrence sur \(i\) ; c'est évident pour \(i = 1\) car \(d_1 = 1\). Soit \(2 \leq i \leq k-1\), et supposons \(d_{i-1} \mid d_i\). Comme \(d_{i-1} \mid d_i + d_{i+1}\) (condition de l'énoncé), on obtient \(d_{i-1} \mid d_{i+1}\).

Considérons les diviseurs \(d_{k-i} = \frac{n}{d_{i+1}}\), \(d_{k-i+1} = \frac{n}{d_i}\), \(d_{k-i+2} = \frac{n}{d_{i-1}}\). D'après la condition de l'énoncé,

\[\frac{d_{k-i+1} + d_{k-i+2}}{d_{k-i}} = \frac{\frac{n}{d_i} + \frac{n}{d_{i-1}}}{\frac{n}{d_{i+1}}} = \frac{d_{i+1}}{d_i} + \frac{d_{i+1}}{d_{i-1}}\]

est un entier. Comme \(\frac{d_{i+1}}{d_{i-1}}\) est un entier, \(\frac{d_{i+1}}{d_i}\) aussi, c'est-à-dire \(d_i \mid d_{i+1}\). \(\square\)

D'après l'affirmation, \(n\) ne peut pas avoir deux diviseurs premiers distincts : le plus petit diviserait l'autre. Donc \(n\) est une puissance d'un nombre premier, et ces nombres conviennent (solution 1). \(\blacksquare\)

Solution 4¶

Voici une fin plus technique de la solution 1, à partir de (1). Notons \(v_p(m)\) la valuation \(p\)-adique de \(m\). Comme \(\gcd(p, q) = 1\), on a \(v_p(n/q) = v_p(n)\) ; comme \(\gcd(p, p+1) = 1\),

\[v_p\!\left(\frac{n}{p^j}(p+1)\right) = v_p(n) - j.\]

Mais (1) impose

\[v_p(n) = v_p(n/q) \leq v_p\!\left(\frac{n}{p^j}(p+1)\right) = v_p(n) - j,\]

ce qui est absurde puisque \(j \geq 1\). Donc \(n\) n'a qu'un seul diviseur premier. \(\blacksquare\)