Aller au contenu

Shortlist 2016, N5

Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : non indiqué

Concepts : Descente infinie et Vieta jumping · Équations diophantiennes : factorisation et encadrement · Principe extrémal

Solution officielle : Shortlist officielle 2016 (avec solutions), p. 79 (page 82 du PDF)

Énoncé

Soit \(a\) un entier strictement positif qui n'est pas un carré parfait. On note \(A\) l'ensemble des entiers \(k\) strictement positifs tels que

\[k = \frac{x^2 - a}{x^2 - y^2} \tag{1}\]

pour des entiers \(x\) et \(y\) avec \(x > \sqrt{a}\), et \(B\) l'ensemble des entiers \(k\) strictement positifs tels que (1) soit vérifiée pour des entiers \(x\) et \(y\) avec \(0 \leq x < \sqrt{a}\). Montrer que \(A = B\).

Énoncé original (anglais)

Let \(a\) be a positive integer which is not a square number. Denote by \(A\) the set of all positive integers \(k\) such that

\[k = \frac{x^2 - a}{x^2 - y^2} \tag{1}\]

for some integers \(x\) and \(y\) with \(x > \sqrt{a}\). Denote by \(B\) the set of all positive integers \(k\) such that (1) is satisfied for some integers \(x\) and \(y\) with \(0 \leq x < \sqrt{a}\). Prove that \(A = B\).

Indices : les idées clés
  • Vieta jumping (solutions 1 et 3) : avec \(u = x+y\), \(v = x-y\), la relation (1) devient une équation du second degré symétrique en \(u, v\) ; l'autre racine fournit une nouvelle solution.
  • Équations diophantiennes (solution 2) : (1) s'écrit \(ky^2 - (k-1)x^2 = a\), équation de type Pell, et on fabrique de nouvelles solutions par une transformation linéaire.
  • Principe extrémal (solution 1) : parmi les représentations avec \(x > \sqrt a\), on prend celle qui minimise \(x + y\) (descente).
  • Monter et descendre : une même transformation permet d'augmenter \(|x|\) (pour \(B \subset A\)) ou de le diminuer (pour \(A \subset B\)).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2016 (trois solutions).

Solution 1

Lemme. Pour \(k\) fixé, soient \(x, y\) des entiers vérifiant (1). Alors les nombres

\[x_1 = \frac12\left(x - y + \frac{(x-y)^2 - 4a}{x+y}\right), \qquad y_1 = \frac12\left(x - y - \frac{(x-y)^2 - 4a}{x+y}\right)\]

sont des entiers et vérifient (1) (avec \(x, y\) remplacés par \(x_1, y_1\)).

Preuve. On a \(x_1 + y_1 = x - y\) et

\[x_1 = \frac{x^2 - xy - 2a}{x+y} = -x + \frac{2(x^2 - a)}{x+y} = -x + 2k(x-y),\]

donc \(x_1\) et \(y_1\) sont des entiers. Posons \(u = x + y\) et \(v = x - y\). La relation (1) se réécrit

\[u^2 - (4k-2)uv + (v^2 - 4a) = 0.\]

D'après les relations de Viète (c'est le principe du Vieta jumping), le nombre \(z = \frac{v^2 - 4a}{u}\) vérifie aussi

\[v^2 - (4k-2)vz + (z^2 - 4a) = 0.\]

Comme \(x_1, y_1\) sont définis de sorte que \(v = x_1 + y_1\) et \(z = x_1 - y_1\), on peut remonter les calculs et vérifier (1) pour \(x_1, y_1\). \(\square\)

Montrons \(B \subset A\). Soit \(k \in B\) : (1) est vérifiée pour des entiers \(x, y\) avec \(0 \leq x < \sqrt a\). Clairement \(y \neq 0\) et on peut supposer \(y > 0\). Comme \(a\) n'est pas un carré, \(k > 1\) ; on en déduit \(0 \leq x < y < \sqrt a\). Posons

\[x_1 = \frac12\left|x - y + \frac{(x-y)^2 - 4a}{x+y}\right|, \qquad y_1 = \frac12\left(x - y - \frac{(x-y)^2 - 4a}{x+y}\right).\]

D'après le lemme (et puisque (1) ne dépend que de \(x^2\)), \(x_1, y_1\) sont des entiers vérifiant (1). De plus,

\[x_1 \geq -\frac12\left(x - y + \frac{(x-y)^2 - 4a}{x+y}\right) = \frac{2a + x(y-x)}{x+y} \geq \frac{2a}{x+y} > \sqrt a,\]

la dernière inégalité venant de \(x + y < 2\sqrt a\). Donc \(k \in A\), et \(B \subset A\).

Montrons \(A \subset B\). Soit \(k \in A\) : (1) est vérifiée pour des entiers \(x, y\) avec \(x > \sqrt a\). Là encore on peut supposer \(y > 0\). Par le principe extrémal, on choisit, parmi toutes ces représentations de \(k\), celle pour laquelle \(x + y\) est minimal. On définit \(x_1, y_1\) par les mêmes formules (avec la valeur absolue pour \(x_1\)) ; d'après le lemme ce sont des entiers vérifiant (1). Comme \(k > 1\), on a \(x > y > \sqrt a\). Alors

\[y_1 = \frac{(x-y)y + 2a}{x+y} > 0 \qquad \text{et} \qquad \frac{4a}{x+y} < x + y.\]

Le livret écrit \(y_1 > \frac{4a}{x+y}\) ; le calcul donne en fait \(y_1 = \frac{(x-y)y+2a}{x+y}\), et seule la positivité \(y_1 > 0\) sert dans la suite.

Selon le signe de la quantité dans la valeur absolue, \(x_1 + y_1\) vaut \(x - y\) ou \(\frac{4a - (x-y)^2}{x+y}\), d'où

\[x_1 + y_1 \leq \max\left\{x - y,\ \frac{4a - (x-y)^2}{x+y}\right\} < x + y.\]

Si l'on avait \(x_1 > \sqrt a\), cela contredirait la minimalité de \(x + y\). Donc \(0 \leq x_1 < \sqrt a\) (l'égalité est impossible car \(a\) n'est pas un carré), c'est-à-dire \(k \in B\). Ainsi \(A \subset B\).

Les deux inclusions donnent \(A = B\). \(\blacksquare\)

Solution 2

La relation (1) équivaut à

\[ky^2 - (k-1)x^2 = a. \tag{2}\]

En s'inspirant de l'équation de Pell, on montre le résultat suivant, qui est au fond le même que le lemme de la solution 1.

Lemme. Si \((x_0, y_0)\) est une solution de (2), alors

\[\big((2k-1)x_0 \pm 2ky_0,\ (2k-1)y_0 \pm 2(k-1)x_0\big)\]

est aussi une solution de (2).

Preuve. On vérifie directement :

\[\begin{aligned} &k\big((2k-1)y_0 \pm 2(k-1)x_0\big)^2 - (k-1)\big((2k-1)x_0 \pm 2ky_0\big)^2 \\ &= \big(k(2k-1)^2 - (k-1)(2k)^2\big)y_0^2 + \big(k(2(k-1))^2 - (k-1)(2k-1)^2\big)x_0^2 \\ &= ky_0^2 - (k-1)x_0^2 = a, \end{aligned}\]

les termes croisés s'annulant (ils valent \(\pm 4k(k-1)(2k-1)x_0y_0\) des deux côtés). \(\square\)

\(B \subset A\). Supposons (2) vérifiée avec \(0 \leq x < \sqrt a\) et \(y\) entier positif ou nul. Alors (1) impose \(y > x\), et \(k > 1\) car \(a\) n'est pas un carré. D'après le lemme, on a une autre solution de (2) :

\[x_1 = (2k-1)x + 2ky, \qquad y_1 = (2k-1)y + 2(k-1)x.\]

Elle vérifie \(x_1 \geq (2k-1)x + 2k(x+1) = (4k-1)x + 2k > x\). On remplace donc l'ancienne solution par une nouvelle de plus grand \(x\) ; après un nombre fini de remplacements, on obtient une solution avec \(x > \sqrt a\). Donc \(B \subset A\).

\(A \subset B\). Supposons (2) vérifiée avec \(x > \sqrt a\) et \(y \geq 0\) entier. D'après le lemme, on considère la solution

\[x_1 = \big|(2k-1)x - 2ky\big|, \qquad y_1 = (2k-1)y - 2(k-1)x.\]

D'après (2), \(\sqrt k\, y > \sqrt{k-1}\, x\), donc \(ky > \sqrt{k(k-1)}\, x > (k-1)x\), d'où \((2k-1)x - 2ky < x\). D'autre part, (1) impose \(x > y\), d'où clairement \((2k-1)x - 2ky > -x\). Ainsi \(x_1 < x\) : on a trouvé une solution de (2) avec une valeur absolue de \(x\) plus petite. Après un nombre fini d'étapes, on obtient une solution avec \(0 \leq x < \sqrt a\). Donc \(A \subset B\).

On conclut que \(A = B\). \(\blacksquare\)

Solution 3

Il suffit de montrer que \(A \cup B \subset A \cap B\). Soit \(k \in A \cup B\) : il existe des entiers \(x, y\) vérifiant (1). Comme \(a\) n'est pas un carré, \(k \neq 1\). Comme dans la solution 2, le résultat découle de l'existence d'une solution \((x_1, y_1)\) de (1) avec \(|x_1| > |x|\) et, dans le cas \(x > \sqrt a\), d'une autre solution \((x_2, y_2)\) avec \(|x_2| < |x|\).

Sans perte de généralité, \(x, y \geq 0\). Posons \(u = x + y\) et \(v = x - y\). Alors \(u \geq v\) et (1) devient

\[k = \frac{(u+v)^2 - 4a}{4uv}, \tag{3}\]

ce qui s'écrit

\[v^2 + (2u - 4ku)v + u^2 - 4a = 0.\]

Augmenter \(x\). Posons \(v_1 = 4ku - 2u - v\). Alors \(u + v_1 = 4ku - u - v \geq 8u - u - v > u + v\). Par le théorème de Viète, \(v_1\) vérifie

\[v_1^2 + (2u - 4ku)v_1 + u^2 - 4a = 0,\]

ce qui donne \(k = \frac{(u + v_1)^2 - 4a}{4uv_1}\). Comme \(k\) est entier, \(u + v_1\) est pair. Donc \(x_1 = \frac{u + v_1}{2}\) et \(y_1 = \frac{v_1 - u}{2}\) sont des entiers ; en remontant les calculs, \((x_1, y_1)\) est solution de (1), avec \(x_1 = \frac{u+v_1}{2} > \frac{u+v}{2} = x \geq 0\). Ceci termine la première moitié de la preuve.

Diminuer \(x\). Supposons \(x > \sqrt a\). Alors \(u + v > 2\sqrt a\) et (3) se réécrit

\[u^2 + (2v - 4kv)u + v^2 - 4a = 0.\]

Posons \(u_2 = 4kv - 2v - u\). Par le théorème de Viète, \(uu_2 = v^2 - 4a\) et

\[u_2^2 + (2v - 4kv)u_2 + v^2 - 4a = 0. \tag{4}\]

Comme \(u > 0\), \(u + v > 2\sqrt a\) et (3), on a \(v > 0\). Si \(u_2 \geq 0\), alors \(vu_2 \leq uu_2 = v^2 - 4a < v^2\) ; donc \(u_2 < v \leq u\) et \(0 < u_2 + v < u + v\). Si \(u_2 < 0\), alors \((u_2 + v) + (u + v) = 4kv > 0\) et \(u_2 + v < u + v\) entraînent \(|u_2 + v| < u + v\). Dans tous les cas, \(u_2 + v\) est pair d'après (4), et on peut poser \(x_2 = \frac{u_2 + v}{2}\), \(y_2 = \frac{u_2 - v}{2}\) : (1) est vérifiée avec \(|x_2| < x\), comme voulu. \(\blacksquare\)

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2009 N4 ★★★☆☆ : Pour quelles longueurs \(n\) la récurrence \(a_{k+1} = (a_k^2 + 1)/(a_{k-1} + 1) - 1\) peut-elle rester entière ?
  • 2007 N6 ★★★☆☆ · OIM P5 : \((4k^2 - 1)^2\) a un diviseur de la forme \(8kn - 1\) si et seulement si \(k\) est pair.
  • 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\).
  • 2019 N8 ★★★★★ : Le nombre \(a^2 + \lceil 4a^2/b \rceil\) n'est jamais un carré.