PGCD & Théorèmes fondamentaux

Le PGCD (Plus Grand Commun Diviseur) de a et b est le plus grand entier naturel divisant à la fois a et b. Notation : PGCD(a,b) ou a∧b. a et b sont premiers entre eux si PGCD(a,b) = 1.

Pour calculer PGCD(a,b) avec a > b > 0 : 1. Diviser a par b : a = bq₁ + r₁ 2. Si r₁ = 0 : PGCD(a,b) = b. Sinon continuer. 3. Diviser b par r₁ : b = r₁q₂ + r₂ 4. Répéter jusqu'au reste nul. Le dernier reste non nul est PGCD(a,b). Exemple : PGCD(48,18) : 48=18×2+12 ; 18=12×1+6 ; 12=6×2+0 → PGCD=6.

Pour tous a,b ∈ ℤ non tous nuls, il existe u,v ∈ ℤ tels que : au + bv = PGCD(a,b) Corollaire : a et b sont premiers entre eux ⟺ il existe u,v ∈ ℤ tels que au+bv=1. Les coefficients u,v se calculent par l'algorithme d'Euclide étendu.

Si a|bc et PGCD(a,b)=1, alors a|c. Application (cas particulier) : si p premier et p|bc, alors p|b ou p|c. Utilisation type : pour montrer que a divise c, trouver b coprime avec a tel que a|bc.

L'équation ax+by=c (a,b,c ∈ ℤ) admet des solutions entières ⟺ PGCD(a,b)|c. Si (x₀,y₀) est une solution particulière, les solutions générales sont : x = x₀ + (b/d)·k y = y₀ − (a/d)·k pour tout k ∈ ℤ, avec d = PGCD(a,b).