Exercice 27

1. Les petits entiers se testent un par un. Les entiers $0$, $3$, $5$, $6$, $8 = 3 + 5$, $9$ et $10$ sont réalisables, tandis que $1$, $2$, $4$ et $7$ ne le sont pas : pour $7$, les valeurs possibles $v = 0$ et $v = 1$ laissent $7$ ou $2$, qui ne sont pas multiples de $3$. Montrons que tout entier $n \geqslant 8$ est réalisable, par récurrence forte : c'est vrai pour $8$, $9$ et $10$, et pour $n \geqslant 11$, l'entier $n - 3 \geqslant 8$ est réalisable par hypothèse, donc $n$ aussi, en ajoutant un timbre de $3$. $$\boxed{\text{Les entiers réalisables sont ceux de } \mathbb{N} \setminus \{1\,,2\,,4\,,7\}.}$$

2. Si $d = \mathrm{pgcd}(a,b) \geqslant 2$, tout entier réalisable $au + bv$ est divisible par $d$. Les entiers $kd + 1$, pour $k \in \mathbb{N}$, ne sont donc jamais réalisables. $$\boxed{\text{Il y a une infinité d'entiers non réalisables.}}$$ On suppose désormais $a$ et $b$ premiers entre eux, et l'on pose $g = ab - a - b$.

3. On montre que $g$ est le plus grand entier non réalisable.

L'entier $g$ n'est pas réalisable. Supposons $g = au + bv$ avec $u$, $v$ entiers naturels. Alors $ab = a(u + 1) + b(v + 1)$. Ainsi $a$ divise $b(v + 1)$, et comme $a$ est premier avec $b$, le lemme de Gauss donne $a \mid v + 1$ ; comme $v + 1 \geqslant 1$, on a $v + 1 \geqslant a$. De même $u + 1 \geqslant b$. Mais alors $a(u+1) + b(v+1) \geqslant ab + ab > ab$ : contradiction.

Tout entier $n > g$ est réalisable. Par le théorème de Bézout, il existe $(u_{0}, v_{0}) \in \mathbb{Z}^{2}$ tel que $au_{0} + bv_{0} = 1$, donc $n = a(nu_{0}) + b(nv_{0})$. Pour tout $k \in \mathbb{Z}$, on a aussi $n = a(nu_{0} - kb) + b(nv_{0} + ka)$. La division euclidienne de $nu_{0}$ par $b$ fournit un entier $k$ tel que $u = nu_{0} - kb$ appartienne à $[\![0\,;b - 1]\!]$. L'entier $v = \frac{n - au}{b}$ vérifie alors $$v \geqslant \frac{n - a(b-1)}{b} > \frac{g - ab + a}{b} = \frac{-b}{b} = -1,$$ donc $v \geqslant 0$, puisque $v$ est entier. $$\boxed{\text{Le plus grand entier non réalisable est } ab - a - b.}$$ Pour $a = 3$ et $b = 5$, on retrouve $15 - 3 - 5 = 7$. ✓

4. Montrons que, pour tout $n \in [\![0\,;g]\!]$, exactement un des deux entiers $n$ et $g - n$ est réalisable.

• Ils ne le sont pas tous les deux : sinon leur somme $g$ le serait, en additionnant les deux écritures.

• L'un des deux l'est : comme à la question 3, on écrit $n = au + bv$ avec $u \in [\![0\,;b-1]\!]$ et $v \in \mathbb{Z}$. Si $v \geqslant 0$, l'entier $n$ est réalisable. Sinon $v \leqslant -1$, et $g - n = a(b - 1 - u) + b(-1 - v)$, avec $b - 1 - u \geqslant 0$ et $-1 - v \geqslant 0$ : c'est $g - n$ qui est réalisable.

En associant à chaque entier $n$ de $[\![0\,;g]\!]$ l'entier $g - n$, on échange donc les entiers réalisables et non réalisables de cet intervalle : il y en a autant des uns que des autres. Comme l'intervalle contient $g + 1$ entiers et qu'il n'y a aucun entier non réalisable au-delà de $g$ : $$\boxed{\text{Il y a exactement } \frac{g + 1}{2} = \frac{(a-1)(b-1)}{2} \text{ entiers non réalisables.}}$$ Pour $a = 3$ et $b = 5$, on trouve $\frac{2 \times 4}{2} = 4$, ce qui correspond bien à $\{1\,,2\,,4\,,7\}$. ✓

À retenir : cet exercice est le « problème des pièces » de Frobenius, et le dénombrement de la question 4 est un résultat attribué à Sylvester. La symétrie $n \leftrightarrow g - n$ en est la clé : pour deviner $g$, on pouvait tracer, pour quelques couples $(a,b)$, la liste des entiers non réalisables et remarquer qu'ils se répartissent symétriquement.