Shortlist 2025, N8¶
Domaine : Théorie des nombres · Difficulté : ★★★★★ · Proposé par : Romania
Concepts : Équations diophantiennes : factorisation et encadrement · Congruences, théorèmes de Fermat et d'Euler · Résidus quadratiques · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2025 (avec solutions), section N8 (livret PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Prove that there are finitely many prime numbers \(p\) such that
- \(p - 8\) is a perfect square, and
- for all odd positive integers \(k < \sqrt{p}\), the number \(p - k^2\) has at most two distinct prime factors.
Indices : les idées clés
- Équations diophantiennes : factorisation : avec \(k = 3\), \((n-1)(n+1) = 2^a q^b\), ce qui force \(n = 2^{a-1} \pm 1\) et ramène à \(2^{a-2} = q^b \mp 1\).
- Congruences, petit théorème de Fermat : modulo \(17\), \(2^{2^d} \equiv 1\) dès que \(d \geq 4\).
- Résidus quadratiques : on trouve un petit premier \(r \mid n\), \(r \leq \sqrt{n}\), modulo lequel \(p \equiv 8\) (donc \(2\)) est un carré.
- Divisibilité et PGCD : avec \(m^2 \equiv p \pmod r\), les trois nombres \(p - m^2\), \(p - (4r-m)^2\), \(p - (4r+m)^2\) n'ont que \(2\) et \(r\) comme facteurs premiers, et leurs PGCD deux à deux sont trop petits.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2025 (une solution et trois remarques).
Solution¶
Soit \(p = n^2 + 8\) un tel nombre premier. Alors \(p\) est impair et \(p \geq 8\) ; en fait \(p \geq 11\), et \(n\) est impair. Donc \(3 < \sqrt{p}\) et, avec \(k = 3\), le nombre \(p - 9 = (n+1)(n-1)\) a au plus deux facteurs premiers distincts. Comme \(p - 9\) est pair, l'un d'eux est \(2\). Donc \((n+1)(n-1) = 2^a q^b\) pour un nombre premier impair \(q\) et des entiers naturels \(a\) et \(b\).
Comme \(n\) est impair, \(\gcd(n - 1, n + 1) = 2\). Donc \(\{n - 1, n + 1\} = \{2^{a-1}, 2q^b\}\) ou \(\{2, 2^{a-1} q^b\}\). Le second cas impose \(n = 3\), ce qui donne la solution \(p = 17\). Ainsi \(n - 1\) et \(n + 1\) sont égaux à \(2^{a-1}\) et \(2q^b\) dans un certain ordre. Étudions séparément les deux cas.
Cas 1 : \(n = 2^{a-1} + 1 = 2q^b - 1\).
Si \(b = 0\), alors \(n = 1\) et \(p = 9\), qui n'est pas premier ; on peut donc supposer \(b \geq 1\). Alors
Donc \(1 + q + \cdots + q^{b-1}\) est une puissance de \(2\) et, comme \(q\) est impair, elle a la même parité que \(b\). La seule puissance impaire de \(2\) étant \(1\), si \(b\) est impair alors \(b = 1\). Donc \(b = 1\) ou \(b\) est pair. Si \(b\) est pair, \(2^{a-2} = (q^{b/2} + 1)(q^{b/2} - 1)\) ; donc \(q^{b/2} + 1\) et \(q^{b/2} - 1\) sont des puissances de \(2\) qui diffèrent de \(2\). D'où \(q^{b/2} = 3\), \(n = 17\) et \(p = 297\), qui n'est pas premier. On peut donc supposer \(b = 1\).
De \(b = 1\), on tire \(2^{a-1} + 1 = 2q - 1\), donc \(q = 2^{a-2} + 1\). Si \(a = 2\), alors \(n = 3\) et \(p = 17\), qui est une solution. On peut donc supposer \(a \geq 3\), et \(q\) est un nombre premier de Fermat (premier impair égal à une puissance de \(2\) plus \(1\)). Si un entier impair \(d > 1\) divise \(a - 2\), en écrivant \(a - 2 = de\) on obtient la factorisation
ce qui contredit la primalité de \(q\). Donc \(a = 2^c + 2\) pour un entier naturel \(c\), et \(q = 2^{2^c} + 1\). Si \(c \geq 4\), alors par le petit théorème de Fermat
Donc \(n = 2^{a-1} + 1 \equiv 3\) et \(p = n^2 + 8 \equiv 0 \pmod{17}\), d'où \(p = 17\). Sinon \(c < 4\), ce qui ne laisse que \(4\) possibilités pour \(a\), donc pour \(n\) et \(p\) ; parmi elles figurent les solutions \(p = 89\) et \(p = 1097\).
Cas 2 : \(n = 2^{a-1} - 1 = 2q^b + 1\).
Si \(a\) est pair, alors \(q^b = 2^{a-2} - 1 = \left(2^{a/2 - 1} + 1\right)\left(2^{a/2 - 1} - 1\right)\). Deux puissances de \(q\) diffèrent donc de \(2\) : ce ne peut être que \(1\) et \(3\), ce qui ne donne pas de solution. On peut donc supposer \(a\) impair et \(a \geq 3\). (On pourrait montrer, comme dans le cas précédent, que \(q\) est un nombre premier de Mersenne, mais ce n'est pas nécessaire.)
Lemme. Sauf pour un nombre fini de valeurs de \(n\), il existe un diviseur premier \(r\) de \(n\) tel que \(r \leq \sqrt{n}\) et que \(p\) soit un résidu quadratique modulo \(r\).
(Comme \(n\) est impair, \(r\) est aussi impair. Et comme \(p = n^2 + 8\), le lemme s'applique à tous les \(p\) sauf un nombre fini.) Précision ajoutée : le lemme est énoncé dans le cas 2 ; le cas 1 ne laisse de toute façon qu'un nombre fini de valeurs de \(p\).
Preuve. Si \(r \mid n\), alors \(p = n^2 + 8 \equiv 8 \pmod r\). Donc \(2\) est un résidu quadratique modulo \(r\) si et seulement si \(2 \cdot 2^2 \equiv 8 \equiv p\) en est un.
Cas 2a : \(a - 1\) n'est pas une puissance de \(2\). Soit \(s > 1\) un diviseur impair de \(a - 1\). Comme \(a - 1\) est pair, \(s\) est un diviseur strict de \(a - 1\). Alors \(2^s - 1\) divise \(2^{a-1} - 1 = n\) et \(2^s - 1 \leq \sqrt{n}\). Soit \(r\) un diviseur premier de \(2^s - 1\). Comme \(2^{s+1} \equiv 2 \pmod r\) et que \(s + 1\) est pair, \(2 = \left(2^{(s+1)/2}\right)^2\) est un résidu quadratique modulo \(r\), donc \(p\) aussi.
Cas 2b : \(a - 1\) est une puissance de \(2\). Écrivons \(a - 1 = 2^d\) avec \(d\) entier naturel. Si \(d \geq 4\), alors \(n = 2^{a-1} - 1 = 2^{2^d} - 1 \equiv 0 \pmod{17}\) par le petit théorème de Fermat. Donc \(17 \mid n\) et, comme \(6^2 \equiv 2 \pmod{17}\), \(2\) (donc aussi \(p\)) est un résidu quadratique modulo \(17\). Pour tous les \(n\) sauf un nombre fini, on a \(17 \leq \sqrt{n}\) et \(d \geq 4\) ; pour ces \(n\), on peut prendre \(r = 17\). \(\square\)
En excluant les \(n\) en nombre fini du lemme, on obtient un \(r\) comme ci-dessus. Il existe alors un entier \(m\), \(0 < m < r\), tel que \(m^2 \equiv p \pmod r\). Comme \(r\) est impair, quitte à remplacer \(m\) par \(r - m\), on peut supposer \(m\) impair.
En excluant encore un nombre fini de \(n\) (donc de \(p\)), on peut supposer \(n \geq 25\). Avec \(n \geq 25\) et \(n \geq r^2\), on a \(p = n^2 + 8 > n^2 \geq 25r^2\). Comme \(m < r\), on a \(p > (5r)^2 \geq (4r + m)^2\). Les entiers impairs \(m\), \(4r - m\), \(4r + m\) sont donc inférieurs à \(\sqrt{p}\), et les nombres
sont divisibles par \(2\) et par \(r\), donc (ayant au plus deux facteurs premiers) par aucun autre nombre premier. En considérant les PGCD, on a :
- \(\gcd\left(p - m^2,\ p - (4r - m)^2\right) = \gcd\left(p - m^2,\ (4r - m)^2 - m^2\right)\), qui divise \(8r(2r - m)\) ;
- \(\gcd\left(p - m^2,\ p - (4r + m)^2\right) = \gcd\left(p - m^2,\ (4r + m)^2 - m^2\right)\), qui divise \(8r(2r + m)\) ;
- \(\gcd\left(p - (4r + m)^2,\ p - (4r - m)^2\right) = \gcd\left(p - (4r + m)^2,\ (4r + m)^2 - (4r - m)^2\right)\), qui divise \(16rm\).
Comme \(r\) et \(m\) sont impairs (et \(r \nmid m\), \(r \nmid 2r \pm m\)), la plus grande puissance de \(2\) qui divise l'un de ces PGCD est au plus \(16\), et la plus grande puissance de \(r\) est au plus \(r\). Par conséquent, au plus un des trois nombres \(p - m^2\), \(p - (4r - m)^2\), \(p - (4r + m)^2\) est divisible par \(r^2\), et au plus un est divisible par \(32\). Donc au moins l'un d'eux divise \(16r\). Ainsi le plus petit d'entre eux est au plus \(16r\), c'est-à-dire \(p - (4r + m)^2 \leq 16r\). Comme \(m < r\) sont tous deux impairs, \(m \leq r - 2\), donc \(5r - 2 \geq 4r + m\), et
D'où \(p \leq (5r - 2)^2 + 16r = 25r^2 - 4r + 4 < 25r^2\), ce qui contredit la minoration \(p \geq 25r^2\) obtenue plus haut.
Il n'y a donc qu'un nombre fini de nombres premiers \(p\) vérifiant les conditions. \(\blacksquare\)
Remarques¶
Remarque 1 (la liste complète). Des arguments similaires permettent de montrer que les seuls nombres premiers vérifiant les conditions sont \(17\), \(89\), \(233\) et \(1097\), au prix de nombreuses vérifications arithmétiques.
Remarque 2 (le cœur du problème). Il y a plusieurs façons de montrer que tout nombre premier \(r\) divisant \(p - k^2\) doit être relativement grand. Le point crucial est d'obtenir une contradiction en trouvant un petit nombre premier qui divise \(p - k^2\), comme dans le lemme.
Remarque 3 (Catalan). Les deux cas mènent aux égalités \(2^{a-2} = q^b - 1\) et \(2^{a-2} = q^b + 1\) ; lorsque \(b > 1\), on peut les traiter avec la conjecture de Catalan (théorème de Mihăilescu).