Shortlist 2024, N1¶
Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : Ghana
Concepts : Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler · Principe extrémal
Solution officielle : Shortlist officielle 2024 (avec solutions), section N1 (livret PDF)
Énoncé¶
Find all positive integers \(n\) with the following property: for all positive divisors \(d\) of \(n\), we have that \(d + 1 \mid n\) or \(d + 1\) is prime.
Indices : les idées clés
- Divisibilité : appliquer la condition à des diviseurs bien choisis (\(m\) la partie impaire, \(2^k\), \(n\), \(\frac{n}{2}\), \(\frac{n}{4}\)...) ; si \(d + 1\) ne divise pas \(n\), il doit être premier.
- Le test « \(8 \mid n\) mais \(9 \nmid n\) » : \(8 + 1 = 9\) n'est pas premier, donc \(8 \mid n\) force \(9 \mid n\).
- Congruences modulo 3 : \(2^a + 1\) est multiple de \(3\) si \(a\) est impair ; parmi \(2m + 1\), \(4m + 1\), \(8m + 1\), l'un est multiple de \(3\) si \(3 \nmid m\).
- Principe extrémal (solutions 3 et 4) : le plus petit entier \(p\) qui ne divise pas \(n\) est premier.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (cinq solutions).
Réponse : \(n \in \{1, 2, 4, 12\}\).
On vérifie facilement que ces valeurs conviennent : pour \(n = 12\), les diviseurs \(1, 2, 3, 4, 6, 12\) donnent \(2 \mid 12\), \(3 \mid 12\), \(4 \mid 12\), \(5\) premier, \(7\) premier, \(13\) premier.
Solution 1¶
Il reste à montrer qu'il n'y a pas d'autre solution. Écrivons \(n = 2^k m\) avec \(k \geq 0\) entier et \(m\) impair. Comme \(m \mid n\), soit \(m + 1\) est premier, soit \(m + 1 \mid n\).
Premier cas : \(m + 1\) premier. Comme \(m + 1\) est pair, c'est \(2\), donc \(m = 1\) et \(n = 2^k\). Si \(k \geq 3\), on obtient une contradiction car \(8 \mid n\) mais \(9 \nmid n\) (et \(9\) n'est pas premier). Donc \(k \leq 2\) et \(n \in \{1, 2, 4\}\).
Second cas : \(m + 1 \mid n\). Comme \(m + 1 \mid 2^k m\) et que \(m + 1\) est premier avec \(m\) (divisibilité), \(m + 1 \mid 2^k\). Donc \(m + 1 = 2^j\) avec \(2 \leq j \leq k\) (le cas \(j = 1\) donne \(m = 1\), déjà traité).
Alors \(2^k + 1 \nmid n\) : étant impair, il devrait diviser \(m\), mais il est plus grand que \(m\). Par hypothèse, \(2^k + 1\) est donc premier. Si \(k = 2\), alors \(j = 2\), ce qui donne la solution \(n = 4 \cdot 3 = 12\).
Supposons \(k > 2\). Alors \(2^{k-1} + 1 \nmid n\) : étant impair, il devrait diviser \(m = 2^j - 1\), mais \(2^{k-1} + 1 \mid 2^j - 1\) est impossible pour \(j \leq k\) (le membre de gauche est plus grand que celui de droite, sauf si \(j = k\), auquel cas il en vaut un peu plus de la moitié). Comme \(2^k \mid n\), \(2^k + 1 \nmid n\), \(2^{k-1} \mid n\) et \(2^{k-1} + 1 \nmid n\), les nombres \(2^k + 1\) et \(2^{k-1} + 1\) sont tous deux premiers. Mais \(2^a + 1\) est multiple de \(3\) si \(a\) est impair ; l'un de \(k\), \(k - 1\) étant impair, on doit avoir \(2^k + 1 = 3\) (impossible, cela donne \(k = 1\)) ou \(2^{k-1} + 1 = 3\), ce qui donne \(k = 2\), contradiction.
Finalement \(n \in \{1, 2, 4, 12\}\). \(\blacksquare\)
Solution 2¶
On procède comme dans la solution 1 jusqu'à obtenir \(n = 2^k(2^j - 1)\) avec \(2 \leq j \leq k\) (les autres cas donnant \(n \in \{1, 2, 4\}\)).
On a \(2^j \mid n\) mais \(2^j + 1 \nmid n\), car il est impair et ne divise pas \(2^j - 1\). Donc \(2^j + 1\) est premier. La théorie des nombres premiers de Fermat montre que \(j = 2^h\) avec \(h > 0\).
Alors \(2^{2^h} - 1\) est congru à \(3\) ou à \(6\) modulo \(9\) selon que \(h\) est impair ou pair (en effet \(2^2 \equiv 4\), \(2^4 \equiv 7\), \(2^8 \equiv 4 \pmod 9\), et ainsi de suite en alternance). En particulier, il n'est pas divisible par \(9\), donc \(n = 2^k(2^{2^h} - 1)\) n'est pas divisible par \(9\). On doit donc avoir \(k \leq 2\), car si \(k \geq 3\) alors \(8 \mid n\) mais \(9 \nmid n\), et \(9\) n'est pas premier. Ainsi \(j = k = 2\) et \(n = 12\). \(\blacksquare\)
Solution 3¶
Soit \(p\) le plus petit entier ne divisant pas \(n\) (principe extrémal). Comme \(p - 1\) divise \(n\) et que \(p = (p - 1) + 1\) ne divise pas \(n\), \(p\) est premier. Soit \(r\), avec \(1 \leq r \leq p - 1\), le reste de \(n\) modulo \(p\). Comme \(p - r < p\), on a \(p - r \mid n\), et l'on peut considérer le diviseur \(d = \frac{n}{p - r}\).
Comme \(p \mid n - r\), on a \(p \mid n + p - r = (p - r)(d + 1)\), et \(p\) ne divise pas \(p - r\), donc \(p \mid d + 1\). Par suite \(d + 1 \nmid n\), donc \(d + 1\) est premier. Étant divisible par \(p\), il vaut \(p\) : \(d + 1 = p\), c'est-à-dire
Ensuite, \(p - 2\) et \(p - 3\) divisent \(n\) ; comme ils sont premiers avec \(p - 1\) à un facteur \(2\) près, on obtient \((p - 2)(p - 3) \mid 2(p - r)\), d'où
Cette inéquation du second degré, \(p^2 - 7p + 8 \leq 0\), donne \(p \leq 5\), donc \(n = (p-1)(p-r) \in \{1, 2, 4, 8, 12, 16\}\). Parmi ces valeurs, \(n = 8\) et \(n = 16\) ne conviennent pas (\(8 \mid n\) mais \(9 \nmid n\)). \(\blacksquare\)
Solution 4¶
Supposons que \(n\) n'est ni \(1\) ni \(2\).
Comme \(n \mid n\) et \(n + 1 \nmid n\), \(n + 1\) est premier, donc impair, et \(2 \mid n\). Comme \(n > 2\), on a \(\frac{n}{2} \mid n\) et \(\frac{n}{2} + 1 \nmid n\), donc \(\frac{n}{2} + 1\) est premier, donc impair, et \(4 \mid n\). On doit alors avoir \(\frac{n}{4} + 1 \mid n\) ou \(\frac{n}{4} + 1\) premier.
- Dans le premier cas, \(\frac{n}{4} + 1\) divise \(4\left(\frac{n}{4} + 1\right) - n = 4\), donc \(n = 4\) ou \(n = 12\).
- Dans le second cas, \(\frac{n}{4} + 1\) est impair si \(n \neq 4\). Donc \(n = 8m\) où \(2m + 1\), \(4m + 1\), \(8m + 1\) sont tous premiers. Le cas \(n = 8\) ne convient pas, donc \(m > 1\) et \(3 \mid m\) (sinon l'un de ces trois nombres, tous plus grands que \(3\), serait multiple de \(3\)). Ainsi \(24 \mid n\), puis \(25 \mid n\) puisque \(25\) n'est pas premier.
Soit maintenant \(p\) le plus petit entier positif ne divisant pas \(n\) : comme dans la solution 3, \(p\) est premier, et ce qui précède (\(1, 2, \ldots, 6\) divisent \(n\)) montre que \(p \geq 7\). Tout entier inférieur à \(p\) divise \(n\), donc tout produit d'entiers premiers entre eux inférieurs à \(p\) divise \(n\).
Si \(p^2 - 1 = (p - 1)(p + 1)\) est un tel produit, il divise \(n\) ; comme \(p^2\) n'est pas premier, \(p^2\) divise aussi \(n\), contradiction. Or \(p - 1\) et \(p + 1\) sont pairs et n'ont pas de facteur commun autre que \(2\), donc toutes les puissances de nombres premiers impairs divisant leur produit sont inférieures à \(p\) ; le seul cas où \(p^2 - 1\) n'est pas un produit d'entiers premiers entre eux inférieurs à \(p\) est celui où \(p - 1\) ou \(p + 1\) est une puissance de \(2\), disons \(2^m\) (avec \(m \geq 3\)).
- Si \(p = 2^m - 1\), alors \(3p - 1 = 4(3 \cdot 2^{m-2} - 1)\), où \(3 \cdot 2^{m-2} - 1\) est un entier impair inférieur à \(p\) ; donc \(3p - 1 \mid n\), puis \(3p \mid n\) (car \(3p\) n'est pas premier), contradiction.
- Si \(p = 2^m + 1\), alors \(m\) est pair et \(2p - 1 = 2^{m+1} + 1\) est multiple de \(3\) ; ce n'est une puissance de \(3\) que pour \(m = 2\), or \(m \geq 3\). Donc \(2p - 1\) est un produit d'entiers premiers entre eux inférieurs à \(p\), d'où \(2p - 1 \mid n\) et \(2p \mid n\) : de nouveau une contradiction.
Il ne reste donc que \(n \in \{1, 2, 4, 12\}\). \(\blacksquare\)
Solution 5¶
Comme dans la solution 4, si \(n > 2\) alors \(n\) est pair. Écrivons \(n = 2 \cdot 3^k \cdot r\) avec \(k \geq 0\) entier et \(3 \nmid r\).
Comme \(r\) et \(2r\) sont distincts et non nuls modulo \(3\), l'un d'eux est congru à \(2\) modulo \(3\) ; notons-le \(ar\), avec \(a \in \{1, 2\}\). Comme \(ar \mid n\), \(ar + 1\) est premier ou divise \(n\).
Premier cas : \(ar + 1\) premier. Comme \(3 \mid ar + 1\), on a \(ar + 1 = 3\), donc \(r = \frac{2}{a} \in \{1, 2\}\) et \(n = 2 \cdot 3^k \cdot r\). On doit avoir \(k \leq 1\) (sinon \(9 \mid n\) mais \(10 \nmid n\)). En examinant les cas (\(n \in \{2, 4, 6, 12\}\), et \(6\) ne convient pas car \(4 \nmid 6\)), on obtient \(n \in \{2, 4, 12\}\).
Second cas : \(ar + 1 \mid n\). Comme \(ar + 1\) est premier avec \(r\), on a \(ar + 1 \mid 2 \cdot 3^k\), et puisque \(3 \mid ar + 1\), \(k \geq 1\). En particulier, \(3^k + 1\) est un nombre pair au moins égal à \(4\) ; il n'est pas premier, donc il divise \(n\). Étant premier avec \(3\), il vérifie \(3^k + 1 \mid 2r\).
Soient \(q_1\), \(q_2\) tels que \(q_1(ar + 1) = 2 \cdot 3^k\) et \(q_2(3^k + 1) = 2r\). On a \(q_1 ar < 2 \cdot 3^k\) et \(q_2 3^k < 2r\) ; en multipliant, \(q_1 q_2 a < 4\).
- Si \(a = 2\), alors \(q_1 = q_2 = 1\), donc \(2r + 1 = 2 \cdot 3^k\), ce qui est impossible (parité).
- Si \(a = 1\), alors \(r \equiv 2 \pmod 3\), et \(q_2(3^k + 1) = 2r\) donne \(q_2 \equiv 1 \pmod 3\), d'où \(q_2 = 1\). Donc \(2r = 3^k + 1\). Alors \(q_1(r + 1) = 2 \cdot 3^k\) s'écrit \(q_1(3^k + 3) = 4 \cdot 3^k\), soit \(3^{k-1}(4 - q_1) = q_1\). Ainsi \(3^{k-1} \leq q_1 < 4\), donc \(k \leq 2\). En examinant les cas (\(k = 1\) : \(n = 12\) ; \(k = 2\) : \(n = 90\), qui ne convient pas car \(3 \mid 90\) mais \(4 \nmid 90\)), seul \(n = 12\) convient. \(\blacksquare\)