Fiche résumé : Arithmétique dans $\mathbb{Z}$ (Prépa, 1re année)

Ce chapitre étudie la divisibilité dans $\mathbb{Z}$ : division euclidienne, PGCD et PPCM, nombres premiers, congruences. Ces outils servent à résoudre des équations en nombres entiers, à calculer des restes de grandes puissances, et ils préparent l'étude des anneaux $\mathbb{Z}/n\mathbb{Z}$ et de l'arithmétique des polynômes.

$a \mid b \iff \exists k \in \mathbb{Z},\ b = ka$. Associés : $a \mid b$ et $b \mid a \iff |a| = |b|$.
Division euclidienne : pour $a \in \mathbb{Z}$, $b \in \mathbb{N}^*$, il existe un unique $(q, r)$ avec $a = bq + r$, $0 \leqslant r < b$ ; $q = \lfloor a/b \rfloor$.
PGCD $a \wedge b$ : plus grand diviseur commun ; $\mathcal{D}(a) \cap \mathcal{D}(b) = \mathcal{D}(a \wedge b)$.
Euclide : si $a = bq + r$, alors $a \wedge b = b \wedge r$ ; le PGCD est le dernier reste non nul.
Relation de Bézout : $\exists (u, v),\ au + bv = a \wedge b$ (Euclide étendu). $a\mathbb{Z} + b\mathbb{Z} = (a \wedge b)\mathbb{Z}$.
Théorème de Bézout : $a \wedge b = 1 \iff \exists (u,v),\ au + bv = 1$.
$a = da'$, $b = db'$ avec $d = a \wedge b$ entraîne $a' \wedge b' = 1$. Homogénéité : $(ka) \wedge (kb) = |k|(a \wedge b)$.
Gauss : $a \mid bc$ et $a \wedge b = 1 \Rightarrow a \mid c$.
$a \mid n$, $b \mid n$, $a \wedge b = 1 \Rightarrow ab \mid n$. $a \wedge b = a \wedge c = 1 \Rightarrow a \wedge bc = 1$.
$ax + by = c$ : solutions si et seulement si $d \mid c$ ; alors $(x_0 + kb',\ y_0 - ka')$, $k \in \mathbb{Z}$.
PPCM $a \vee b$ : $a\mathbb{Z} \cap b\mathbb{Z} = (a \vee b)\mathbb{Z}$ et $(a \wedge b)(a \vee b) = |ab|$.
Tout $n \geqslant 2$ a un diviseur premier ; si $n$ est composé, il en a un $\leqslant \sqrt{n}$. $\mathcal{P}$ est infini.
Lemme d'Euclide : $p$ premier, $p \mid ab \Rightarrow p \mid a$ ou $p \mid b$. Et $p \mid a$ ou $p \wedge a = 1$.
Décomposition : $n = p_1^{\alpha_1} \cdots p_r^{\alpha_r}$, unique ; nombre de diviseurs positifs $\prod (\alpha_i + 1)$.
Valuations : $v_p(ab) = v_p(a) + v_p(b)$ ; $a \mid b \iff \forall p,\ v_p(a) \leqslant v_p(b)$ ; $v_p(a \wedge b) = \min$, $v_p(a \vee b) = \max$.
$a \equiv b \;[n] \iff n \mid b - a$ ; compatible avec $+$, $\times$ et les puissances ; simplification par $k$ seulement si $k \wedge n = 1$.
$a$ inversible modulo $n$ $\iff a \wedge n = 1$ ; inverse donné par Bézout.
$p$ premier, $1 \leqslant k \leqslant p - 1 \Rightarrow p \mid \binom{p}{k}$.
Fermat : $p$ premier, $a^p \equiv a \;[p]$ pour tout $a$ ; $a^{p-1} \equiv 1 \;[p]$ si $p \nmid a$.