PGCD(a,b) = plus grand diviseur commun de a et b
Notation : PGCD(a,b) ou a∧b
PROPRIÉTÉS :
GPGCD(a,b)=PGCD(b,a)
GPGCD(a,0)=a
Si d=PGCD(a,b) : a=d·a', b=d·b' avec PGCD(a',b')=1
GPGCD(a,b)=PGCD(a,a−b)
a et b COPRIMES : PGCD(a,b)=1
Algorithme d'Euclide
MéthodePGCD(a,b) avec a≥b>0 :
Principe : PGCD(a,b)=PGCD(b,r) où r=a mod b
ÉTAPES :
a = bq₁+r₁ → PGCD(a,b)=PGCD(b,r₁)
b = r₁q₂+r₂ → PGCD(b,r₁)=PGCD(r₁,r₂)
… jusqu'à rₖ=0
Dernier reste non nul = PGCD(a,b)
Exemple : PGCD(252,105) :
252=105×2+42
105=42×2+21
42=21×2+0
→ PGCD=21
⚡ Complexité : O(log(min(a,b))) divisions. C'est un des algorithmes les plus anciens (Euclide, ~300 av.J.-C.).