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$

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

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

$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$ .

$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$