Arithmétique PGCD et PPCM Démonstration de l'algorithme d'Euclide

Démonstration de l'algorithme d'Euclide

Soient a et b deux entiers positifs. Supposons que a est le plus grand, a b, et divisons a par b : a = bq₁ + r₁ avec 0 r₁ < b.

Tout diviseur commun à a et b est un diviseur commun à b et r₁ et réciproquement.
Donc pgcd(a,b) = pgcd(b,r₁).

On itère le procédé et l'on sait que la suite des restes obtenue est une suite d'entiers strictement décroissante. Donc à un certain stade r_k = 0.

b = r₁ q₂ + r₂    et    0 r₂ < r₁

r₁ = r₂ q₃ + r₃    et    0 r₃ < r₂

r_k-3 = r_k-2 q_k-1 + r_k-1   et    0 r_k-1 < r_k-2  

r_k-2 = r_k-1 q_k

Donc r_k-1 divise r_k-2 et pgcd(r_k-2, r_k-1) = r_k-1 et de proche en proche r_k-1=pgcd(a,b).

Cet algorithme est une démonstration d'existence du pgcd. Il permet aussi de montrer que tout diviseur commun à a et b est un diviseur de d. Comme nous l'avons vu sur l'exemple, cet algorithme permet de déterminer successivement chaque reste comme na + mb avec n et m entiers. Nous allons donc nous intéresser aux entiers qui peuvent s'écrire sous la forme ax + by.

Arithmétique PGCD Existence