Soient deux entiers relatifs a et b
non nuls, ab 
0. Considérons l'ensemble S' des entiers
positifs qui peuvent s'écrire sous la forme ax + by : S' = {
ax + by | x, y 
et ax + by > 0 }
. De façon
évidente S' est non vide puisque l'un des nombres au moins ±
a, ± b est positif. D'après la propriété du bon ordre, cet
ensemble possède un plus petit élément d. Il existe deux entiers
relatifs x0 et y0 tels que d = x0a + y0b.
Montrons
que ce nombre d est le pgcd des deux nombres a et b.
On va d'abord montrer que d | a et d |
b. Sinon, on peut écrire la division euclidienne de a par d
avec un reste non nul : a = dq + r avec 0 < r < d. Comme
d = x0 a + y0 b , r = a - (x0 a + y0 b)q = a(1 - x0 q) - b y0 q ,
ce qui montre que r appartient à l'ensemble S' et est plus
petit que d, ce qui est contraire à la définition de d. On en
conclut que d divise a. De la même façon, on montre que d
divise b et donc que d est un diviseur commun à a et b.
On va maintenant montrer que d est le pgcd de a et b : dans les
propriétés sur la divisibilité, on a montré que tout diviseur
commun à a et b divise tous les éléments de S et donc en
particulier d. Ceci démontre que d est le plus grand diviseur
commun de a et de b.
