mathématiques MPSI · Chapitre 7 · Exercice de TD

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

Arithmétique dans l'ensemble des entiers relatifs · C. Entiers premiers entre eux et lemme de Gauss · niveau 3 (difficile)

É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é de la question 1

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.

Question 2 : comment l'IA t'aide

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

Élève

Pour le b), le sens « $y \geq 0$ implique représentable » est immédiat. Pour la réciproque, j'ai $n = a x_{1} + b y_{1}$ avec $x_{1}, y_{1} \in N$ , mais rien ne dit que $x_{1} \leq b - 1$ : je ne peux pas l'identifier au couple canonique.

Justement : comment ramener $x_{1}$ dans ${0, \dots, b - 1}$ sans changer la valeur de $a x_{1} + b y_{1}$ ? Pense à ce que tu as fait pour l'existence au a).

Élève

Je divise $x_{1}$ par $b$ : $x_{1} = b q + x$ avec $0 \leq x \leq b - 1$ . Alors $a x_{1} = a x + ab q$ , et je peux faire passer $ab q$ dans le terme en $b$ .

Bien. Quel résultat du a) te permet d'affirmer que le couple obtenu est le couple canonique, et pourquoi sa seconde coordonnée reste-t-elle positive ? Que sais-tu du signe de $q$ ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →