pgcd et combinaison linéaire de deux entiers naturels

Propriété :
L'ensemble n où n est le pgcd de deux entiers naturels non nuls a et b est l'ensemble des combinaisons linéaires à coefficients dans de a et de b.

Démonstration :
Considérons l'ensemble
E = { x tel que x = u a + v b avec (u ; v) ² }
L'ensemble E ≠ {0} puisque a E par exemple.
Soit n le plus petit élément strictement positif de E, il existe donc deux entiers relatifs u0 et v0 tels que n = u0a + v0b.

Montrons que E = n :
Tout élément de n est alors encore un multiple de n :
en effet pour tout k , kn = k( u0a + v0b) = (ku0)a + (kv0)b
kn E, par conséquent n E.

Inversement soit x un élément quelconque de E,
il existe (u ; v) ² tel que x = u a + v b , la division euclidienne de x par n donne un quotient q et un reste r tels que 0 r < n on a :
x = nq + r
r = x - nq = u a + v b - (u0a + v0b)q = (u - u0q)a + (v - v0q)b
r est donc encore un élément de E, mais si r > 0 alors r < n ce qui est impossible puisque n est le plus petit élément strictement positif de E, donc r = 0 et x est un multiple de n.
Il en résulte E n

on a donc démontrer que le nombre n plus petit élément strictement positif de E est tel que E = n

Montrons que n est le pgcd de a et de b

Soit Dn, Da, Db respectivement les ensembles des diviseurs de n,a et b, montrons que Dn = Da Db
x Da Db
x|a et x|b
x|u0a et x|v0b
x| (u0a + v0b) d'ou x | n
(Note : x |a signifie x divise a )
x Dn

Inversement
La division euclidienne de a par n donne un quotient q et un reste r tels que 0 r < n on a :
a = nq + r
r = a - nq = a - (u0a + v0b)q = (1 - u0q )a + (- v0q )b
r est donc un élément de E, mais si r > 0 alors r < n ce qui est impossible puisque n est le plus petit élément strictement positif de E, donc r = 0 et a est un multiple de n ou n est diviseur de a.
De la même façon on démontre que n est un diviseur de b.
on a donc n|a et n|b.
x Dn x|a et x|b x Da Db.