Afin de démontrer cet algorithme nous avons besoin du théorème de Bézout :

$a$ et $b$ sont deux entiers naturels non nuls. Dire « $a$ et $b$ sont premiers entre eux » équivaut à dire « il existe deux entiers relatifs $u$ et $v$ tels que $au+bv = 1$ ».

Supposons qu’il existe deux entiers $u$ et $v$ tels que $au+bv=1$ et prouvons que $a$ et $b$ sont premiers entre eux.

On note $d=\text{PGCD }(a\ ;b)$. $d$ divise $a$ et $b$ donc $d$ divise $au+bv$.

Comme $au+bv=1$, $d=1$ et $a$ et $b$ sont premiers entre eux.

Supposons $a$ et $b$ premiers entre eux et démontrons que $1$ s’écrit sous la forme $au+bv$. Soit $\varepsilon$ l’ensemble des nombres de la forme $au+bv$, avec $u ∈\mathbb Z$ et $v ∈\mathbb Z$.

L’ensemble $\varepsilon$ n’est pas vide car pour $u = 1$ et $v = 0$, ∈ $\varepsilon$. Il en est de même pour $b$.

Ainsi $\varepsilon$ contient des entiers strictement positifs et, parmi eux, un plus petit que tous les autres.

Notons $m = au$1+bv1 ce plus petit élément. La division euclidienne de $a$ par $m$ s’écrit $a=mq+r$ avec $0 ≤ r < m$

soit $\begin{aligned}r&=a-mq\&=a-(au$1+bv1)q\&=a(1-u1q)+b(-v1q)\end{aligned}

Ainsi r ∈ $\varepsilon$.

Or $m$ est le plus petit entier strictement positif de $\varepsilon$ donc $r=0$. Ainsi $m$ divise $a$. On montre de même que $m$ divise $b$.

Comme $a$ et $b$ sont premiers entre eux, $m = 1$ et $au$1+bv1=1.

En pratique, pour trouver $u$ et $v$, on utilise l’algorithme d’Euclide pour démontrer que les deux nombres sont premiers entre eux. Puis, on reprend chaque division euclidienne pour exprimer chaque reste au fur et à mesure. On trouve ainsi le couple solution.