Aller au contenu

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

\[ax + by = c.\]

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

\[ax + by = c.\]

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

\[c = a(x - kb) + b(y + ka), \qquad c + a = a(x + 1 - kb) + b(y + ka),\]

où \(k\) est un entier quelconque. Comme \(\lvert x \rvert + \lvert y \rvert\) est minimal, on a

\[x + y = \lvert x \rvert + \lvert y \rvert \leq \lvert x - kb \rvert + \lvert y + ka \rvert\]

pour tout \(k\). D'autre part, \(w(c + a) \leq w(c)\), donc il existe un \(k\) tel que

\[\lvert x + 1 - kb \rvert + \lvert y + ka \rvert \leq \lvert x \rvert + \lvert y \rvert = x + y.\]

Alors

\[(x + 1 - kb) + (y + ka) \leq \lvert x + 1 - kb \rvert + \lvert y + ka \rvert \leq x + y \leq \lvert x - kb \rvert + \lvert y + ka \rvert.\]

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

\[c - a = a(x - 1) - by \qquad \text{et} \qquad c + b = ax - b(y - 1),\]

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

\[c + a = a(x + 1 - kb) - b(y - ka) \qquad \text{et} \qquad \lvert x + 1 - kb \rvert + \lvert y - ka \rvert \leq x + y.\]

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

\[\lvert x + 1 - b \rvert + \lvert y - a \rvert \leq x + y.\]

Sachant que \(c = a(x - b) - b(y - a)\), on a aussi

\[x + y \leq \lvert x - b \rvert + \lvert y - a \rvert.\]

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

\[(b - x - 1) + (a - y) \leq x + y \leq (b - x) + (a - y), \qquad \frac{a + b - 1}{2} \leq x + y \leq \frac{a + b}{2}.\]

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

\[w(c + a) \leq \lvert x + 1 - b \rvert + \lvert y - a \rvert = a + b - 1 - (x + y) \leq x + y = w(c)\]

et

\[w(c - b) \leq \lvert x - b \rvert + \lvert y + 1 - a \rvert = a + b - 1 - (x + y) \leq x + y = w(c),\]

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

\[\lvert x - kb \rvert + \lvert y - ka \rvert = (kb - x) + (ka - y) = k(a + b) - (x + y) \geq (2k - 1)(x + y) \geq x + y.\]

Donc \(w(c) = x + y\). \(\square\)

Les lemmes 1, 2 et 3 donnent ensemble que l'ensemble des champions locaux est

\[C = \left\{\pm(ax - by) : 0 < x < b, \ x + y = \left\lfloor \frac{a + b}{2} \right\rfloor\right\}.\]

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

\[2c_1 \equiv -2c_2 \equiv 2\left(a\frac{a + b - 1}{2} - b \cdot 0\right) \equiv -a \pmod{a + b}\]

et

\[2c_1 - 2c_2 \equiv -2a \pmod{a + b}.\]

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.