Division euclidienne
On suppose connue la construction de $\mathbb{N}$ (avec les cinq axiomes de Peano).
- (Théorème fondamental de $\mathbb{N}$)
-
Toute partie non vide de $\mathbb{N}$ admet un plus petit élément.
-
.....................
- (Corolaire du théorème fondamental de $\mathbb{N}$)
-
Toute partie de $\mathbb{N}$ non vide et majorée admet un plus grand élément.
-
.....................
- (Théorème de la division euclidienne)
-
$\forall \left(a ; b\right) \in \mathbb{N} \times \mathbb{N}^*,\ \exists ! \left(q ; r\right) \in \mathbb{N}^2,$
- $a = bq + r$
- $0 \leqslant r \lt b$
$q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$.
-
Soient $\left(a ; b\right) \in \mathbb{N} \times \mathbb{N}^*$.
Soit $ A = \left\{q \in \mathbb{N} ~\middle|~ a \lt b(q+1) \right\} $.
Pour appliquer le théorème fondamental de $\mathbb{N}$, il faut d'abord montrer que $A \neq \emptyset$.
Si $a=0$, c'est évident car $\forall q \in \mathbb{N}, \ 0 \lt b(q+1)$ donc $b\neq 0$.
Sinon, on a $b \geqslant 1$, donc $a \in A$, donc $A \neq \emptyset$.
D'après le théorème fondamental de $\mathbb{N}$, soit $q$ le plus petit élément de $A$. Posons $r = a - bq$ et montrons que $0 \leqslant r \lt b$.
Comme $q$ est le plus petit élément de $A$, $q - 1 \notin A$, donc $a \geqslant b(q - 1 + 1) = bq$.
$ a \geqslant bq \Rightarrow a - bq \geqslant 0 \Rightarrow r \geqslant 0$
$ a \lt b(q + 1) \Rightarrow a - bq \lt b \Rightarrow r \lt b$
On a donc existence de $\left(q; r\right)$.
Montrons l'unicité : soit $\left(q_1; r_1\right) \in \mathbb{N}^2$ un autre couple vérifant le système :
$ \begin{cases}
a = bq + r \\
a = bq_1 + r_1
\end{cases}
\Rightarrow bq + r = bq_1 + r_1 \Rightarrow b(q - q_1) = r_1 - r$
$ \begin{cases}
0 \leqslant r1 \lt b \\
0 \leqslant r \lt b
\end{cases}
\Rightarrow \left|r_1 - r\right| \lt b$
Si $q - q_1 \neq 0$, on obtient $b\left|q - q_1\right| \geqslant b$, ce qui est une contradiction. Donc $q = q_1$, d'où $r = r_1$.
