Shortlist 2019, N7¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Canada
Concepts : Congruences, théorèmes de Fermat et d'Euler · Théorème des restes chinois · Ordre d'un élément et racines primitives
Solution officielle : Shortlist officielle 2019 (avec solutions), section N7 (livret PDF)
Énoncé¶
Prove that there is a constant \(c > 0\) and infinitely many positive integers \(n\) with the following property: there are infinitely many positive integers that cannot be expressed as the sum of fewer than \(c\, n \log(n)\) pairwise coprime \(n\)-th powers.
Indices : les idées clés
- Théorème d'Euler : si \(\varphi(p^e) \mid n\), toute puissance \(n\)-ième est congrue à \(0\) ou \(1\) modulo \(p^e\), donc une somme de \(m\) puissances \(n\)-ièmes deux à deux premières entre elles est congrue à \(m\) ou \(m - 1\).
- Théorème des restes chinois : modulo \(N\), ces sommes n'occupent qu'au plus \(2^k m\) classes (\(k\) = nombre de facteurs premiers de \(N\)) ; si \(N > 2^k m\), une infinité d'entiers ne sont pas de cette forme.
- Ordre de \(2\) modulo un diviseur premier des nombres de Fermat (solution 1) : si \(p \mid 2^{2^{t-1}} + 1\), alors \(2^t \mid p - 1\) ; cela donne des premiers \(p\), \(q\) congrus à \(1\) modulo une grande puissance de \(2\) sans être trop grands.
- Théorème des nombres premiers (solution 2) : avec \(N = \operatorname{ppcm}(1, \ldots, 2x)\) et \(n = 2\operatorname{ppcm}(1, \ldots, x)\), on obtient même \(N > 2^{\pi(2x)} n^{2-\varepsilon}\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (deux solutions et trois remarques).
Solution 1¶
Supposons que, pour un entier \(n\), on trouve un entier \(N\) vérifiant la propriété suivante :
Cette propriété assure (théorème d'Euler) que toute puissance \(n\)-ième est congrue à \(0\) ou \(1\) modulo chacune de ces puissances \(p^e\) ; donc toute somme de \(m\) puissances \(n\)-ièmes deux à deux premières entre elles est congrue à \(m\) ou \(m - 1\) modulo \(p^e\), puisqu'au plus une de ces puissances \(n\)-ièmes est divisible par \(p\). Ainsi, si \(k\) désigne le nombre de facteurs premiers distincts de \(N\), le théorème des restes chinois montre qu'il y a au plus \(2^k m\) classes de résidus modulo \(N\) qui sont des sommes d'au plus \(m\) puissances \(n\)-ièmes deux à deux premières entre elles. En particulier, si \(N > 2^k m\), il y a une infinité d'entiers positifs qui ne s'écrivent pas comme somme d'au plus \(m\) puissances \(n\)-ièmes deux à deux premières entre elles.
Il suffit donc de prouver qu'il existe des couples \((n, N)\) d'entiers arbitrairement grands vérifiant \((\dagger)\) et tels que
pour une constante \(c > 0\).
Construction. Fixons un entier positif \(t\) et choisissons des nombres premiers (distincts) \(p \mid 2^{2^{t-1}} + 1\) et \(q \mid 2^{2^t} + 1\) ; posons \(N = pq\). Il est bien connu que \(2^t \mid p - 1\) et \(2^{t+1} \mid q - 1\) (l'ordre de \(2\) modulo \(p\) est \(2^t\), et modulo \(q\) il est \(2^{t+1}\)). Donc
est un entier, et le couple \((n, N)\) vérifie \((\dagger)\) (ici \(k = 2\)).
Estimations. On a
ce qui se réécrit
et l'on conclut en choisissant \(c < \frac{1}{8\log(2)} \approx 0{,}18\). \(\blacksquare\)
Solution 2 (avec de meilleures bornes)¶
Comme dans la solution précédente, on cherche des couples d'entiers \((n, N)\) arbitrairement grands vérifiant \((\dagger)\) et tels que \(N > c\, 2^k n \log(n)\).
Cette fois, on fixe un entier \(x \geq 4\), on prend pour \(N\) le ppcm de \(1, 2, \ldots, 2x\), et pour \(n\) le double du ppcm de \(1, 2, \ldots, x\). Le couple \((n, N)\) vérifie bien la condition : si \(p^e\) est une puissance de premier divisant \(N\), alors \(\frac{\varphi(p^e)}{2} \leq x\) est un diviseur de \(\frac n2 = \operatorname{ppcm}_{r \leq x}(r)\).
Le quotient \(2N/n\) est le produit de tous les nombres premiers ayant une puissance dans l'intervalle \((x, 2x]\), donc \(2N/n > x^{\pi(2x) - \pi(x)}\). Ainsi, pour \(x\) assez grand,
d'après le théorème des nombres premiers \(\pi(t) \sim t/\log(t)\).
D'autre part, \(n\) est un produit d'au plus \(\pi(x)\) puissances de premiers inférieures ou égales à \(x\) (à un facteur \(2\) près), d'où la majoration
encore par le théorème des nombres premiers. En combinant avec l'inégalité précédente, on trouve que pour tout \(\varepsilon > 0\), l'inégalité
est vraie pour \(x\) assez grand. Cela se réécrit
pour tout \(x\) assez grand, ce qui conclut (ici \(k = \pi(2x)\)). \(\blacksquare\)
Remarques¶
Remarque 1 (variante de la solution 1). L'astuce de la solution 1 consiste à trouver des nombres premiers \(p\) et \(q\) congrus à \(1\) modulo un certain \(d = 2^t\) et pas trop grands. On peut aussi utiliser le théorème de Linnik : il existe des constantes absolues \(b\) et \(L > 1\) telles que, pour tous entiers premiers entre eux \(a\) et \(d\), il existe un nombre premier congru à \(a\) modulo \(d\) et inférieur ou égal à \(b d^L\). En choisissant \(d\) non divisible par \(3\) et deux premiers distincts \(p, q \leq b(3d)^L\) congrus à \(1\) modulo \(d\) (et, par exemple, distincts modulo \(3\)), on obtient un couple \((n, N)\) vérifiant \((\dagger)\) avec \(N = pq\) et \(n = \frac{(p-1)(q-1)}{d}\). Un calcul direct montre que \(N > C n^{1 + \frac{1}{2L - 1}}\) pour une constante \(C\), ce qui dépasse \(c \cdot 2^2 n \log(n)\) pour \(p\) grand, quelle que soit \(c\). L'énoncé est donc vrai pour toute constante \(c\) ; plus fortement, il reste vrai en remplaçant \(c\,n\log(n)\) par \(n^{1+\delta}\) pour \(\delta > 0\) assez petit.
Remarque 2 (meilleures bornes). La borne \(N > 2^{\pi(2x)} n^{2-\varepsilon}\) de la solution 2 montre qu'une infinité d'entiers positifs ne s'écrivent pas comme somme d'au plus \(n^{2-\varepsilon}\) puissances \(n\)-ièmes deux à deux premières entre elles. En affinant la méthode, on peut remplacer \(n^{2-\varepsilon}\) par \(n^\alpha\) pour tout \(\alpha > 0\) : on fixe un entier \(d\), on prend pour \(N\) le produit des nombres premiers au plus égaux à \(dx\) et congrus à \(1\) modulo \(d\), et \(n = d \operatorname{ppcm}_{r \leq x}(r)\) ; le couple \((n, N)\) vérifie \((\dagger)\). Le théorème des nombres premiers dans les progressions arithmétiques donne \(\log(N) \sim \frac{d}{\varphi(d)} x\), \(\log(n) \sim x\) et \(\pi(dx) \sim \frac{dx}{\log(x)}\) pour \(d\) fixé, d'où \(N > 2^{\pi(dx)} n^{d/\varphi(d) - \varepsilon}\) pour tout \(\varepsilon > 0\) et \(x\) assez grand. Comme le rapport \(\frac{d}{\varphi(d)}\) peut être rendu arbitrairement grand par un choix judicieux de \(d\), on obtient la borne en \(n^\alpha\).
Remarque 3. Les grands résultats de théorie analytique des nombres (théorème des nombres premiers, théorème de Linnik) ne simplifient pas vraiment le problème : toutes les solutions connues passent d'abord par la réduction à la condition \((\dagger)\), et même ensuite les résultats analytiques n'indiquent pas clairement comment conclure. C'est pourquoi le problème a été jugé adapté à l'OIM. Ces résultats permettent surtout de renforcer la borne principale, typiquement en remplaçant \(n\log(n)\) par une puissance \(n^{1+\delta}\), mais de telles bornes sont peu susceptibles d'être trouvées par des élèves en épreuve. La meilleure borne connue par des méthodes purement élémentaires est de la forme \(N > 2^k n (\log n)^M\) pour tout entier \(M > 0\) : on l'obtient par une variante de la solution 1, en choisissant des premiers \(p_0, \ldots, p_M\) avec \(p_i \mid 2^{2^{t+i-1}} + 1\) et en posant \(N = \prod_i p_i\) et \(n = 2^{-tM} \prod_i (p_i - 1)\).