Shortlist 2012, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : non indiqué
Concepts : Ordre d'un élément et racines primitives · Résidus quadratiques · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Théorème des restes chinois
Solution officielle : Shortlist officielle 2012 (avec solutions), p. 48 (page 48 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(x\) and \(y\) be positive integers. If \(x^{2^n} - 1\) is divisible by \(2^n y + 1\) for every positive integer \(n\), prove that \(x = 1\).
Indices : les idées clés
- Une infinité de premiers \(p \equiv 3 \pmod 4\) divisent un nombre \(2^n y + 1\) : sinon, avec un \(n\) bien choisi par Euler (restes chinois), \(2^n y + 1\) serait \(\equiv 3 \pmod 4\) et \(\equiv 1 \pmod 4\) à la fois.
- Ordre : si \(p \mid 2^n y + 1\), alors \(x^{2^n} \equiv 1\) et \(x^{p-1} \equiv 1 \pmod p\), donc \(x^{\operatorname{pgcd}(2^n, p - 1)} \equiv 1\).
- Modulo 4 : pour \(p \equiv 3 \pmod 4\), ce PGCD vaut \(2\), donc \(p \mid x^2 - 1\) pour une infinité de \(p\) : \(x = 1\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2012 (une solution et une remarque).
Solution¶
Montrons d'abord le fait suivant : pour tout entier \(y \geq 1\), il existe une infinité de nombres premiers \(p \equiv 3 \pmod 4\) qui divisent un nombre de la forme \(2^n y + 1\).
Il suffit évidemment de traiter le cas \(y\) impair. Soit
la décomposition en facteurs premiers de \(2y + 1\). Supposons au contraire qu'il n'y ait qu'un nombre fini de nombres premiers \(p_{r+1}, \ldots, p_{r+s} \equiv 3 \pmod 4\) qui divisent un nombre de la forme \(2^n y + 1\) sans diviser \(2y + 1\).
On cherche un \(n\) tel que \(p_i^{e_i} \parallel 2^n y + 1\) pour \(1 \leq i \leq r\) et \(p_i \nmid 2^n y + 1\) pour \(r + 1 \leq i \leq r + s\). Pour cela, il suffit de prendre
car alors, par le théorème d'Euler,
Cette congruence signifie que \(p_1^{e_1}, \ldots, p_r^{e_r}\) divisent exactement \(2^n y + 1\) et qu'aucun des nombres premiers \(p_{r+1}, \ldots, p_{r+s}\) ne divise \(2^n y + 1\). La décomposition de \(2^n y + 1\) est donc formée des puissances \(p_1^{e_1}, \ldots, p_r^{e_r}\) et de puissances de nombres premiers \(\equiv 1 \pmod 4\). Comme \(y\) est impair, on obtient
C'est une contradiction, puisque \(n > 1\) et donc \(2^n y + 1 \equiv 1 \pmod 4\).
Passons au problème. Si \(p\) est un diviseur premier de \(2^n y + 1\), l'énoncé implique que \(x^d \equiv 1 \pmod p\) pour \(d = 2^n\). Par le petit théorème de Fermat, la même congruence est vraie pour \(d = p - 1\), donc aussi pour \(d = \operatorname{pgcd}(2^n, p - 1)\) (ordre de \(x\) modulo \(p\)). Pour \(p \equiv 3 \pmod 4\), on a \(\operatorname{pgcd}(2^n, p - 1) = 2\), donc dans ce cas \(x^2 \equiv 1 \pmod p\).
En résumé, tout nombre premier \(p \equiv 3 \pmod 4\) qui divise un nombre de la forme \(2^n y + 1\) divise aussi \(x^2 - 1\). Ce n'est possible que si \(x = 1\) : sinon, d'après ce qui précède, \(x^2 - 1\) serait un entier strictement positif ayant une infinité de facteurs premiers. \(\blacksquare\)
Remarque¶
Pour tout \(x\) et tout nombre premier impair \(p\), la plus grande puissance de \(p\) qui divise \(x^{2^n} - 1\) pour un \(n\) est bornée ; il en est donc de même pour les nombres \(2^n y + 1\). On en déduit que \(p^2\) divise \(2^{p-1} - 1\) pour tout diviseur premier \(p\) de \(2^n y + 1\). Toutefois, essayer d'aboutir à une contradiction avec cette seule conclusion semble sans espoir, car on ne sait même pas s'il existe une infinité de nombres premiers sans cette propriété.