Shortlist 2009, N7

Domaine : Théorie des nombres · Difficulté : ★★★★★ · Proposé par : Mongolia

Concepts : Suites et récurrences · Résidus quadratiques · Valuations p-adiques et lemme LTE

Solution officielle : Shortlist officielle 2009 (avec solutions), p. 81 (page 83 du PDF)

Pas encore relu

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

Énoncé

Let \(a\) and \(b\) be distinct integers greater than \(1\). Prove that there exists a positive integer \(n\) such that \((a^n - 1)(b^n - 1)\) is not a perfect square.

Indices : les idées clés

• Développement en série : si \(x_n = \sqrt{(a^n - 1)(b^n - 1)}\) est toujours entier, \(x_n = \sum c_{k,\ell}\left(\frac{\sqrt{ab}}{a^kb^\ell}\right)^n\), combinaison de suites géométriques.
• Récurrence linéaire : une combinaison entière de termes consécutifs tend vers \(0\), donc s'annule ; \(x_n\) vérifie alors une récurrence finie, et \(\sqrt{(1 - \alpha)(1 - \beta)}\) serait un polynôme, ce qui est absurde.
• Formulation originale (\(ab\) non carré) : un premier \(p\) tel que \(ab\) ne soit pas un résidu quadratique, puis le lemme de relèvement \(\nu_p\big(a^{\frac{p-1}{2}p} - 1\big) = \nu_p\big(a^{\frac{p-1}{2}} - 1\big) + 1\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2009 (deux solutions, la solution de la formulation originale et deux remarques).

Solution 1

Remarquons d'abord que

\[(1 - \alpha)^{\frac{1}{2}}(1 - \beta)^{\frac{1}{2}} = \left(1 - \tfrac{1}{2} \cdot \alpha - \tfrac{1}{8} \cdot \alpha^2 - \cdots\right)\left(1 - \tfrac{1}{2} \cdot \beta - \tfrac{1}{8} \cdot \beta^2 - \cdots\right) = \sum_{k, \ell \geq 0} c_{k,\ell} \cdot \alpha^k\beta^\ell \qquad \text{pour tous } \alpha, \beta \in (0, 1), \tag{1}\]

où \(c_{0,0} = 1\) et les \(c_{k,\ell}\) sont certains coefficients.

Raisonnons par l'absurde : supposons que \(x_n = \sqrt{(a^n - 1)(b^n - 1)} \in \mathbb{Z}\) pour tout entier \(n > 0\). Quitte à remplacer \(a\) par \(a^2\) et \(b\) par \(b^2\), on peut supposer que \(a\) et \(b\) sont des carrés parfaits, de sorte que \(\sqrt{ab}\) est entier.

Supposons d'abord que \(a^\mu \neq b^\nu\) pour tous entiers \(\mu, \nu > 0\). On a

\[x_n = (\sqrt{ab})^n\left(1 - \frac{1}{a^n}\right)^{\frac{1}{2}}\left(1 - \frac{1}{b^n}\right)^{\frac{1}{2}} = \sum_{k, \ell \geq 0} c_{k,\ell}\left(\frac{\sqrt{ab}}{a^kb^\ell}\right)^n. \tag{2}\]

En choisissant \(k_0\) et \(\ell_0\) tels que \(a^{k_0} > \sqrt{ab}\), \(b^{\ell_0} > \sqrt{ab}\), on définit le polynôme

\[P(x) = \prod_{k=0, \ell=0}^{k_0-1, \ell_0-1}(a^kb^\ell x - \sqrt{ab}) =: \sum_{i=0}^{k_0 \cdot \ell_0} d_ix^i\]

à coefficients entiers \(d_i\). D'après notre hypothèse, les racines

\[\frac{\sqrt{ab}}{a^kb^\ell}, \qquad k = 0, \ldots, k_0 - 1, \quad \ell = 0, \ldots, \ell_0 - 1,\]

de \(P\) sont deux à deux distinctes.

Considérons ensuite la suite d'entiers

\[y_n = \sum_{i=0}^{k_0 \cdot \ell_0} d_ix_{n+i}, \qquad n = 1, 2, \ldots \tag{3}\]

Par la théorie des récurrences linéaires, on obtient

\[y_n = \sum_{\substack{k, \ell \geq 0 \\ k \geq k_0 \text{ ou } \ell \geq \ell_0}} e_{k,\ell}\left(\frac{\sqrt{ab}}{a^kb^\ell}\right)^n, \qquad n = 1, 2, \ldots, \tag{4}\]

avec des réels \(e_{k,\ell}\). On a

\[\lvert y_n \rvert \leq \sum_{\substack{k, \ell \geq 0 \\ k \geq k_0 \text{ ou } \ell \geq \ell_0}} \lvert e_{k,\ell} \rvert\left(\frac{\sqrt{ab}}{a^kb^\ell}\right)^n =: M_n.\]

Comme la série (4) s'obtient comme combinaison linéaire finie de la série absolument convergente (1), on conclut en particulier que \(M_1 < \infty\). Comme

\[\frac{\sqrt{ab}}{a^kb^\ell} \leq \lambda := \max\left\{\frac{\sqrt{ab}}{a^{k_0}}, \frac{\sqrt{ab}}{b^{\ell_0}}\right\} \qquad \text{pour tous } k, \ell \geq 0 \text{ tels que } k \geq k_0 \text{ ou } \ell \geq \ell_0,\]

on obtient les estimations \(M_{n+1} \leq \lambda M_n\), \(n = 1, 2, \ldots\) Notre choix de \(k_0\) et \(\ell_0\) garantit \(\lambda < 1\), ce qui implique \(M_n \to 0\) et donc \(y_n \to 0\) quand \(n \to \infty\). Il s'ensuit que \(y_n = 0\) pour tout \(n\) assez grand.

L'équation (3) se réduit donc à \(\sum_{i=0}^{k_0 \cdot \ell_0} d_ix_{n+i} = 0\). En utilisant de nouveau la théorie des récurrences linéaires, on a, pour \(n\) assez grand,

\[x_n = \sum_{k=0, \ell=0}^{k_0-1, \ell_0-1} f_{k,\ell}\left(\frac{\sqrt{ab}}{a^kb^\ell}\right)^n\]

pour certains réels \(f_{k,\ell}\). En comparant avec (2), on voit que \(f_{k,\ell} = c_{k,\ell}\) pour tous \(k, \ell \geq 0\) avec \(k < k_0\), \(\ell < \ell_0\), et que \(c_{k,\ell} = 0\) si \(k \geq k_0\) ou \(\ell \geq \ell_0\), puisqu'on a supposé \(a^\mu \neq b^\nu\) pour tous entiers \(\mu, \nu > 0\). Vu (1), cela signifie que

\[(1 - \alpha)^{\frac{1}{2}}(1 - \beta)^{\frac{1}{2}} = \sum_{k=0, \ell=0}^{k_0-1, \ell_0-1} c_{k,\ell} \cdot \alpha^k\beta^\ell \tag{5}\]

pour tous réels \(\alpha, \beta \in (0, 1)\). Choisissons \(k^* < k_0\) maximal tel qu'il existe un \(i\) avec \(c_{k^*,i} \neq 0\). En élevant (5) au carré et en identifiant les coefficients de \(\alpha^{2k^*}\beta^{2i^*}\), où \(i^*\) est maximal tel que \(c_{k^*,i^*} \neq 0\), on voit que \(k^* = 0\). Cela signifie que le membre de droite de (5) est indépendant de \(\alpha\), ce qui est évidemment impossible.

Il reste le cas où \(a^\mu = b^\nu\) pour certains entiers \(\mu, \nu > 0\). On peut supposer \(\mu\) et \(\nu\) premiers entre eux. Il existe alors un entier \(c > 0\) tel que \(a = c^\nu\) et \(b = c^\mu\). En partant du développement (2), c'est-à-dire

\[x_n = \sum_{j \geq 0} g_j\left(\frac{\sqrt{c^{\mu+\nu}}}{c^j}\right)^n\]

pour certains coefficients \(g_j\), et en reprenant les arguments ci-dessus, on voit que \(g_j = 0\) pour \(j\) assez grand, disons \(j > j_0\). Mais cela signifie que

\[(1 - x^\mu)^{\frac{1}{2}}(1 - x^\nu)^{\frac{1}{2}} = \sum_{j=0}^{j_0} g_jx^j\]

pour tout réel \(x \in (0, 1)\). En élevant au carré, on voit que

\[(1 - x^\mu)(1 - x^\nu)\]

est le carré d'un polynôme en \(x\). En particulier, toutes ses racines sont d'ordre au moins \(2\), ce qui implique \(\mu = \nu\), en considérant les racines de l'unité. On obtient donc \(\mu = \nu = 1\), c'est-à-dire \(a = b\), ce qui est une contradiction. \(\blacksquare\)

Solution 2

Posons \(a^2 = A\), \(b^2 = B\) et \(z_n = \sqrt{(A^n - 1)(B^n - 1)}\). Supposons que \(z_n\) soit entier pour \(n = 1, 2, \ldots\) Sans perte de généralité, on peut supposer \(b < a\). Déterminons un entier \(k \geq 2\) tel que \(b^{k-1} \leq a < b^k\), et définissons une suite \(\gamma_1, \gamma_2, \ldots\) de rationnels par

\[2\gamma_1 = 1 \qquad \text{et} \qquad 2\gamma_{n+1} = \sum_{i=1}^{n}\gamma_i\gamma_{n-i} \quad \text{pour } n = 1, 2, \ldots\]

On pourrait facilement montrer que \(\gamma_n = \frac{1 \cdot 1 \cdot 3 \cdots (2n - 3)}{2 \cdot 4 \cdot 6 \cdots 2n}\), par exemple en lisant la convolution de Vandermonde comme une égalité entre polynômes, mais nous n'aurons pas besoin de ce fait.

Avec la notation \(O\) de Landau usuelle, on a

\[\begin{aligned} &\left\{(ab)^n - \gamma_1\left(\frac{a}{b}\right)^n - \gamma_2\left(\frac{a}{b^3}\right)^n - \cdots - \gamma_k\left(\frac{a}{b^{2k-1}}\right)^n + O\left(\frac{b}{a}\right)^n\right\}^2 \\ &\quad = A^nB^n - 2\gamma_1A^n - \sum_{i=2}^{k}\left(2\gamma_i - \sum_{j=1}^{i-1}\gamma_j\gamma_{i-j}\right)\left(\frac{A}{B^{i-1}}\right)^n + O\left(\frac{A}{B^k}\right)^n + O(B^n) \\ &\quad = A^nB^n - A^n + O(B^n), \end{aligned}\]

d'où

\[z_n = (ab)^n - \gamma_1\left(\frac{a}{b}\right)^n - \gamma_2\left(\frac{a}{b^3}\right)^n - \cdots - \gamma_k\left(\frac{a}{b^{2k-1}}\right)^n + O\left(\frac{b}{a}\right)^n.\]

Choisissons maintenant des rationnels \(r_1, r_2, \ldots, r_{k+1}\) tels que

\[(x - ab) \cdot \left(x - \frac{a}{b}\right) \cdots \left(x - \frac{a}{b^{2k-1}}\right) = x^{k+1} - r_1x^k + - \cdots \pm r_{k+1},\]

puis un entier naturel \(M\) tel que \(Mr_1, Mr_2, \ldots, Mr_{k+1}\) soient entiers. Pour des raisons connues,

\[M(z_{n+k+1} - r_1z_{n+k} + - \cdots \pm r_{k+1}z_n) = O\left(\frac{b}{a}\right)^n\]

pour tout \(n \in \mathbb{N}\), et il existe donc un entier naturel \(N\) assez grand pour que

\[z_{n+k+1} = r_1z_{n+k} - r_2z_{n+k-1} + - \cdots \mp r_{k+1}z_n\]

pour tout \(n \geq N\). La théorie des récurrences linéaires montre alors qu'il existe des rationnels \(\delta_0, \delta_1, \delta_2, \ldots, \delta_k\) tels que

\[z_n = \delta_0(ab)^n - \delta_1\left(\frac{a}{b}\right)^n - \delta_2\left(\frac{a}{b^3}\right)^n - \cdots - \delta_k\left(\frac{a}{b^{2k-1}}\right)^n\]

pour \(n\) assez grand, où \(\delta_0 > 0\) puisque \(z_n > 0\). Comme précédemment, on obtient

\[\begin{aligned} A^nB^n - A^n - B^n + 1 = z_n^2 &= \left\{\delta_0(ab)^n - \delta_1\left(\frac{a}{b}\right)^n - \delta_2\left(\frac{a}{b^3}\right)^n - \cdots - \delta_k\left(\frac{a}{b^{2k-1}}\right)^n\right\}^2 \\ &= \delta_0^2A^nB^n - 2\delta_0\delta_1A^n - \sum_{i=2}^{k}\left(2\delta_0\delta_i - \sum_{j=1}^{i-1}\delta_j\delta_{i-j}\right)\left(\frac{A}{B^{i-1}}\right)^n + O\left(\frac{A}{B^k}\right)^n. \end{aligned}\]

Des calculs asymptotiques faciles donnent \(\delta_0 = 1\), \(\delta_1 = \frac{1}{2}\), \(\delta_i = \frac{1}{2}\sum_{j=1}^{i-1}\delta_j\delta_{i-j}\) pour \(i = 2, 3, \ldots, k - 2\), puis \(a = b^{k-1}\). Il s'ensuit que \(k > 2\) et qu'il existe un \(P \in \mathbb{Q}[X]\) tel que \((X - 1)(X^{k-1} - 1) = P(X)^2\). Mais c'est impossible, par exemple parce que \(X^{k-1} - 1\) n'a pas de racine double. Notre hypothèse selon laquelle \(z_n\) serait entier pour \(n = 1, 2, \ldots\) était donc fausse, ce qui résout le problème. \(\blacksquare\)

Formulation originale du problème

Soient \(a\), \(b\) des entiers strictement positifs tels que \(a \cdot b\) ne soit pas un carré d'entier. Montrer qu'il existe un (une infinité d') entier(s) \(n > 0\) tel(s) que \((a^n - 1)(b^n - 1)\) ne soit pas un carré d'entier.

Lemme. Soit \(c\) un entier strictement positif qui n'est pas un carré parfait. Il existe alors un nombre premier impair \(p\) tel que \(c\) ne soit pas un résidu quadratique modulo \(p\).

Preuve. En notant \(c'\) la partie sans facteur carré de \(c\), on a l'égalité \(\left(\frac{c'}{p}\right) = \left(\frac{c}{p}\right)\) des symboles de Legendre correspondants. Supposons \(c' = q_1 \cdots q_m\), où \(q_1 < \cdots < q_m\) sont premiers. On a alors

\[\left(\frac{c'}{p}\right) = \left(\frac{q_1}{p}\right) \cdots \left(\frac{q_m}{p}\right).\]

Cas 1 : \(q_1\) est impair. Choisissons un non-résidu quadratique \(r_1\) modulo \(q_1\) et des résidus quadratiques \(r_i\) modulo \(q_i\) pour \(i = 2, \ldots, m\). D'après le théorème chinois et le théorème de Dirichlet, il existe un (une infinité de) nombre(s) premier(s) \(p\) tel(s) que

\[p \equiv r_1 \pmod{q_1}, \quad p \equiv r_2 \pmod{q_2}, \quad \ldots, \quad p \equiv r_m \pmod{q_m}, \quad p \equiv 1 \pmod 4.\]

Par le choix des résidus, on obtient

\[\left(\frac{p}{q_i}\right) = \left(\frac{r_i}{q_i}\right) = \begin{cases} -1, & i = 1, \\ 1, & i = 2, \ldots, m. \end{cases}\]

La congruence \(p \equiv 1 \pmod 4\) implique \(\left(\frac{q_i}{p}\right) = \left(\frac{p}{q_i}\right)\), \(i = 1, \ldots, m\), par la loi de réciprocité quadratique. Donc

\[\left(\frac{c'}{p}\right) = \left(\frac{q_1}{p}\right) \cdots \left(\frac{q_m}{p}\right) = -1.\]

Cas 2 : \(q_1 = 2\). Choisissons des résidus quadratiques \(r_i\) modulo \(q_i\) pour \(i = 2, \ldots, m\). Là encore, d'après le théorème chinois et le théorème de Dirichlet, il existe un nombre premier \(p\) tel que

\[p \equiv r_2 \pmod{q_2}, \quad \ldots, \quad p \equiv r_m \pmod{q_m}, \quad p \equiv 5 \pmod 8.\]

Par le choix des résidus, \(\left(\frac{p}{q_i}\right) = \left(\frac{r_i}{q_i}\right) = 1\) pour \(i = 2, \ldots, m\). Comme \(p \equiv 1 \pmod 4\), on a \(\left(\frac{q_i}{p}\right) = \left(\frac{p}{q_i}\right)\), \(i = 2, \ldots, m\), par la loi de réciprocité quadratique. La congruence \(p \equiv 5 \pmod 8\) implique \(\left(\frac{2}{p}\right) = -1\). Donc

\[\left(\frac{c'}{p}\right) = \left(\frac{2}{p}\right)\left(\frac{q_2}{p}\right) \cdots \left(\frac{q_m}{p}\right) = -1,\]

et le lemme est démontré. \(\square\)

En appliquant le lemme à \(c = a \cdot b\), on trouve un nombre premier impair \(p\) tel que

\[\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \cdot \left(\frac{b}{p}\right) = -1.\]

Cela implique

\[a^{\frac{p-1}{2}} \equiv 1 \pmod p, \quad b^{\frac{p-1}{2}} \equiv -1 \pmod p, \qquad \text{ou} \qquad a^{\frac{p-1}{2}} \equiv -1 \pmod p, \quad b^{\frac{p-1}{2}} \equiv 1 \pmod p.\]

Sans perte de généralité, supposons \(a^{\frac{p-1}{2}} \equiv 1 \pmod p\) et \(b^{\frac{p-1}{2}} \equiv -1 \pmod p\). La seconde congruence implique que \(b^{\frac{p-1}{2}} - 1\) n'est pas divisible par \(p\). Donc, si l'exposant \(\nu_p\big(a^{\frac{p-1}{2}} - 1\big)\) de \(p\) dans la décomposition en facteurs premiers de \(a^{\frac{p-1}{2}} - 1\) est impair, alors \(\big(a^{\frac{p-1}{2}} - 1\big)\big(b^{\frac{p-1}{2}} - 1\big)\) n'est pas un carré parfait. Si \(\nu_p\big(a^{\frac{p-1}{2}} - 1\big)\) est pair, alors \(\nu_p\big(a^{\frac{p-1}{2}p} - 1\big)\) est impair, d'après la propriété bien connue de relèvement des exposants

\[\nu_p\left(a^{\frac{p-1}{2}p} - 1\right) = \nu_p\left(a^{\frac{p-1}{2}} - 1\right) + 1.\]

Dans ce cas, \(\big(a^{\frac{p-1}{2}p} - 1\big)\big(b^{\frac{p-1}{2}p} - 1\big)\) n'est pas un carré parfait. \(\blacksquare\)

Remarques

Remarque 1. En 1998, le problème suivant est paru dans Crux Mathematicorum : Problème 2344. Trouver tous les entiers \(N > 0\) qui sont résidus quadratiques modulo tous les nombres premiers supérieurs à \(N\). La solution publiée (Crux Mathematicorum, 25 (1999) 4) est la même que la preuve du lemme ci-dessus.

Remarque 2. Il existe aussi une preuve élémentaire du lemme. On cite le théorème 3 du chapitre 5 du livre Ireland, Rosen : A Classical Introduction to Modern Number Theory, Springer, 1982, et sa preuve.

Théorème. Soit \(a\) un entier qui n'est pas un carré. Il existe alors une infinité de nombres premiers \(p\) pour lesquels \(a\) n'est pas un résidu quadratique.

Preuve. On voit facilement qu'on peut supposer \(a\) sans facteur carré. Soit \(a = 2^eq_1q_2 \cdots q_n\), où les \(q_i\) sont des nombres premiers impairs distincts et \(e = 0\) ou \(1\). Le cas \(a = 2\) doit être traité séparément. Supposons d'abord \(n \geq 1\), c'est-à-dire que \(a\) est divisible par un nombre premier impair.

Soit \(\ell_1, \ell_2, \ldots, \ell_k\) un ensemble fini de nombres premiers impairs ne contenant aucun \(q_i\). Soit \(s\) un non-résidu quadratique modulo \(q_n\), et trouvons une solution simultanée des congruences

\[x \equiv 1 \pmod{\ell_i}, \ i = 1, \ldots, k, \qquad x \equiv 1 \pmod 8, \qquad x \equiv 1 \pmod{q_i}, \ i = 1, \ldots, n - 1, \qquad x \equiv s \pmod{q_n}.\]

Appelons \(b\) cette solution ; \(b\) est impair. Soit \(b = p_1p_2 \cdots p_m\) sa décomposition en facteurs premiers. Comme \(b \equiv 1 \pmod 8\), on a \(\left(\frac{2}{b}\right) = 1\) et \(\left(\frac{q_i}{b}\right) = \left(\frac{b}{q_i}\right)\) par un résultat sur les symboles de Jacobi. Donc

\[\left(\frac{a}{b}\right) = \left(\frac{2}{b}\right)^e\left(\frac{q_1}{b}\right) \cdots \left(\frac{q_{n-1}}{b}\right)\left(\frac{q_n}{b}\right) = \left(\frac{b}{q_1}\right) \cdots \left(\frac{b}{q_{n-1}}\right)\left(\frac{b}{q_n}\right) = \left(\frac{1}{q_1}\right) \cdots \left(\frac{1}{q_{n-1}}\right)\left(\frac{s}{q_n}\right) = -1.\]

D'autre part, par définition de \(\left(\frac{a}{b}\right)\), on a \(\left(\frac{a}{b}\right) = \left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right) \cdots \left(\frac{a}{p_m}\right)\). Il s'ensuit que \(\left(\frac{a}{p_i}\right) = -1\) pour un certain \(i\).

Remarquons que \(\ell_j\) ne divise pas \(b\). Donc \(p_i \notin \{\ell_1, \ell_2, \ldots, \ell_k\}\).

En résumé, si \(a\) n'est pas un carré et est divisible par un nombre premier impair, on a trouvé un nombre premier \(p\), hors d'un ensemble fini donné de nombres premiers \(\{2, \ell_1, \ell_2, \ldots, \ell_k\}\), tel que \(\left(\frac{a}{p}\right) = -1\). Cela prouve le théorème dans ce cas.

Il reste le cas \(a = 2\). Soit \(\ell_1, \ell_2, \ldots, \ell_k\) un ensemble fini de nombres premiers, différents de \(3\), pour lesquels \(\left(\frac{2}{\ell_i}\right) = -1\). Posons \(b = 8\ell_1\ell_2 \cdots \ell_k + 3\). Alors \(b\) n'est divisible ni par \(3\) ni par aucun \(\ell_i\). Comme \(b \equiv 3 \pmod 8\), on a \(\left(\frac{2}{b}\right) = (-1)^{\frac{b^2-1}{8}} = -1\). Soit \(b = p_1p_2 \cdots p_m\) la décomposition en facteurs premiers de \(b\). Alors, comme précédemment, \(\left(\frac{2}{p_i}\right) = -1\) pour un certain \(i\), et \(p_i \notin \{3, \ell_1, \ell_2, \ldots, \ell_k\}\). Cela prouve le théorème pour \(a = 2\).