D'après le théorème de Bezout on a :
a et b sont premiers entre eux <=> il existe u et v entiers tels que a*u + b*v = 1.

Preuve : a*Z + b*Z est un sous groupe additif de Z (ou Z est l'ensemble des relatifs) :
_ non vide.
_ inclus dans Z.
_ stable par + et opposé.
De plus il est non réduit à {0} donc il existe d tel que :
a*Z + b*Z = d*Z et d = pgcd(a,b)
car tout sous-groupe additif G de Z, différents de {0} peut s'écrire n*Z.
preuve de cette dernière affirmation :
soit n le plus petit élément > 0 de G.
par double inclusion :
_ n*Z inclus dans G.
_ si il existe g appartient à (G-n*Z).
alors g appartient à ]k*n ; (k+1)*n[ où k appartient à Z.
donc g-k*n appartient à G or g-k*n < n ; contradiction.
Donc G = n*Z.
Ici d=1 donc tout élément de Z , et à fortiori 1, peut s'écrire a*u+b*v.