Shortlist 2017, N6¶

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

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Descente infinie et Vieta jumping

Solution officielle : Shortlist officielle 2017 (avec solutions), p. 82 (page 84 du PDF)

Énoncé¶

Find the smallest positive integer $n$, or show that no such $n$ exists, with the following property: there are infinitely many distinct $n$-tuples of positive rational numbers $(a_1, a_2, \ldots, a_n)$ such that both

\[a_1 + a_2 + \cdots + a_n \quad\text{and}\quad \frac{1}{a_1} + \frac{1}{a_2} + \cdots + \frac{1}{a_n}\]

are integers.

Indices : les idées clés

Réponse : $n = 3$.
Divisibilité, PGCD et algorithme d'Euclide (solution 1) : pour $n = 2$, en écrivant $x = a/b$, $y = c/d$ sous forme irréductible, les conditions de divisibilité forcent $b = d$ et $a = c$.
Normaliser la somme à $1$ : quitte à diviser par la somme, il suffit de trouver des triplets d'entiers $(a, b, c)$ avec $(a+b+c)\left(\frac1a + \frac1b + \frac1c\right)$ entier.
Vieta jumping : une équation du second degré symétrique en $(b, c)$ fournit, par « saut » de racine, une infinité de solutions.
Discriminant carré parfait (solution 2) : on choisit les paramètres pour que le discriminant soit une différence de carrés imposée.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (deux solutions et deux remarques).

Réponse : $n = 3$.

Solution 1¶

Pour $n = 1$ : $a_1 \in \mathbb{Z}_{>0}$ et $\frac{1}{a_1} \in \mathbb{Z}_{>0}$ si et seulement si $a_1 = 1$. Montrons ensuite :

(i) Il n'y a qu'un nombre fini de $(x, y) \in \mathbb{Q}_{>0}^2$ tels que $x + y \in \mathbb{Z}$ et $\frac1x + \frac1y \in \mathbb{Z}$.

Écrivons $x = \frac{a}{b}$ et $y = \frac{c}{d}$ avec $a, b, c, d \in \mathbb{Z}_{>0}$ et $\operatorname{pgcd}(a, b) = \operatorname{pgcd}(c, d) = 1$. Les conditions $x + y \in \mathbb{Z}$ et $\frac1x + \frac1y \in \mathbb{Z}$ équivalent aux deux conditions de divisibilité

\[bd \mid ad + bc \quad (1) \qquad \text{et} \qquad ac \mid ad + bc \quad (2).\]

La condition (1) entraîne $d \mid ad + bc$, donc $d \mid bc$, donc $d \mid b$ puisque $\operatorname{pgcd}(c, d) = 1$. Toujours d'après (1), $b \mid ad + bc$, donc $b \mid ad$, donc $b \mid d$ puisque $\operatorname{pgcd}(a, b) = 1$. De $b \mid d$ et $d \mid b$, on tire $b = d$.

Un raisonnement analogue avec la condition (2) montre que $a = c$. Donc $x = \frac{a}{b} = \frac{c}{d} = y$, et le problème revient à trouver les $x \in \mathbb{Q}_{>0}$ tels que $2x \in \mathbb{Z}_{>0}$ et $\frac{2}{x} \in \mathbb{Z}_{>0}$. En posant $m = 2x \in \mathbb{Z}_{>0}$, on a $\frac{2}{x} = \frac{4}{m} \in \mathbb{Z}_{>0}$ si et seulement si $m = 1, 2$ ou $4$. Il n'y a donc qu'un nombre fini de solutions : $(x, y) = \left(\frac12, \frac12\right)$, $(1, 1)$ ou $(2, 2)$.

(ii) Il existe une infinité de triplets $(x, y, z) \in \mathbb{Q}_{>0}^3$ tels que $x + y + z \in \mathbb{Z}$ et $\frac1x + \frac1y + \frac1z \in \mathbb{Z}$.

(Le livret écrit $\mathbb{Q}_{>0}^2$ ; il faut lire $\mathbb{Q}_{>0}^3$.)

On cherche des triplets avec $x + y + z = 1$, que l'on peut écrire

\[(x, y, z) = \left(\frac{a}{a+b+c}, \frac{b}{a+b+c}, \frac{c}{a+b+c}\right) \quad \text{avec } a, b, c \in \mathbb{Z}_{>0}.\]

On veut

\[\frac1x + \frac1y + \frac1z = \frac{a+b+c}{a} + \frac{a+b+c}{b} + \frac{a+b+c}{c} \in \mathbb{Z} \iff \frac{b+c}{a} + \frac{a+c}{b} + \frac{a+b}{c} \in \mathbb{Z}.\]

En fixant $a = 1$, il suffit de trouver une infinité de couples $(b, c) \in \mathbb{Z}_{>0}^2$ tels que

\[\frac1b + \frac1c + \frac{c}{b} + \frac{b}{c} = 3 \iff b^2 + c^2 - 3bc + b + c = 0. \tag{$*$}\]

Pour montrer que $(*)$ a une infinité de solutions, on utilise le Vieta jumping (« saut de racine ») : partant de $b = 2$, $c = 3$, l'algorithme suivant engendre une infinité de solutions. Soit $c \geq b$ ; voyons $(*)$ comme une équation du second degré en $b$, à $c$ fixé :

\[b^2 - (3c - 1)\, b + (c^2 + c) = 0. \tag{$**$}\]

Il existe une autre racine $b_0 \in \mathbb{Z}$ de $(**)$, avec $b + b_0 = 3c - 1$ et $b \cdot b_0 = c^2 + c$. Comme $c \geq b$,

\[b_0 = \frac{c^2 + c}{b} \geq \frac{c^2 + c}{c} > c.\]

À partir de la solution $(b, c)$, on obtient donc une autre solution $(c, b_0)$ avec $b_0 > c$, et on peut sauter de nouveau, cette fois avec $c$ comme variable de $(*)$. Cet algorithme engendre une suite infinie de solutions distinctes, dont les premiers termes sont

\[(2, 3),\ (3, 6),\ (6, 14),\ (14, 35),\ (35, 90),\ (90, 234),\ (234, 611),\ (611, 1598),\ (1598, 4182),\ \ldots\]

Chacune donne un triplet $(x, y, z)$ convenable, et ces triplets sont distincts. $\blacksquare$

Solution 2¶

Appelons bons les $n$-uplets $(a_1, \ldots, a_n) \in \mathbb{Q}_{>0}^n$ vérifiant les conditions de l'énoncé, et jolis ceux pour lesquels

\[f(a_1, \ldots, a_n) := (a_1 + a_2 + \cdots + a_n)\left(\frac{1}{a_1} + \frac{1}{a_2} + \cdots + \frac{1}{a_n}\right)\]

est entier. Les bons $n$-uplets sont jolis, et si $(b_1, \ldots, b_n)$ est joli, alors

\[\left(\frac{b_1}{b_1 + \cdots + b_n}, \frac{b_2}{b_1 + \cdots + b_n}, \ldots, \frac{b_n}{b_1 + \cdots + b_n}\right)\]

est bon, car la somme de ses composantes vaut $1$ et la somme des inverses de ses composantes vaut $f(b_1, \ldots, b_n)$. On déclare équivalents les $n$-uplets jolis proportionnels : ce sont exactement ceux qui donnent le même bon $n$-uplet. Chaque classe d'équivalence contient exactement un $n$-uplet d'entiers positifs sans diviseur premier commun, que l'on appelle joli primitif. Il s'agit de trouver une infinité de $n$-uplets jolis primitifs.

Pour $n = 1$, il n'y a évidemment qu'un $1$-uplet primitif. Pour $n = 2$, $f(a, b) = \frac{(a+b)^2}{ab}$, qui ne peut être entier (pour $a, b \in \mathbb{Z}_{>0}$ premiers entre eux) que si $a = b = 1$ (voir par exemple le point (i) de la solution 1).

Construisons maintenant une infinité de triplets jolis primitifs pour $n = 3$. Fixons $b, c, k \in \mathbb{Z}_{>0}$ ; cherchons des conditions suffisantes d'existence de $a \in \mathbb{Q}_{>0}$ tel que $f(a, b, c) = k$. Posons $\sigma = b + c$ et $\tau = bc$. L'égalité $f(a, b, c) = k$ impose à $a$ l'équation du second degré

\[a^2 \sigma + a\left(\sigma^2 - (k-1)\tau\right) + \sigma\tau = 0, \tag{1}\]

de discriminant

\[\Delta = \left(\sigma^2 - (k-1)\tau\right)^2 - 4\sigma^2\tau = \left((k+1)\tau - \sigma^2\right)^2 - 4k\tau^2.\]

Il faut que ce soit le carré d'un entier, $\Delta = M^2$ avec $M \in \mathbb{Z}$, c'est-à-dire

\[\left((k+1)\tau - \sigma^2\right)^2 - M^2 = 2k \cdot 2\tau^2,\]

et il suffit pour cela de poser

\[(k+1)\tau - \sigma^2 = \tau^2 + k, \qquad M = \tau^2 - k.\]

La première relation s'écrit $\sigma^2 = (\tau - 1)(k - \tau)$. Donc, si $b$ et $c$ vérifient

\[\tau - 1 \mid \sigma^2, \quad \text{c'est-à-dire} \quad bc - 1 \mid (b + c)^2, \tag{2}\]

alors $k = \frac{\sigma^2}{\tau - 1} + \tau$ est entier, et (1) a des solutions rationnelles, à savoir

\[a = \frac{\sigma}{\tau - 1} = \frac{b + c}{bc - 1} \qquad \text{ou} \qquad a = \frac{\tau^2 - \tau}{\sigma} = \frac{bc\,(bc - 1)}{b + c}.\]

On peut alors trouver une infinité de couples $(b, c)$ vérifiant (2) par Vieta jumping. Par exemple, si l'on impose

\[(b + c)^2 = 5(bc - 1),\]

tous les couples $(b, c) = (v_i, v_{i+1})$ conviennent, où

\[v_1 = 2, \quad v_2 = 3, \quad v_{i+2} = 3v_{i+1} - v_i \quad (i \geq 1).\]

(Le livret écrit « $i \geq 0$ » ; la suite commençant à $v_1$, il faut lire $i \geq 1$.)

Pour $(b, c) = (v_i, v_{i+1})$, une des solutions de (1) est $a = \frac{b + c}{bc - 1} = \frac{5}{b + c} = \frac{5}{v_i + v_{i+1}}$. Le triplet joli $(a, b, c)$ est alors équivalent au triplet joli entier

\[\left(5,\ v_i(v_i + v_{i+1}),\ v_{i+1}(v_i + v_{i+1})\right).\]

Après une éventuelle division par $5$, on obtient une infinité de triplets jolis primitifs, comme voulu. $\blacksquare$

Remarques¶

Remarque 1 (solution 1 : formule explicite). Bien que ce ne soit pas nécessaire, on peut résoudre explicitement la récurrence donnée par le Vieta jumping. Soit $(x_n)$ définie par

\[x_0 = 2, \quad x_1 = 3, \quad x_{n+2} = 3x_{n+1} - x_n - 1 \quad (n \geq 0).\]

Alors le triplet

\[(x, y, z) = \left(\frac{1}{1 + x_n + x_{n+1}}, \frac{x_n}{1 + x_n + x_{n+1}}, \frac{x_{n+1}}{1 + x_n + x_{n+1}}\right)\]

vérifie les conditions du problème pour tout $n \in \mathbb{N}$. On montre facilement que $x_n = F_{2n+1} + 1$, où $F_n$ est la suite de Fibonacci ($F_0 = 0$, $F_1 = 1$, $F_{n+2} = F_{n+1} + F_n$).

Remarque 2 (solution 2 : d'autres suites). Il existe beaucoup d'autres suites infinies de couples $(b, c) = (v_i, v_{i+1})$ avec $bc - 1 \mid (b + c)^2$. Par exemple :

\[v_1 = 1,\ v_2 = 3,\ v_{i+1} = 6v_i - v_{i-1}, \qquad (v_i + v_{i+1})^2 = 8(v_i v_{i+1} - 1) ;\]

\[v_1 = 1,\ v_2 = 5,\ v_{i+1} = 7v_i - v_{i-1}, \qquad (v_i + v_{i+1})^2 = 9(v_i v_{i+1} - 1) ;\]

\[v_1 = 1,\ v_2 = 2,\ v_{i+1} = 7v_i - v_{i-1}, \qquad (v_i + v_{i+1})^2 = 9(v_i v_{i+1} - 1)\]

(les deux dernières sont en fait une même suite prolongée dans les deux sens possibles).