Shortlist 2022, N8¶
Domaine : Théorie des nombres · Difficulté : ★★★★★ · Proposé par : Belgium
Concepts : Principe extrémal · Principe des tiroirs · Congruences, théorèmes de Fermat et d'Euler · Résidus quadratiques
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 71 (page 73 du PDF)
Énoncé¶
Montrer que \(5^n - 3^n\) n'est divisible par \(2^n + 65\) pour aucun entier \(n\) strictement positif.
Énoncé original (anglais)
Prove that \(5^n - 3^n\) is not divisible by \(2^n + 65\) for any positive integer \(n\).
Indices : les idées clés
- Principe extrémal (solution 1) : on considère le plus petit multiple positif \(m_1\) de \(m = 2^n + 65\) de la forme \(|5a^2 - 3b^2|\) ou \(|a^2 - 15b^2|\), et on le fait « descendre ».
- Principe des tiroirs (solution 1) : parmi les \(5^{k+1}x + 3^{k+1}y\) avec \(0 \leq x, y \leq \sqrt m\), deux sont congrus modulo \(m\), ce qui donne \(m_1 \leq 5m\) (lemme de Thue).
- Congruences : \(n\) est impair, et les formes \(\pm(5a^2 - 3b^2)\), \(\pm(a^2 - 15b^2)\) ne peuvent valoir \(2^n + 65\) (étude modulo \(3\), \(4\) et \(5\)).
- Symboles de Jacobi (solution 2) : par réciprocité quadratique, \(\left(\frac{5}{m}\right) = -1\) alors que \(\left(\frac{3}{m}\right) = 1\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (deux solutions et deux remarques).
Solution 1¶
Soit \(n\) un entier positif et \(m = 2^n + 65\). Supposons par l'absurde que \(m \mid 5^n - 3^n\), c'est-à-dire \(5^n \equiv 3^n \pmod m\).
Si \(n\) est pair, alors \(3 \mid m\) (\(2^n \equiv 1\) et \(65 \equiv 2 \pmod 3\)), mais \(3 \nmid 5^n - 3^n\) : contradiction. On suppose donc désormais \(n\) impair, \(n = 2k + 1\). Évidemment \(n = 1\) est impossible (\(67 \nmid 2\)), donc \(n \geq 3\). Remarquons que \(m\) est premier avec \(2\), \(3\) et \(5\).
Principe extrémal. Soit \(m_1\) le plus petit multiple positif de \(m\) qui peut s'écrire sous la forme \(|5a^2 - 3b^2|\) ou \(|a^2 - 15b^2|\) avec des entiers \(a\) et \(b\).
Comme \(5^n - 3^n = 5\left(5^k\right)^2 - 3\left(3^k\right)^2\) est un multiple de \(m\), l'ensemble de tels multiples est non vide, et \(m_1\) est bien défini.
I. Montrons que \(m_1 \leq 5m\). Considérons les nombres
Il y a \(\lfloor \sqrt m \rfloor + 1 > \sqrt m\) choix pour \(x\) et pour \(y\), donc plus de \(m\) couples \((x, y)\). Par le principe des tiroirs, deux de ces sommes sont congrues modulo \(m\) : \(5^{k+1}x_1 + 3^{k+1}y_1 \equiv 5^{k+1}x_2 + 3^{k+1}y_2 \pmod m\). Posons \(a = x_1 - x_2\) et \(b = y_1 - y_2\) ; l'un au moins de \(a, b\) est non nul, et
De
(on a utilisé \(5^n \equiv 3^n\)), et comme \(m\) est premier avec \(3\), on voit que \(|5a^2 - 3b^2|\) est un multiple de \(m\). Comme \(a\) ou \(b\) est non nul, \(5a^2 \neq 3b^2\) (irrationalité de \(\sqrt{15}\)). Donc, par le choix de \(a, b\),
ce qui montre que \(m_1 \leq 5m\).
II. Montrons que \(m_1\) n'est divisible ni par \(2\), ni par \(3\), ni par \(5\). Comme \(m_1\) vaut \(|5a^2 - 3b^2|\) ou \(|a^2 - 15b^2|\), il y a six cas. Dans chacun, on obtient une contradiction en exhibant un multiple de \(m\) de la même forme, plus petit que \(m_1\).
- Si \(5 \mid m_1\) et \(m_1 = |5a^2 - 3b^2|\), alors \(5 \mid b\) et \(\left|a^2 - 15\left(\frac{b}{5}\right)^2\right| = \frac{m_1}{5} < m_1\).
- Si \(5 \mid m_1\) et \(m_1 = |a^2 - 15b^2|\), alors \(5 \mid a\) et \(\left|5\left(\frac{a}{5}\right)^2 - 3b^2\right| = \frac{m_1}{5} < m_1\).
- Si \(3 \mid m_1\) et \(m_1 = |5a^2 - 3b^2|\), alors \(3 \mid a\) et \(\left|b^2 - 15\left(\frac{a}{3}\right)^2\right| = \frac{m_1}{3} < m_1\).
- Si \(3 \mid m_1\) et \(m_1 = |a^2 - 15b^2|\), alors \(3 \mid a\) et \(\left|5b^2 - 3\left(\frac{a}{3}\right)^2\right| = \frac{m_1}{3} < m_1\).
- Si \(2 \mid m_1\) et \(m_1 = |5a^2 - 3b^2|\), alors \(\left|\left(\frac{5a - 3b}{2}\right)^2 - 15\left(\frac{a - b}{2}\right)^2\right| = \frac{m_1}{2} < m_1\).
- Si \(2 \mid m_1\) et \(m_1 = |a^2 - 15b^2|\), alors \(\left|5\left(\frac{a - 3b}{2}\right)^2 - 3\left(\frac{a - 5b}{2}\right)^2\right| = \frac{m_1}{2} < m_1\).
(Dans les deux derniers cas, \(m_1\) pair impose que \(a\) et \(b\) aient la même parité, donc les fractions sont entières. Ces deux expressions s'obtiennent à partir de \((\sqrt5 a + \sqrt3 b)(\sqrt5 - \sqrt3) = (5a - 3b) + \sqrt{15}(b - a)\) et \((a + \sqrt{15}b)(\sqrt5 - \sqrt3) = \sqrt5(a - 3b) + \sqrt3(5b - a)\).)
Dans les six cas, l'un des nombres \(\frac{m_1}{2}\), \(\frac{m_1}{3}\), \(\frac{m_1}{5}\) est de la forme \(|5x^2 - 3y^2|\) ou \(|x^2 - 15y^2|\). Comme \(m\) est premier avec \(2\), \(3\) et \(5\), ce nombre est un multiple de \(m\), ce qui contredit la minimalité de \(m_1\).
III. Le cas restant \(m_1 = m\). D'après I et II, \(m_1 \in \{m, 2m, 3m, 4m, 5m\}\) n'est divisible ni par \(2\), ni par \(3\), ni par \(5\), donc \(m_1 = m\) : on a \(m = |5a^2 - 3b^2|\) ou \(m = |a^2 - 15b^2|\). On obtient une contradiction en regardant les deux membres modulo \(3\), \(4\) et \(5\) (avec \(n\) impair et \(n \geq 3\)) :
- \(2^n + 65 = 5a^2 - 3b^2\) est impossible, car \(2^n + 65 \equiv 1 \pmod 3\), alors que \(5a^2 - 3b^2 \equiv 2a^2 \not\equiv 1 \pmod 3\).
- \(2^n + 65 = 3b^2 - 5a^2\) est impossible, car \(2^n + 65 \equiv 1 \pmod 4\), alors que \(3b^2 - 5a^2 \not\equiv 1 \pmod 4\).
- \(2^n + 65 = a^2 - 15b^2\) est impossible, car \(2^n + 65 \equiv \pm 2 \pmod 5\), alors que \(a^2 - 15b^2 \equiv a^2 \not\equiv \pm 2 \pmod 5\).
- \(2^n + 65 = 15b^2 - a^2\) est impossible, car \(2^n + 65 \equiv 1 \pmod 4\), alors que \(15b^2 - a^2 \not\equiv 1 \pmod 4\).
On a obtenu une contradiction dans tous les cas, ce qui achève la solution. \(\blacksquare\)
Solution 2¶
Supposons à nouveau que \(5^n \equiv 3^n \pmod{m}\) avec \(m = 2^n + 65\). Comme dans la première solution, \(n\) est impair et \(n \geq 3\), donc \(8 \mid 2^n\) et \(m \equiv 1 \pmod 4\).
Avec les symboles de Jacobi (et la loi de réciprocité quadratique, applicable car \(5 \equiv 1 \pmod 4\) et \(m \equiv 1 \pmod 4\)),
contradiction. \(\blacksquare\)
(Précision ajoutée : la première égalité vient de \(2^n + 65 \equiv 2^n \equiv \pm 2 \pmod 5\) et de ce que \(\pm 2\) ne sont pas des carrés modulo \(5\) ; les égalités avec \(5^n\) et \(3^n\) utilisent que \(n\) est impair ; la dernière vient de \(2^n + 65 \equiv 1 \pmod 3\).)
Remarques¶
Remarque 1 (lemme de Thue). La partie I est une application classique du lemme de Thue : si \(m > 1\) et \(c\) sont des entiers, et \(X, Y\) des entiers positifs tels que \(X \leq m < XY\), alors il existe des entiers \(x, y\) avec \(|x| < X\) et \(0 < y < Y\) tels que \(x \equiv cy \pmod m\). Un corollaire bien connu : si \(c, d\) sont premiers avec \(m\), si la congruence \(cx^2 \equiv dy^2 \pmod m\) a une solution avec \(x, y\) premiers avec \(m\), et si \(X, Y\) sont des entiers positifs avec \(XY > m\), alors \(cx^2 \equiv dy^2 \pmod m\) a une solution avec \(x\) ou \(y\) non nul, \(|x| < X\) et \(|y| < Y\). Dans la solution, on a appliqué ce corollaire avec \(c = 5\), \(d = 3\), \(X = Y = \lfloor \sqrt m \rfloor + 1\).
Remarque 2 (réciprocité quadratique). En fait, la solution 1 prouve qu'un entier positif \(m \equiv 13\) ou \(37 \pmod{60}\) ne peut diviser aucun entier non nul de la forme \(5a^2 - 3b^2\) ou \(a^2 - 15b^2\) avec \(a, b\) premiers entre eux ; autrement dit, si \(m \equiv 13\) ou \(37 \pmod{60}\), alors \(15\) n'est pas un résidu quadratique modulo \(m\). La réciprocité quadratique raccourcit beaucoup la solution. Si \(a\) et \(b\) sont premiers entre eux, pour tout diviseur premier \(p > 5\) de \(5a^2 - 3b^2\) ou de \(a^2 - 15b^2\),
où \(\left(\frac{a}{p}\right)\) est le symbole de Legendre. En considérant les restes de \(p\) modulo \(4\), \(3\) et \(5\), on obtient \(p \equiv \pm 1, \pm 7, \pm 11\) ou \(\pm 17 \pmod{60}\). Ces restes forment un sous-groupe des inversibles modulo \(60\) ; comme \(13\) et \(37\) n'y appartiennent pas, \(m = 2^n + 65\) ne peut pas être un produit de tels premiers. Au lieu de traiter séparément les diviseurs premiers de \(m\), on peut utiliser les symboles de Jacobi : c'est la solution 2.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2024 N2 ★☆☆☆☆ : Trouver les ensembles finis d'entiers où, pour tous \(a, b\), un élément \(c\) vérifie \(a \mid b + 2c\).
- 2020 N5 ★★★☆☆ : Trouver les fonctions additives sur les produits, à valeurs entières, symétriques sur une infinité d'intervalles \([0, n]\).
- 2024 C7 ★★★★☆ · OIM P3 : Chaque terme compte les apparitions du précédent : l'une des deux sous-suites de parité finit par être périodique.
- 2023 A6 ★★★★☆ · OIM P3 : Trouver les suites d'entiers pour lesquelles \(P(a_n)\) est le produit des \(k\) termes suivants, pour un polynôme unitaire de degré \(k\).