Arithmétique dans $\mathbb{Z}$

Le sens réciproque est immédiat : si $b = \pm a$, alors $a \mid b$ et $b \mid a$.

Supposons $a \mid b$ et $b \mid a$. Si $b = 0$, alors $b \mid a$ impose $a = 0$, d'où $|a| = |b|$. Sinon, il existe $k, l \in \mathbb{Z}$ tels que $b = ka$ et $a = lb$. Alors $b = klb$, et comme $b \neq 0$, $kl = 1$. Les seuls entiers dont le produit vaut $1$ sont $k = l = 1$ ou $k = l = -1$. Donc $b = \pm a$, c'est-à-dire $|a| = |b|$.

Existence. Posons $q = \lfloor a/b \rfloor$. Par définition de la partie entière, $q \leqslant \dfrac{a}{b} < q + 1$. Comme $b > 0$, on multiplie par $b$ : $bq \leqslant a < bq + b$. Posons $r = a - bq$. Alors $r \in \mathbb{Z}$ et $0 \leqslant r < b$.

Unicité. Supposons $a = bq + r = bq' + r'$ avec $0 \leqslant r, r' < b$. Alors $b(q - q') = r' - r$, et $-b < r' - r < b$. Donc $b|q - q'| < b$, puis $|q - q'| < 1$. Comme $q - q'$ est un entier, $q = q'$, puis $r = r'$.

Si $c$ divise $a$ et $b$, alors $c$ divise $a - qb = r$, donc $c$ divise $b$ et $r$.

Si $c$ divise $b$ et $r$, alors $c$ divise $bq + r = a$, donc $c$ divise $a$ et $b$.

Les deux ensembles sont égaux, donc ils ont le même plus grand élément.

Soit $S = \{au + bv \,;\, (u,v) \in \mathbb{Z}^2,\ au + bv > 0\}$. C'est une partie de $\mathbb{N}^*$, non vide car $a \cdot a + b \cdot b = a^2 + b^2 > 0$. Elle admet un plus petit élément $\delta = au_0 + bv_0$.

$\delta$ divise $a$. Écrivons $a = \delta q + r$ avec $0 \leqslant r < \delta$. Alors $r = a - q(au_0 + bv_0) = a(1 - qu_0) + b(-qv_0)$. Si $r > 0$, alors $r \in S$ et $r < \delta$, ce qui contredit la minimalité de $\delta$. Donc $r = 0$ et $\delta \mid a$. De même, $\delta \mid b$.

Inclusions. Si $c$ divise $a$ et $b$, alors $c$ divise $au_0 + bv_0 = \delta$. Donc $\mathcal{D}(a) \cap \mathcal{D}(b) \subset \mathcal{D}(\delta)$. Réciproquement, comme $\delta$ divise $a$ et $b$, tout diviseur de $\delta$ divise $a$ et $b$. D'où l'égalité $\mathcal{D}(a) \cap \mathcal{D}(b) = \mathcal{D}(\delta)$.

Conclusion. Le plus grand élément de $\mathcal{D}(\delta)$ est $\delta$, donc $a \wedge b = \delta = au_0 + bv_0$. Les deux points sont démontrés.

Si $a \wedge b = 1$, la relation de Bézout fournit $(u,v)$ tel que $au + bv = 1$.

Réciproquement, si $au + bv = 1$, alors $a$ et $b$ ne sont pas tous deux nuls, et tout diviseur commun positif $c$ de $a$ et $b$ divise $au + bv = 1$, donc $c = 1$. Ainsi $a \wedge b = 1$.

Comme $a \wedge b = 1$, il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$. En multipliant par $c$ : $$c = acu + bcv.$$ Or $a \mid acu$ et $a \mid bc$, donc $a \mid bcv$. Ainsi $a$ divise la somme, c'est-à-dire $a \mid c$.

Point 1. Soit $m = a \vee b$. Tout multiple de $m$ est multiple de $a$ et de $b$. Réciproquement, soit $M$ un multiple commun ; écrivons $M = mq + r$ avec $0 \leqslant r < m$. Alors $r = M - mq$ est un multiple commun de $a$ et $b$. S'il était strictement positif, il contredirait la minimalité de $m$. Donc $r = 0$ et $m \mid M$.

Point 2. Les deux membres ne dépendent que de $|a|$ et $|b|$ ; on suppose $a, b > 0$. Soit $d = a \wedge b$, avec $a = da'$, $b = db'$ et $a' \wedge b' = 1$. Posons $m = da'b' = ab' = a'b$ : c'est un multiple commun strictement positif.

Soit $M$ un multiple commun : $M = ak = da'k$. Comme $b \mid M$, $db' \mid da'k$, donc $b' \mid a'k$. Par Gauss ($a' \wedge b' = 1$), $b' \mid k$, donc $k = b'l$ et $M = ml$. Tout multiple commun est un multiple de $m$, donc $m$ est le plus petit multiple commun strictement positif : $m = a \vee b$. Enfin $dm = d \cdot da'b' = (da')(db') = ab$.

Supposons par l'absurde que $\mathcal{P}$ est fini : $\mathcal{P} = \{p_1, \dots, p_k\}$. Posons $N = p_1 p_2 \cdots p_k + 1 \geqslant 3$. D'après la propriété précédente, $N$ admet un diviseur premier, donc il existe $i$ tel que $p_i \mid N$. Comme $p_i \mid p_1 \cdots p_k$, on obtient $p_i \mid N - p_1 \cdots p_k = 1$, ce qui est absurde car $p_i \geqslant 2$.

1. $p \wedge a$ est un diviseur positif de $p$, donc vaut $1$ ou $p$. S'il vaut $p$, alors $p \mid a$.

2. Si $p \nmid a$, alors $p \wedge a = 1$ d'après 1, et le lemme de Gauss donne $p \mid b$.

3. Par récurrence sur $s$ à partir de 2, $p$ divise l'un des $q_j$. Or les diviseurs positifs de $q_j$ sont $1$ et $q_j$, et $p \geqslant 2$, donc $p = q_j$.

4. Si $p \neq q$ sont premiers, $p \nmid q$ (sinon $p = q$), donc $p \wedge q = 1$ d'après 1.

Existence, par récurrence forte sur $n \geqslant 2$. Si $n$ est premier, l'écriture $n = n$ convient. Sinon, $n = ab$ avec $2 \leqslant a, b < n$ ; par hypothèse de récurrence, $a$ et $b$ sont des produits de nombres premiers, donc $n$ aussi. On regroupe ensuite les facteurs égaux.

Unicité. Il suffit de montrer que si $p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$ avec des premiers rangés dans l'ordre croissant au sens large ($p_1 \leqslant \dots \leqslant p_r$, $q_1 \leqslant \dots \leqslant q_s$), alors $r = s$ et $p_i = q_i$ pour tout $i$. On raisonne par récurrence forte sur $n$, la valeur commune des deux produits.

$p_1$ divise $q_1 \cdots q_s$, donc $p_1 = q_j$ pour un certain $j$, d'où $p_1 \geqslant q_1$. Symétriquement, $q_1 = p_i$ pour un certain $i$, d'où $q_1 \geqslant p_1$. Ainsi $p_1 = q_1$. En simplifiant : $p_2 \cdots p_r = q_2 \cdots q_s = n/p_1$.

Si $n/p_1 = 1$, les deux produits sont vides : $r = s = 1$. Sinon $2 \leqslant n/p_1 < n$, et l'hypothèse de récurrence donne $r - 1 = s - 1$ et $p_i = q_i$ pour $i \geqslant 2$.

1. Écrivons $a = p^\alpha a'$ et $b = p^\beta b'$ avec $\alpha = v_p(a)$, $\beta = v_p(b)$, $p \nmid a'$, $p \nmid b'$. Alors $ab = p^{\alpha+\beta} a'b'$ et, par le lemme d'Euclide, $p \nmid a'b'$. Si $p^{\alpha+\beta+1}$ divisait $ab$, on aurait $p \mid a'b'$ après simplification. Donc $v_p(ab) = \alpha + \beta$.

2. Si $b = ka$, alors $k \neq 0$ et $v_p(b) = v_p(k) + v_p(a) \geqslant v_p(a)$. Réciproquement, si $v_p(a) \leqslant v_p(b)$ pour tout $p$, l'entier $k = \prod_p p^{v_p(b) - v_p(a)}$ vérifie $|b| = k|a|$, donc $a \mid b$.

3. Soit $\delta = \prod_p p^{\min(v_p(a), v_p(b))}$. D'après 2, $\delta$ divise $a$ et $b$. Si $c > 0$ divise $a$ et $b$, alors $v_p(c) \leqslant \min(v_p(a), v_p(b))$ pour tout $p$, donc $c \mid \delta$ et $c \leqslant \delta$. Ainsi $\delta = a \wedge b$. Le raisonnement est analogue pour le PPCM avec le $\max$.

Cas $a \in \mathbb{N}$, par récurrence sur $a$. Pour $a = 0$ : $0^p = 0$. Supposons $a^p \equiv a \;[p]$. Par la formule du binôme, $$(a+1)^p = a^p + 1 + \sum_{k=1}^{p-1} \binom{p}{k} a^k.$$ D'après le lemme, chaque terme de la somme est divisible par $p$. Donc $(a+1)^p \equiv a^p + 1 \equiv a + 1 \;[p]$.

Cas $a \in \mathbb{Z}$ quelconque. Soit $r \in \{0, \dots, p-1\}$ le reste de $a$ modulo $p$. Alors $a^p \equiv r^p \equiv r \equiv a \;[p]$, en utilisant le cas précédent pour $r \in \mathbb{N}$.

Point 2. On a $p \mid a^p - a = a(a^{p-1} - 1)$. Si $p \nmid a$, alors $p \wedge a = 1$, et le lemme de Gauss donne $p \mid a^{p-1} - 1$.