Shortlist 2008, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : non indiqué
Concepts : Résidus quadratiques · Congruences, théorèmes de Fermat et d'Euler
Solution officielle : Shortlist officielle 2008 (avec solutions), p. 50 (page 51 du PDF)
Problème 3 de l'OIM 2008
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2008, où il était le problème 3 (jour 1).
Énoncé¶
Prove that there exist infinitely many positive integers \(n\) such that \(n^2 + 1\) has a prime divisor greater than \(2n + \sqrt{2n}\).
Indices : les idées clés
- Racines carrées de \(-1\) : pour \(p \equiv 1 \pmod 8\), la plus petite solution \(n\) de \(x^2 \equiv -1 \pmod p\) vérifie \(n \leq \frac{p - 1}{2}\).
- Écart : en posant \(n = \frac{p - 1}{2} - \ell\), on obtient \((2\ell + 1)^2 + 4 = rp\) avec \(r \equiv 5 \pmod 8\), donc \(r \geq 5\) et \(\ell \geq \frac{\sqrt{5p - 4} - 1}{2}\).
- Inégalité du second degré : avec \(u = \sqrt{5p - 4}\), on obtient \(p \geq 2n + u > 2n + \sqrt{10n}\), plus fort que demandé ; il y a une infinité de premiers \(8k + 1\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution et une remarque). C'est le problème 3 de l'OIM 2008.
Solution¶
Soit \(p \equiv 1 \pmod 8\) un nombre premier. La congruence \(x^2 \equiv -1 \pmod p\) a deux solutions dans \([1, p - 1]\), de somme \(p\). Si \(n\) est la plus petite des deux, alors \(p\) divise \(n^2 + 1\) et \(n \leq (p - 1)/2\). Montrons que \(p > 2n + \sqrt{10n}\).
Posons \(n = (p - 1)/2 - \ell\) avec \(\ell \geq 0\). Alors \(n^2 \equiv -1 \pmod p\) donne
Donc \((2\ell + 1)^2 + 4 = rp\) pour un certain \(r \geq 0\). Comme \((2\ell + 1)^2 \equiv 1 \equiv p \pmod 8\), on a \(r \equiv 5 \pmod 8\), de sorte que \(r \geq 5\). Donc \((2\ell + 1)^2 + 4 \geq 5p\), ce qui implique \(\ell \geq \left(\sqrt{5p - 4} - 1\right)/2\). Posons \(\sqrt{5p - 4} = u\) pour plus de clarté ; alors \(\ell \geq (u - 1)/2\). Par conséquent,
Combiné avec \(p = (u^2 + 4)/5\), cela donne \(u^2 - 5u - 10n + 4 \geq 0\). La résolution de cette inégalité du second degré en \(u \geq 0\) donne \(u \geq \left(5 + \sqrt{40n + 9}\right)/2\). L'estimation \(n \leq (p - u)/2\) donne donc
Comme il existe une infinité de nombres premiers de la forme \(8k + 1\), il s'ensuit facilement qu'il existe aussi une infinité d'entiers \(n\) ayant la propriété voulue (des premiers \(p\) distincts donnent des \(n\) distincts, puisque \(p\) est le plus grand facteur premier de \(n^2 + 1\) supérieur à \(2n\)). \(\blacksquare\)
Remarque¶
En considérant la décomposition en facteurs premiers du produit \(\prod_{n=1}^{N}(n^2 + 1)\), on peut obtenir que son plus grand diviseur premier est au moins \(cN\log N\). Cela pourrait améliorer l'énoncé en \(p > n\log n\).
Cependant, la preuve utilise des informations avancées sur la répartition des nombres premiers de la forme \(4k + 1\), ce qui ne convient pas aux compétitions lycéennes.