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.