Le th´eor`eme de B´ezout implique un autre r´esultat important :
Th´eor`eme 2.4.1 (Lemme de Gauss) Si des entiers a, b et csont tels que a divise bc et a est premier avec b, alors a divise c.
D´emonstration. Comme aest premier avec b, on peut ´ecrireau+bv= 1 pour des entiers uet v. Ainsiauc+bvc=c et commea divise auc(car il divisea) etbvc (car il divisebc), il
divise la somme qui vautc. ¤
Une premi`ere cons´equence du lemme de Gauss est le lemme 1.2.3 utilis´e lors de la preuve de l’unicit´e de la d´ecomposition en facteurs premiers, `a savoir :
Lemme 2.4.2 Si un nombre premier p divise le produit a1· · ·an, alors il divise l’un desai. D´emonstration.Supposons quepne divise aucun desai. Comme les seuls diviseurs positifs de p sont 1 etp, les nombres p et a1 sont forc´ement premiers entre eux. On en d´eduit, par le lemme de Gauss, que p divise a2· · ·an (puisque p est premier avec a1). Ensuite, p divise a3· · ·an, puis en it´erant il divise an, ce qui est suppos´e faux. ¤ Deux autres cons´equences tr`es importantes et tr`es utiles du lemme de Gauss sont donn´ees respectivement en proposition et en exercice :
Proposition 2.4.3 Si deux entiers premiers entre eux a et b divisent n, alors le produitab divise ´egalement n.
D´emonstration. Comme a divise n, on peut ´ecrire n =ak pour un certain entier k. Mais alors b divise ak et comme il est premier avec a, il divise k. Ainsi k =bk0 pour un entier k0
et puisn =abk0, ce qui prouve bien que ab divise n. ¤
Exercice: Soient aetbdeux entiers premiers entre eux. On notex0 ety0 des entiers tels que ax0+by0 = 1. Soit d un entier. Trouver tous les entiers x ety v´erifiant :
ax+by=d
Solution : On remarque dans un premier temps que le couple (dx0, dy0) est solution. Soit (x, y) une autre solution. On a alors ax+by = d et adx0 +bdy0 = d et donc en faisant la diff´erence :
a(x−dx0) = −b(y−dy0)
On en d´eduit quea divise b(y−dy0) et comme il est premier avecb, il divisey−dy0. Ainsi, il existe un entierk tel quey=dy0+ka. Finalement, en reportant dans l’´equation de d´epart, on arrive `ax=dx0−kb.
R´eciproquement on v´erifie que x et y ainsi d´efinis constituent bien une solution pour tout entier relatif k. Finalement, les solutions sont les couples (dx0 −kb, dy0 +ka) pour k
entier relatif. √
Remarque. R´esoudre en entiers l’´equation ax+by = d revient g´eom´etriquement `a trouver les points `a coordonn´ees enti`eres sur la droite d’´equation cart´esienne ax+by=d.
De fa¸con plus anecdotique, on peut chercher `a r´esoudre l’´equationax+by =den nombres entiers naturels. On a, dans ce sens, la proposition suivante :
Proposition 2.4.4 (Coin exchange problem of Frobenius4) Soientaetbdeux entiers strictement positifs et premiers entre eux. Le nombre relatif d peut s’´ecrire sous la forme ax+by pour des entiers x et y positifs ou nuls si et seulement si le nombre ab−a−b−x ne peut pas s’´ecrire sous cette forme.
En particulier, ab−a−b est le plus grand entier qui ne puisse pas s’´ecrire ax+by o`u x et y sont des entiers positifs ou nuls.
D´emonstration. Notonsx0 ety0 des entiers tels queax0+by0 = 1. On a vu dans l’exercice pr´ec´edent que les solutions (en entiers relatifs) de l’´equation ax+by=d sontx=dx0−kb et y =dy0+ka. Ainsi, l’´equation admet une solution en nombre entiers positifs ou nuls si et seulement s’il existe un entier k tel que dx0−kb > −1 etdy0+ka >−1, autrement dit si et seulement s’il y a un entier dans l’intervalle ¤
−dy0a+1,dx0b+1£ . Il s’agit donc de prouver qu’il y a un entier dans l’intervalle¤
−dy0a+1,dx0b+1£
si et seulement s’il n’y en a pas dans l’intervalle
i
−(D−d)ya 0+1,(D−d)xb 0+1 h
o`u on pose D=ab−a−b. Or, si n est un entier, les propri´et´es suivantes sont ´equivalentes :
−(D−d)y0+ 1
a < n < (D−d)x0+ 1 b
−by0+y0+ by0 a +dy0
a − 1
a < n < ax0−x0− ax0
b − dx0 b +1
b
En se rappelant queax0+by0 = 1, l’in´equation pr´ec´edente se simplifie consid´erablement et devient :
−by0+ dy0
a < n+x0−y0 < ax0−dx0
ou encore : b
dy0
a < n+x0−y0+by0 <1− dx0 b puis, en passant aux oppos´es :
dx0
b −1<−n−x0 +y0−by0 <−dy0 a
D´esormais, il suffit donc de montrer qu’il y a un entier dans l’intervalle ¤
−dy0a+1,dx0b+1£ si et seulement s’il n’y en a pas dans l’intervalle¤dx
0
b −1,−dya0£ .
D´ej`a, on remarque que le premier intervalle n’est jamais vide, puisque l’on a bien : dx0+ 1
b + dy0+ 1
a = d+a+b ab >0 Le second intervalle peut ˆetre vide. En effet :
−dy0
a −dx0
b + 1 = 1− d ab
qui peut ˆetre n´egatif si d>ab. Seulement dans ce cas, le premier intervalle est d’amplitude strictement sup´erieure `a 1 et donc contient forc´ement un entier : l’´equivalence est donc bien v´erifi´ee.
Sinon, on remarque que l’intersection de deux intervalles consiste en l’intervalle¤
−dy0a+1,−dya0£ qui ne peut contenir aucun entier, et que par contre la r´eunion consiste en l’intervalle
¤dx
0
b −1,dx0b+1£
qui contient autant d’entiers que ¤dx
0
b −1,dxb0¤
, c’est-`a-dire un et un seul.
Ceci d´emontre la proposition. ¤
Exercice: Soient aetb des entiers strictement positifs et premiers entre eux. Montrer que le nombre d’entiers positifs qui ne peuvent pas se mettre sous la formeax+by pour des entiers positifs ou nulsx et y est donn´e par la formule :
(a−1) (b−1) 2
Solution : D’apr`es la proposition pr´ec´edente tous les nombres strictement sup´erieurs `a d= ab−a−b peuvent se mettre sous la forme de l’´enonc´e. D’autre part sin∈ {0, . . . , d}, on sait que n peut se mettre sous la forme en question si, et seulement si d−n ne le peut pas. Or l’application n 7→ d−n r´ealise une bijection de l’ensemble {0, . . . , d} sur lui-mˆeme. On en d´eduit qu’exactement la moiti´e des nombres de cet ensemble s’´ecrivent sous la forme voulue.
Cela e fait d+12 , soit encore la formule donn´ee dans l’´enonc´e. √