Divisibilité et division euclidienne
Définitiona divise b (noté a|b) si ∃k∈ℤ tel que b=ka.
Division euclidienne : ∀a∈ℤ, ∀b∈ℕ*, ∃!(q,r) :
a = b·q + r avec 0 ≤ r < b
PGCD(a,b) = plus grand diviseur commun positif de a et b.
Algorithme d'Euclide : PGCD(a,b) = PGCD(b, a mod b) jusqu'à r=0.
Identité de Bézout
Théorème∀a,b∈ℤ, ∃u,v∈ℤ tels que :
au + bv = PGCD(a,b)
Corollaire : a et b premiers entre eux (PGCD=1) ⟺ ∃u,v : au+bv=1
Théorème de Gauss : si a|bc et PGCD(a,b)=1 alors a|c
Lemme d'Euclide : si p premier et p|ab alors p|a ou p|b
⚡ On trouve u,v par l'algorithme d'Euclide remonté (substitutions successives).