Arithmétique

a divise b (a|b) si ∃k∈ℤ tel que b = ka.
PGCD(a,b) : le plus grand diviseur commun.
PPCM(a,b) = |a·b| / PGCD(a,b)

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

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

Si a|bc et PGCD(a,b) = 1, alors a|c.

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