Soit a ∈ ℤ et b ∈ ℕ*, il existe un unique couple (q, r) tel que a = bq + r avec 0 ≤ r < b
Vocabulaire: a est le dividende, b le diviseur, q le quotient et r le reste
a divise b
⟺ b multiple de a
⟺ il existe k ∈ ℤ tel que b = ka
Notation: a|b
a|a
Transitivité: { a|b
b|c } ⟹ a|c
Linéarité: { a|b
a|c } ⟹ a|bu + cv
Lien avec les congruences: a|b ⟺ b ≡ 0(a)
Lien avec le PGCD: a|b ⟺ PGCD(a, b) = a
a et b ont même reste dans la division euclidienne par n
⟺ a est congru à b modulo n
⟺ a − b est multiple de n
Notation: a ≡ b (modn) (ou directement a ≡ b (n))
a ≡ a (n)
a ≡ b (n) ⟹ b ≡ a (n)
Transitivité: { a ≡ b (n)
b ≡ c (n) } ⟹ a ≡ c (n)
Addition: { a ≡ b (n)
a' ≡ b' (n) } ⟹ a + a' ≡ b + b' (n)
Multiplication: { a ≡ b (n)
a' ≡ b' (n) } ⟹ aa' ≡ bb' (n)
Puissance: a ≡ b (n) ⟹ ak ≡ bk (n)
Un entier p supérieur ou égal à 2 est premier si et seulement si il admet exactement deux diviseurs: 1 et lui-même
si n n'admet pas de diviseur premier p tel que 2 ≤ p ≤ √n alors n est premier
Propriété: Si a divise b et a divise c, alors a divise αb+βc pour tous entiers α et β
L'ensemble des diviseurs communs à a et b admet un plus grand élément noté PGCD(a, b)
L'ensemble des multiples communs à a et b admet un plus petit élément noté PPCM(a, b)
ap-1 ≡ 1 (p) avec p premier ne divisant pas a
PGCD(a, b) = a·PGCD(1, b/a)
Si a = bq + r, alors PGCD(a, b) = PGCD(b, r)
Le PGCD de deux nombres non nuls est le dernier reste non nul de la suite des divisions de l'algorithme d'Euclide
PGCD(a, b) = 1
⟺ a et b sont premiers entre eux
⟺ il existe deux entiers u et v tels que au + bv = 1
PGCD(a, b) = d
⟺ il existe deux entiers u et v tels que au + bv = d
L'équation au + bv = c admet des solutions entières ⟺ c est multiple de PGCD(a, b)
⟹ a|c
Soient a et b deux entiers naturels non nuls, b ≥ 2 et PGCD(a, b) = 1 alors il existe un unique entier non nul u appartenant à {1, 2, ..., b-1} tel que a.u ≡ 1(b)
On dit que u est l'inverse de a modulo b
Si n≠0 (p),
n.v ≡ 0 (p) ⟹
a.b≡j