Divisibilité dans ℤ

Division euclidienne

Pour $a \in \mathbb{Z}$ et $b \in \mathbb{Z}^*$, il existe des uniques $q, r \in \mathbb{Z}$ tels que :

$a = bq + r \quad \text{avec } 0 \leq r < |b|$

$q$ est le quotient, $r$ le reste.

$b \mid a \iff r = 0$

---

Propriétés de la divisibilité

Pour $a, b, c \in \mathbb{Z}$ :

• $a \mid a$ (réflexivité)
• $a \mid b$ et $b \mid c \implies a \mid c$ (transitivité)
• $a \mid b$ et $a \mid c \implies a \mid (bx + cy)$ pour tous $x, y \in \mathbb{Z}$ (combinaison linéaire)
• $a \mid b$ et $b \mid a \implies b = \pm a$

---

PGCD — Algorithme d’Euclide

Le PGCD de $a$ et $b$ est le plus grand entier qui divise $a$ et $b$.

flowchart TD
    E["Entrée : a, b — b ≠ 0"] --> W{"b = 0 ?"}
    W -->|Non| D["Division euclidienne\na = b·q + r"]
    D --> U["a ← b\nb ← r"]
    U --> W
    W -->|Oui| R["Retourner a = PGCD"]

Algorithme : divisons successivement :

$a = bq_1 + r_1 \implies \text{PGCD}(a,b) = \text{PGCD}(b, r_1)$

On itère jusqu’à $r = 0$. Le dernier reste non nul est le PGCD.

Exemple : PGCD(252, 105)

$252 = 2 \times 105 + 42$

$105 = 2 \times 42 + 21$

$42 = 2 \times 21 + 0$

PGCD(252, 105) = 21

---

Entiers premiers entre eux

$a$ et $b$ sont premiers entre eux (ou copremiers) si PGCD$(a,b) = 1$.

Lemme de Gauss : Si $a \mid bc$ et $a \land b = 1$ (copremiers), alors $a \mid c$.

---

Congruences — Définition

$a \equiv b \pmod{n} \iff n \mid (a - b)$

Propriétés :

• Réflexivité, symétrie, transitivité
• Compatible avec $+$ et $\times$ : si $a \equiv b$ et $c \equiv d$ mod $n$, alors $a+c \equiv b+d$ et $ac \equiv bd$

Exemple : $17 \equiv 2 \pmod{5}$ car $5 \mid 15$