Le problème des deux pièces (Sylvester)

Exercice de TD · niveau 3 (difficile) · mathématiques MPSI, chapitre 7 — Arithmétique dans l'ensemble des entiers relatifs · C. Entiers premiers entre eux et lemme de Gauss

Énoncé

Soient $a, b \geq 2$ deux entiers premiers entre eux. Un entier $n \in N$ est dit représentable s'il existe $(x, y) \in N^{2}$ tel que $n = a x + b y$ — on peut payer $n$ avec des pièces de $a$ et de $b$ .

a) Montrer que pour tout $n \in Z$ , il existe un unique couple $(x, y) \in Z^{2}$ tel que $n = a x + b y$ et $0 \leq x \leq b - 1$ . On l'appelle le couple canonique de $n$ .

b) Montrer que $n \in N$ est représentable si et seulement si, dans son couple canonique, $y \geq 0$ .

c) En déduire que tout entier $n \geq (a - 1) (b - 1)$ est représentable.

d) Montrer que $ab - a - b$ n'est pas représentable. Conclure. Avec des pièces de $5$ et de $8$ , quel est le plus grand montant impayable ?

e) Montrer que $n \mapsto ab - a - b - n$ échange, sur ${0, 1, \dots, ab - a - b}$ , les entiers représentables et les non représentables. En déduire qu'il y a exactement $\frac{( a - 1 ) ( b - 1 )}{2}$ entiers non représentables.

Corrigé

La stratégie. La relation de Bézout donne une écriture $n = a x + b y$ — mais avec des entiers relatifs, et sans unicité. La division euclidienne normalise $x$ dans ${0, \dots, b - 1}$ , le lemme de Gauss rend cette écriture unique, et alors la question « peut-on payer $n$ ? » se lit sur le signe de $y$ .

a) Existence et unicité du couple canonique. Existence. Comme $a \land b = 1$ , le théorème de Bézout fournit $(u, v) \in Z^{2}$ avec $a u + b v = 1$ . En multipliant par $n$ : $n = a (n u) + b (n v)$ . Effectuons la division euclidienne de $n u$ par $b$ : $n u = b q + x$ avec $0 \leq x \leq b - 1$ . Alors $n = a (b q + x) + b (n v) = a x + b (a q + n v),$ et le couple $(x, y)$ avec $y = a q + n v$ convient.

Unicité. Soient $(x, y)$ et $(x^{'}, y^{'})$ deux couples convenables. De $a x + b y = a x^{'} + b y^{'}$ on tire $a (x - x^{'}) = b (y^{'} - y)$ . Donc $b$ divise $a (x - x^{'})$ ; comme $b \land a = 1$ , le lemme de Gauss donne $b ∣ x - x^{'}$ . Or $x$ et $x^{'}$ sont dans ${0, \dots, b - 1}$ , donc $∣ x - x^{'} ∣ \leq b - 1 < b$ : le seul multiple de $b$ possible est $0$ , et $x = x^{'}$ . Alors $b (y^{'} - y) = 0$ avec $b \neq = 0$ , donc $y = y^{'}$ . Le couple canonique est unique.

b) Le critère. Si $y \geq 0$ dans le couple canonique, alors $n = a x + b y$ avec $x, y \in N$ : $n$ est représentable. Réciproquement, supposons $n = a x_{1} + b y_{1}$ avec $x_{1}, y_{1} \in N$ . Divisons $x_{1}$ par $b$ : $x_{1} = b q + x$ avec $0 \leq x \leq b - 1$ et $q \geq 0$ (car $x_{1} \geq 0$ ). Alors $n = a x + b (y_{1} + a q)$ , et le couple $(x, y_{1} + a q)$ vérifie la condition du a) : par unicité, c'est le couple canonique, dont la seconde coordonnée $y = y_{1} + a q$ est positive. $n$ est représentable si et seulement si le $y$ de son couple canonique est positif.

c) Au-delà de $(a - 1) (b - 1)$ , tout se paie. Soit $n \geq (a - 1) (b - 1)$ et $(x, y)$ son couple canonique. Comme $x \leq b - 1$ , $b y = n - a x \geq (a - 1) (b - 1) - a (b - 1) = (b - 1) (a - 1 - a) = - (b - 1) > - b .$ Donc $y > - 1$ , et comme $y$ est un entier, $y \geq 0$ : par le b), $n$ est représentable.

d) Le montant impayable. Posons $g = ab - a - b = a (b - 1) - b = a (b - 1) + b (- 1)$ . Le couple $(b - 1, - 1)$ vérifie $0 \leq b - 1 \leq b - 1$ : c'est le couple canonique de $g$ , et sa seconde coordonnée vaut $- 1 < 0$ . Par le b), $g$ n'est pas représentable. Or $(a - 1) (b - 1) = ab - a - b + 1 = g + 1$ , donc par le c) tout entier $n \geq g + 1$ est représentable. Conclusion : le plus grand entier non représentable est $ab - a - b$ . Avec $a = 5$ et $b = 8$ : $40 - 13 = 27$ . On vérifie : $28 = 5 \cdot 4 + 8$ , $29 = 5 + 8 \cdot 3$ , $30 = 5 \cdot 6$ , $31 = 5 \cdot 3 + 8 \cdot 2$ , $32 = 8 \cdot 4$ , et au-delà on ajoute des pièces de $5$ à l'un de ces cinq montants consécutifs ; tandis que $27 - 8 k$ pour $k = 0, 1, 2, 3$ vaut $27, 19, 11, 3$ , dont aucun n'est multiple de $5$ .

e) La symétrie de Sylvester. Soit $n \in {0, \dots, g}$ , de couple canonique $(x, y)$ . Alors $g - n = a (b - 1) - b - a x - b y = a (b - 1 - x) + b (- 1 - y) .$ Comme $0 \leq x \leq b - 1$ , on a $0 \leq b - 1 - x \leq b - 1$ : le couple $(b - 1 - x, - 1 - y)$ est le couple canonique de $g - n$ . Par le b), $g - n$ est représentable si et seulement si $- 1 - y \geq 0$ , c'est-à-dire $y \leq - 1$ , c'est-à-dire $y < 0$ , c'est-à-dire $n$ n'est pas représentable. L'application $n \mapsto g - n$ est une bijection de ${0, \dots, g}$ sur lui-même (elle est sa propre réciproque) qui échange représentables et non représentables : les deux ensembles ont le même nombre d'éléments, soit la moitié de $g + 1 = (a - 1) (b - 1)$ . Il y a donc exactement $\frac{( a - 1 ) ( b - 1 )}{2}$ entiers non représentables (ce nombre est entier : $a$ et $b$ premiers entre eux ne sont pas tous deux pairs, donc l'un de $a - 1$ , $b - 1$ est pair). Pour $5$ et $8$ : $\frac{4 \times 7}{2} = 14$ montants impayables, à savoir $1, 2, 3, 4, 6, 7, 9, 11, 12, 14, 17, 19, 22, 27$ .

Le point délicat. L'hypothèse $a \land b = 1$ sert deux fois : pour l'existence (Bézout) et pour l'unicité (Gauss). Sans elle, l'énoncé est faux : avec des pièces de $4$ et de $6$ , aucun montant impair n'est payable, et il n'y a pas de « plus grand » impayable.

Ce que l'exercice installe. L'usage constructif de Bézout : une relation $a u + b v = 1$ n'est pas une fin, c'est un point de départ qu'on normalise par la division euclidienne et qu'on rend unique par Gauss. C'est exactement ce qu'on refera pour les systèmes de congruences (exercice 8) et, au chapitre des polynômes, pour la décomposition en éléments simples. Ce problème, résolu par Sylvester en 1882, s'appelle aujourd'hui le problème de Frobenius ; pour trois pièces, aucune formule fermée n'est connue.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.