Aller au contenu

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)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

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

\[5^{k+1}x + 3^{k+1}y, \qquad 0 \leq x, y \leq \sqrt{m}.\]

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

\[5^{k+1}a + 3^{k+1}b \equiv 0 \pmod m, \qquad |a|, |b| \leq \sqrt m.\]

De

\[0 \equiv (5^{k+1}a)^2 - (3^{k+1}b)^2 = 5^{n+1}a^2 - 3^{n+1}b^2 \equiv 5 \cdot 3^n a^2 - 3^{n+1}b^2 = 3^n(5a^2 - 3b^2) \pmod m\]

(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\),

\[0 < |5a^2 - 3b^2| \leq \max(5a^2, 3b^2) \leq 5m,\]

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\)),

\[-1 = \left(\frac{2^n + 65}{5}\right) = \left(\frac{5}{2^n + 65}\right) = \left(\frac{5^n}{2^n + 65}\right) = \left(\frac{3^n}{2^n + 65}\right) = \left(\frac{3}{2^n + 65}\right) = \left(\frac{2^n + 65}{3}\right) = 1,\]

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\),

\[1 = \left(\frac{15}{p}\right) = \left(\frac{3}{p}\right)\left(\frac{5}{p}\right) = (-1)^{\frac{p-1}{2}}\left(\frac{p}{3}\right)\left(\frac{p}{5}\right),\]

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.