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é¶

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