Shortlist 2006, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : United States of America
Concepts : Équations diophantiennes : factorisation et encadrement · Convexité, inégalité de Jensen, lissage · Congruences, théorèmes de Fermat et d'Euler
Solution officielle : Shortlist officielle 2006 (avec solutions), p. 60 (page 61 du PDF)
Énoncé¶
Soient \(a > b > 1\) des entiers strictement positifs premiers entre eux. On appelle poids d'un entier \(c\), noté \(w(c)\), la plus petite valeur possible de \(\lvert x \rvert + \lvert y \rvert\) sur tous les couples d'entiers \(x\) et \(y\) tels que
Un entier \(c\) est appelé un champion local si \(w(c) \geq w(c \pm a)\) et \(w(c) \geq w(c \pm b)\).
Trouver tous les champions locaux et déterminer leur nombre.
Énoncé original (anglais)
Let \(a > b > 1\) be relatively prime positive integers. Define the weight of an integer \(c\), denoted by \(w(c)\), to be the minimal possible value of \(\lvert x \rvert + \lvert y \rvert\) taken over all pairs of integers \(x\) and \(y\) such that
An integer \(c\) is called a local champion if \(w(c) \geq w(c \pm a)\) and \(w(c) \geq w(c \pm b)\).
Find all local champions and determine their number.
Indices : les idées clés
- Signes opposés : dans une représentation optimale d'un champion local, \(x\) et \(y\) sont de signes opposés ; on écrit \(c = ax - by\) avec \(x, y > 0\) (équation de Bézout).
- Caractérisation : \(c\) est un champion si et seulement si \(\lvert x \rvert < b\) et \(\lvert x \rvert + \lvert y \rvert = \left\lfloor \frac{a + b}{2} \right\rfloor\) ; la convexité de \(t \mapsto \lvert x + 1 - bt \rvert + \lvert y - at \rvert\) permet de prendre \(k = 1\).
- Comptage : deux progressions arithmétiques de \(b - 1\) termes et de raison \(a + b\), confondues si \(a\), \(b\) sont impairs et disjointes modulo \(a + b\) sinon.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2006 (une solution et une remarque).
Réponse : les champions locaux sont les nombres \(\pm(ax - by)\) avec \(0 < x < b\) et \(x + y = \left\lfloor \frac{a + b}{2} \right\rfloor\) ; il y en a \(b - 1\) si \(a\) et \(b\) sont impairs, et \(2(b - 1)\) sinon.
Solution¶
On appelle représentation de \(c\) un couple d'entiers \((x, y)\) tel que \(ax + by = c\) et que \(\lvert x \rvert + \lvert y \rvert\) ait la plus petite valeur possible, c'est-à-dire \(\lvert x \rvert + \lvert y \rvert = w(c)\).
Caractérisons les champions locaux par les trois observations suivantes.
Lemme 1. Si \((x, y)\) est une représentation d'un champion local \(c\), alors \(xy < 0\).
Preuve. Supposons par l'absurde que \(x \geq 0\) et \(y \geq 0\), et considérons les valeurs \(w(c)\) et \(w(c + a)\). Toutes les écritures des nombres \(c\) et \(c + a\) sous la forme \(au + bv\) s'écrivent
où \(k\) est un entier quelconque. Comme \(\lvert x \rvert + \lvert y \rvert\) est minimal, on a
pour tout \(k\). D'autre part, \(w(c + a) \leq w(c)\), donc il existe un \(k\) tel que
Alors
En comparant le premier et le troisième membre, on trouve \(k(a - b) + 1 \leq 0\), ce qui implique \(k < 0\). En comparant le deuxième et le quatrième, on obtient \(\lvert x + 1 - kb \rvert \leq \lvert x - kb \rvert\), donc \(kb > x\) ; c'est une contradiction.
Si \(x, y \leq 0\), on se ramène au cas précédent avec \(-c\), \(-x\) et \(-y\). \(\square\)
À partir de maintenant, on écrit \(c = ax - by\) au lieu de \(c = ax + by\), et l'on ne considère que les cas où \(x\) et \(y\) sont non nuls et de même signe. D'après le lemme 1, il n'y a pas de perte de généralité.
Lemme 2. Soit \(c = ax - by\) avec \(\lvert x \rvert + \lvert y \rvert\) minimal et \(x\), \(y\) de même signe. Le nombre \(c\) est un champion local si et seulement si \(\lvert x \rvert < b\) et \(\lvert x \rvert + \lvert y \rvert = \left\lfloor \frac{a + b}{2} \right\rfloor\).
Preuve. Sans perte de généralité, on peut supposer \(x, y > 0\). Les nombres \(c - a\) et \(c + b\) s'écrivent
et l'on a trivialement \(w(c - a) \leq (x - 1) + y < w(c)\) et \(w(c + b) \leq x + (y - 1) < w(c)\) dans tous les cas.
Supposons maintenant que \(c\) soit un champion local et considérons \(w(c + a)\). Comme \(w(c + a) \leq w(c)\), il existe un entier \(k\) tel que
Cette inégalité ne peut pas être vraie si \(k \leq 0\), donc \(k > 0\). Montrons qu'on peut choisir \(k = 1\). Considérons la fonction \(f(t) = \lvert x + 1 - bt \rvert + \lvert y - at \rvert - (x + y)\). C'est une fonction convexe, et l'on a \(f(0) = 1\) et \(f(k) \leq 0\). Par l'inégalité de Jensen, \(f(1) \leq \left(1 - \frac{1}{k}\right)f(0) + \frac{1}{k}f(k) < 1\). Mais \(f(1)\) est entier. Donc \(f(1) \leq 0\) et
Sachant que \(c = a(x - b) - b(y - a)\), on a aussi
En combinant ces deux inégalités, on obtient \(\lvert x + 1 - b \rvert \leq \lvert x - b \rvert\), ce qui équivaut à \(x < b\). En considérant \(w(c - b)\), on obtient de même \(y < a\).
Maintenant, \(\lvert x - b \rvert = b - x\), \(\lvert x + 1 - b \rvert = b - x - 1\) et \(\lvert y - a \rvert = a - y\), donc on a
Donc \(x + y = \left\lfloor \frac{a + b}{2} \right\rfloor\).
Pour la réciproque, supposons \(0 < x < b\) et \(x + y = \left\lfloor \frac{a + b}{2} \right\rfloor\). Comme \(a > b\), on a aussi \(0 < y < a\). Alors
et
donc \(c\) est bien un champion local. \(\square\)
Lemme 3. Soit \(c = ax - by\), avec \(x\) et \(y\) de même signe, \(\lvert x \rvert < b\), \(\lvert y \rvert < a\) et \(\lvert x \rvert + \lvert y \rvert = \left\lfloor \frac{a + b}{2} \right\rfloor\). Alors \(w(c) = x + y\).
Preuve. Par définition, \(w(c) = \min\{\lvert x - kb \rvert + \lvert y - ka \rvert : k \in \mathbb{Z}\}\). Si \(k \leq 0\), alors évidemment \(\lvert x - kb \rvert + \lvert y - ka \rvert \geq x + y\). Si \(k \geq 1\), alors
Donc \(w(c) = x + y\). \(\square\)
Les lemmes 1, 2 et 3 donnent ensemble que l'ensemble des champions locaux est
Notons \(C^+\) et \(C^-\) les deux ensembles engendrés par les expressions \(+(ax - by)\) et \(-(ax - by)\) respectivement. On voit facilement que ces deux ensembles sont des progressions arithmétiques de longueur \(b - 1\) et de raison \(a + b\).
Si \(a\) et \(b\) sont impairs, alors \(C^+ = C^-\), car \(a(-x) - b(-y) = a(b - x) - b(a - y)\) et \(x + y = \frac{a + b}{2}\) équivaut à \((b - x) + (a - y) = \frac{a + b}{2}\). Dans ce cas, il y a \(b - 1\) champions locaux.
Si \(a\) et \(b\) sont de parités différentes, la réponse est différente. Pour tous \(c_1 \in C^+\) et \(c_2 \in C^-\),
et
Le nombre \(a + b\) est impair et premier avec \(a\) ; les éléments de \(C^+\) et de \(C^-\) appartiennent donc à deux classes de restes différentes modulo \(a + b\). L'ensemble \(C\) est donc la réunion de deux progressions arithmétiques disjointes, et le nombre total de champions locaux est \(2(b - 1)\).
Le nombre de champions locaux est donc \(b - 1\) si \(a\) et \(b\) sont tous deux impairs, et \(2(b - 1)\) sinon. \(\blacksquare\)
Remarque¶
La question originale, telle que posée par le proposant, était : (a) montrer qu'il n'y a qu'un nombre fini de champions locaux ; (b) montrer qu'il existe au moins un champion local.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2022 N4 ★★☆☆☆ · OIM P5 : Résoudre \(a^p = b! + p\) avec \(p\) premier.
- 2012 N2 ★★☆☆☆ : Résoudre en entiers \(x^3(y^3 + z^3) = 2012(xyz + 2)\).
- 2015 N5 ★★★☆☆ · OIM P2 : Trouver les triplets pour lesquels \(ab - c\), \(bc - a\) et \(ca - b\) sont tous des puissances de \(2\).
- 2025 N8 ★★★★★ : Seul un nombre fini de premiers \(p\) ont \(p - 8\) carré et tous les \(p - k^2\) (\(k\) impair, \(k < \sqrt{p}\)) avec au plus deux facteurs premiers.