Exercice 42 Relation de Bézout à coefficients dans $\mathbb{N}$

a) Supposons par l'absurde que $ab-a-b=au+bv$ avec $u$ et $v$ dans $\mathbb{N}$. Alors : $$ab=a(u+1)+b(v+1)$$ Ainsi $a$ divise $ab-a(u+1)=b(v+1)$. Comme $\mathrm{PGCD}(a,b)=1$, le théorème de Gauss donne $a\mid v+1$ ; or $v+1\geqslant 1$, donc $v+1\geqslant a$. De même, $b\mid u+1$, donc $u+1\geqslant b$. Mais alors : $$ab=a(u+1)+b(v+1)\geqslant ab+ab=2ab$$ ce qui est absurde puisque $ab>0$. $\boxed{ab-a-b \text{ n'est pas de la forme } au+bv,\ (u,v)\in\mathbb{N}^{2}}$

b) Soit $n\geqslant ab-a-b+1$. Pour $u\in\{0,\dots,b-1\}$ : $$n-au\geqslant n-a(b-1)\geqslant ab-a-b+1-ab+a=1-b$$ Ces $b$ entiers ont des restes distincts modulo $b$. En effet, si $n-au\equiv n-au'\;[b]$, alors $b\mid a(u'-u)$, donc $b\mid u'-u$ par le théorème de Gauss ; comme $|u'-u|<b$, on a $u=u'$. Les $b$ restes possibles $0$, $1$, …, $b-1$ sont donc tous atteints, en particulier $0$ : il existe $u_{0}\in\{0,\dots,b-1\}$ tel que $n-au_{0}=bv_{0}$ avec $v_{0}\in\mathbb{Z}$. Comme $bv_{0}\geqslant 1-b>-b$, on a $v_{0}>-1$, donc $v_{0}\in\mathbb{N}$. $$\boxed{n=au_{0}+bv_{0} \text{ avec } (u_{0},v_{0})\in\mathbb{N}^{2}}$$

c) Avec $a=5$ et $b=8$, premiers entre eux, le plus grand montant impossible est : $$\boxed{5\times 8-5-8=27 \text{ centimes}}$$ et tout montant à partir de $28$ centimes est payable. En testant les montants de $1$ à $27$, on trouve que les montants payables sont $5$, $8$, $10$, $13$, $15$, $16$, $18$, $20$, $21$, $23$, $24$, $25$ et $26$. Les montants impossibles sont donc : $$1,\ 2,\ 3,\ 4,\ 6,\ 7,\ 9,\ 11,\ 12,\ 14,\ 17,\ 19,\ 22,\ 27$$ Il y en a $14=\dfrac{4\times 7}{2}=\dfrac{(a-1)(b-1)}{2}$. Cette formule est générale : c'est la question c de l'exercice 507 du poly. On peut la contrôler sur $a=3$, $b=5$ : les montants impossibles sont $1$, $2$, $4$, $7$, soit $4=\frac{2\times 4}{2}$, le plus grand valant $15-3-5=7$.