a divise b (a|b) si ∃k∈ℤ : b=ka
• a|b et a|c ⟹ a|(bu+cv)  pour u,v∈ℤ

Pour a∈ℤ, b∈ℤ* : ∃! q,r∈ℤ :
a = bq + r  avec 0≤r<|b|
q = quotient, r = reste

PGCD(a,b) = PGCD(b, a mod b)
On divise successivement jusqu'au reste nul.
Le dernier diviseur non nul = PGCD(a,b).

a et b sont premiers entre eux
⟺ ∃ u,v∈ℤ : au+bv = 1
Plus généralement : ∃ u,v : au+bv = PGCD(a,b)

Si a|bc et PGCD(a,b)=1, alors a|c.
Applications : résolution d'équations diophantiennes.

p est premier si ses seuls diviseurs sont 1 et p.
Petit théorème de Fermat : si p premier et p∤a,
alors aᵖ⁻¹ ≡ 1  [mod p]

a ≡ b [n] ⟺ n|(a−b)
Propriétés :
• a≡b et c≡d ⟹ a+c≡b+d, ac≡bd  [n]
• a≡b [n] ⟹ aᵏ≡bᵏ [n]

• Div. par 2 : dernier chiffre pair
• Div. par 3 : somme des chiffres div. par 3
• Div. par 9 : somme des chiffres div. par 9
• Div. par 11 : somme alternée div. par 11