Divisibilité et division euclidienne
Définitiona divise b (noté a|b) ⟺ ∃k∈ℤ : b=k·a
DIVISION EUCLIDIENNE de a par b (b>0) :
Il existe un unique couple (q,r) tel que
a = b·q + r avec 0 ≤ r < b
q = quotient, r = reste = a mod b
PROPRIÉTÉS :
a|b et a|c → a|(bu+cv) pour tous u,v∈ℤ
a|b et b|a → |a|=|b|
Transitivité : a|b et b|c → a|c
⚡ r = a mod b est l'opérateur modulo (%) en programmation, fondamental pour le hachage et l'indexation circulaire.
Algorithme d'Euclide et Bézout
ThéorèmeALGORITHME D'EUCLIDE :
PGCD(a,b) = PGCD(b, a mod b), jusqu'à reste = 0.
Le dernier reste non nul est le PGCD.
Exemple PGCD(252,180) :
252=1×180+72 → PGCD(180,72)
180=2×72+36 → PGCD(72,36)
72=2×36+0 → PGCD=36
IDENTITÉ DE BÉZOUT :
∃ u,v∈ℤ : a·u + b·v = PGCD(a,b)
a et b premiers entre eux ⟺ PGCD(a,b)=1 ⟺ ∃u,v : au+bv=1
PPCM : PGCD(a,b) × PPCM(a,b) = |a·b|