Aller au contenu

Shortlist 2015, N5

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

Concepts : Équations diophantiennes : factorisation et encadrement · Valuations p-adiques et lemme LTE · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2015 (avec solutions), p. 70 (page 71 du PDF)

Problème 2 de l'OIM 2015

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2015, où il était le problème 2 (jour 1).

Énoncé

Determine all triples \((a, b, c)\) of positive integers for which \(ab - c\), \(bc - a\), and \(ca - b\) are powers of \(2\).

Explanation: A power of \(2\) is an integer of the form \(2^n\), where \(n\) denotes some nonnegative integer.

Indices : les idées clés
  • Encadrement : en ordonnant \(a < b < c\), une puissance de \(2\) divisible par \(2^\beta\) et majorée force \(a\) à être très petit (\(a = 2\) ou \(a = 3\)).
  • Valuations 2-adiques : comparer la plus grande puissance de \(2\) dans des combinaisons comme \((b + a\vartheta)(c - \vartheta)\) (solution 1) ou \((ab-2)(a+b)\) (solution 2).
  • Congruences modulo 4 : une puissance de \(2\) n'est pas \(\equiv -1 \pmod 4\) ; parmi \(b+a\) et \(b-a\) (\(a\) impair), un seul est divisible par \(4\).
  • Étude des parités (solution 2) : tous pairs, tous impairs, ou parités mélangées.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (deux solutions et une remarque).

Réponse. Il y a seize triplets : \((2, 2, 2)\), les trois permutations de \((2, 2, 3)\), et les six permutations de chacun des triplets \((2, 6, 11)\) et \((3, 5, 7)\).

Solution 1

On vérifie facilement que ces seize triplets conviennent. Soit maintenant \((a, b, c)\) un triplet ayant la propriété voulue. Si \(a = 1\), alors \(b - c\) et \(c - b\) seraient tous deux des puissances de \(2\), ce qui est impossible car leur somme est nulle ; par symétrie, \(a, b, c \geq 2\).

Cas 1 : deux des nombres sont égaux. Supposons \(a = b\). Alors \(a^2 - c\) et \(a(c - 1)\) sont des puissances de \(2\). La seconde condition montre que \(a\) et \(c - 1\) sont des puissances de \(2\) : \(a = 2^\alpha\) et \(c = 2^\gamma + 1\). Comme \(a^2 - c = 2^{2\alpha} - 2^\gamma - 1\) est une puissance de \(2\), elle n'est pas congrue à \(-1\) modulo \(4\), donc \(\gamma \leq 1\). De plus, \(2^{2\alpha} - 2\) et \(2^{2\alpha} - 3\) ne peuvent être des puissances de \(2\) que si \(\alpha = 1\). Donc \((a, b, c) = (2, 2, 2)\) ou \((2, 2, 3)\).

Cas 2 : \(a\), \(b\), \(c\) sont distincts. Par symétrie, on suppose

\[2 \leq a < b < c. \tag{1}\]

Il faut montrer que \((a, b, c)\) est \((2, 6, 11)\) ou \((3, 5, 7)\). Il existe des entiers \(\alpha, \beta, \gamma \geq 0\) tels que

\[bc - a = 2^\alpha, \tag{2}\]
\[ac - b = 2^\beta, \tag{3}\]
\[ab - c = 2^\gamma. \tag{4}\]

Évidemment

\[\alpha > \beta > \gamma. \tag{5}\]

Cas 2.1 : \(a = 2\). Montrons d'abord que \(\gamma = 0\). Sinon \(\gamma > 0\), donc \(c\) est pair par (4), et \(b\) est pair par (5) et (3). Le membre de gauche de (2) est alors congru à \(2\) modulo \(4\), ce qui n'est possible que si \(bc = 4\), contredisant (1). Donc \(\gamma = 0\), c'est-à-dire \(c = 2b - 1\).

Alors (3) donne \(3b - 2 = 2^\beta\). Comme \(b > 2\), cela impose \(\beta \geq 4\). Si \(\beta = 4\), on obtient \(b = 6\) et \(c = 11\), qui est une solution. Reste le cas \(\beta \geq 5\). Alors (2) donne

\[9 \cdot 2^\alpha = 9b(2b - 1) - 18 = (3b - 2)(6b + 1) - 16 = 2^\beta\left(2^{\beta+1} + 5\right) - 16,\]

et comme \(\beta \geq 5\), le membre de droite n'est pas divisible par \(32\). Donc \(\alpha \leq 4\), ce qui contredit (5).

Cas 2.2 : \(a \geq 3\). Choisissons \(\vartheta \in \{-1, +1\}\) tel que \(c - \vartheta\) ne soit pas divisible par \(4\). Alors

\[2^\alpha + \vartheta \cdot 2^\beta = (bc - a\vartheta^2) + \vartheta(ca - b) = (b + a\vartheta)(c - \vartheta)\]

est divisible par \(2^\beta\), donc (valuations 2-adiques) \(b + a\vartheta\) est divisible par \(2^{\beta - 1}\). D'autre part, \(2^\beta = ac - b > (a - 1)c \geq 2c\) entraîne, avec (1), que \(a\) et \(b\) sont inférieurs à \(2^{\beta - 1}\). Tout cela n'est possible que si \(\vartheta = 1\) et \(a + b = 2^{\beta - 1}\). Alors (3) donne

\[ac - b = 2(a + b), \tag{6}\]

d'où \(4b > a + 3b = a(c - 1) \geq ab\), ce qui impose \(a = 3\).

Alors (6) se simplifie en \(c = b + 2\), et (2) dit que \(b(b+2) - 3 = (b - 1)(b + 3)\) est une puissance de \(2\). Donc \(b - 1\) et \(b + 3\) sont des puissances de \(2\) ; leur différence étant \(4\), on a \(b = 5\), d'où \(c = 7\). \(\blacksquare\)

Solution 2

Comme au début de la solution 1, \(a, b, c \geq 2\). On distingue trois cas selon les parités.

Cas 1 : \(a\), \(b\), \(c\) sont pairs. Soient \(2^A\), \(2^B\), \(2^C\) les plus grandes puissances de \(2\) divisant \(a\), \(b\), \(c\) ; on peut supposer \(1 \leq A \leq B \leq C\). Alors \(2^B\) est la plus grande puissance de \(2\) divisant \(ac - b\), donc \(ac - b = 2^B \leq b\). De même \(bc - a = 2^A \leq a\). En additionnant, \((a + b)c \leq 2(a + b)\), donc \(c \leq 2\). Ainsi \(c = 2\), \(A = B = C = 1\), et toutes les inégalités sont des égalités : \(a = 2\), \(b = 2\). On trouve la solution \((2, 2, 2)\).

Cas 2 : \(a\), \(b\), \(c\) sont impairs. Si deux d'entre eux sont égaux, disons \(a = b\), alors \(ac - b = a(c - 1)\) a un diviseur impair non trivial : impossible. Donc ils sont distincts, et on peut supposer \(a < b < c\). Soient \(\alpha\), \(\beta\) tels que \(bc - a = 2^\alpha\) et \(ac - b = 2^\beta\). On a \(\alpha > \beta\), donc \(2^\beta\) divise

\[a \cdot 2^\alpha - b \cdot 2^\beta = a(bc - a) - b(ac - b) = b^2 - a^2 = (b + a)(b - a).\]

Comme \(a\) est impair, \(b + a\) et \(b - a\) ne sont pas tous deux divisibles par \(4\). L'un d'eux est donc multiple de \(2^{\beta - 1}\), donc l'un des nombres \(2(b + a)\), \(2(b - a)\) est divisible par \(2^\beta\), et dans les deux cas

\[ac - b = 2^\beta \leq 2(a + b). \tag{7}\]

Ainsi \((a - 1)b < ac - b < 4b\), d'où \(a = 3\) (\(a\) impair et \(a > 1\)). En reportant dans (7), \(c \leq b + 2\). Mais par parité, \(b < c\) entraîne \(b + 2 \leq c\). Donc \(c = b + 2\), et comme \(bc - a = (b - 1)(b + 3)\) est une puissance de \(2\), on obtient \(b = 5\) et \(c = 7\).

Cas 3 : les deux parités apparaissent. On suppose \(c\) impair et \(a \leq b\) ; il faut montrer que \((a, b, c)\) est \((2, 2, 3)\) ou \((2, 6, 11)\). Comme \(a\) ou \(b\) est pair, \(ab - c\) est impair ; c'est une puissance de \(2\), donc

\[ab - c = 1. \tag{8}\]

Si \(a = b\), alors \(c = a^2 - 1\), et \(ac - b = a(a^2 - 2)\) est une puissance de \(2\), donc \(a\) et \(a^2 - 2\) aussi, d'où \(a = 2\) : solution \((2, 2, 3)\).

Supposons désormais \(a < b\), et soient \(\alpha > \beta\) tels que

\[2^\alpha = bc - a \qquad \text{et} \qquad 2^\beta = ac - b. \tag{9}\]

Si \(\beta = 0\), on aurait \(ac - b = ab - c = 1\), d'où \(b = c = 1\) : absurde. Donc \(\alpha\) et \(\beta\) sont positifs, et \(a\), \(b\) sont pairs. En remplaçant \(c = ab - 1\) dans (9) :

\[2^\alpha = ab^2 - (a + b), \tag{10}\]
\[2^\beta = a^2 b - (a + b). \tag{11}\]

En additionnant, \(2^\alpha + 2^\beta = (ab - 2)(a + b)\). Or \(ab - 2\) est pair mais pas divisible par \(4\), donc la plus grande puissance de \(2\) divisant \(a + b\) est \(2^{\beta - 1}\). Par (10) et (11), la plus grande puissance de \(2\) divisant \(ab^2\), et celle divisant \(a^2 b\), sont aussi \(2^{\beta - 1}\). Il existe donc un entier \(\tau \geq 1\) et des entiers impairs \(A\), \(B\), \(C\) tels que

\[a = 2^\tau A, \quad b = 2^\tau B, \quad a + b = 2^{3\tau} C, \quad \beta = 1 + 3\tau.\]

On a \(A + B = 2^{2\tau} C \geq 4C\). De plus, (11) donne \(A^2 B - C = 2\). Donc

\[8 = 4A^2 B - 4C \geq 4A^2 B - A - B \geq A^2(3B - 1).\]

Comme \(A < B\) sont impairs, cela impose \(A = 1\) et \(B = 3\). On conclut \(C = 1\), \(\tau = 1\), \(a = 2\), \(b = 6\), \(c = 11\) : le triplet \((2, 6, 11)\). Ceci achève le cas 3 et la solution. \(\blacksquare\)

Remarques

Remarque (autre traitement du sous-cas \(a < b\) du cas 3 de la solution 2). On part de (8) et (9). Soit \(d = \gcd(a, b)\), \(a = dp\), \(b = dq\), avec \(p < q\) et \(\gcd(p, q) = 1\). Par (8), \(c = d^2 pq - 1\), donc

\[2^\alpha = d(d^2 pq^2 - p - q) \qquad \text{et} \qquad 2^\beta = d(d^2 p^2 q - p - q). \tag{12}\]

Alors \(2^\beta\) divise \(2^\alpha - 2^\beta = d^3 pq(q - p)\) ; comme \(p\) et \(q\) sont premiers avec \(d^2 p^2 q - p - q\),

\[(d^2 p^2 q - p - q) \mid d^2 (q - p). \tag{13}\]

En particulier \(d^2 p^2 q - p - q \leq d^2(q - p)\), soit \(d^2(p^2 q + p - q) \leq p + q\). Comme \(p^2 q + p - q > 0\), on en déduit \(p^2 q + p - q \leq p + q\), donc \(p^2 q \leq 2q\) et \(p = 1\). Alors (13) devient

\[(d^2 q - q - 1) \mid d^2 (q - 1). \tag{14}\]

Si \(2(d^2 q - q - 1) \leq d^2(q - 1)\), on aurait \(d^2(q + 1) \leq 2(q + 1)\), donc \(d = 1\) et \(a = 1\) : absurde. Donc \(2(d^2 q - q - 1) > d^2(q - 1)\) et (14) impose \(d^2 q - q - 1 = d^2(q - 1)\), soit \(q = d^2 - 1\). Dans (12), \(2^\beta = d^3(d^2 - 2)\), donc \(d\) et \(d^2 - 2\) sont des puissances de \(2\) : \(d = 2\), \(q = 3\), \(a = 2\), \(b = 6\), \(c = 11\).