Division euclidienne

Il s'agit de formaliser avec précision la bonne vieille division euclidienne, celle que vous connaissez depuis l'école primaire.

Théorème 2   Soit $a$ un entier (relatif) et $b\geqslant 1$ un entier strictement positif. Alors il existe un couple $(q,r)$ unique (d'entiers) vérifiant la double condition :

$$a=bq+r\qquad{\rm et}\qquad 0\leqslant r < b.$$

Démonstration : On va prouver successivement l'existence et l'unicité de $(q,r)$.

Existence de $(q,r)$ : la démonstration se prête bien à discuter selon le signe de $a$. Le cas où $a\geqslant 0$ est le cas contenant l'essentiel de la démonstration ; lorsque $a<0$, on ne peut utiliser mot à mot la même preuve, mais on se ramène alors sans mal au cas intéressant déjà traité.

$\bullet$ Premier cas (le cas significatif) : si $a\geqslant 0$.

L'idée de la démonstration est de dire que le quotient de $a$ par $b$ est le plus grand entier $q$ tel que $bq$ soit encore plus petit que $a$.

Introduisons donc l'ensemble $A=\{c\in\mathbb{N} ,\;bc\leqslant a\}$. L'ensemble $A$ est un ensemble d'entiers naturels ; il est non vide, car il contient 0. Il est fini : en effet soit $d$ un entier tel que $d\geqslant a+1$ ; on a alors $bd\geqslant b(a+1) \geqslant a+1 > a$, donc $d\not\in A$ et ainsi $A$ ne contient que des entiers inférieurs ou égaux à $a$.

L'ensemble $A$ possède donc un plus grand élément $q$. Posons $r=a-bq$. La première condition sur $(q,r)$ est alors évidemment vérifiée, c'est la seconde qui nécessite une vérification.

Comme $q\in A$, par définition de $A$, on a $bq\leqslant a$. Donc $r=a-bq\geqslant 0$.

Comme $q$ est maximal parmi les éléments de $A$, $q+1\not\in A$. Donc $b(q+1)>a$, donc $r=a-bq<b$.

L'existence est démontrée dans ce cas.

$\bullet$ Second cas (preuve sans imagination) : si $a<0$.

Posons $a'=a(1-b)$. Comme $a<0$ et $1-b\leqslant 0$, on obtient $a'\geqslant 0$.

On peut donc, en appliquant le premier cas, faire la division euclidienne de $a'$ par $b$ ; notons $(q',r)$ le couple ainsi obtenu : on a alors $a'=bq'+r$, avec en outre $0\leqslant r < b$. En réinjectant la définition de $a'$, on écrit alors $a-ba=bq'+r$, donc $a=b(q'+a)+r$. Si on pose $q=q'+a$, on constate qu'on a réussi la division euclidienne de $a$ par $b$.

Unicité de $(q,r)$ : soit $(q_1,r_1)$ et $(q_2,r_2)$ des couples vérifiant les deux conditions exigées dans l'énoncé du théorème.

On déduit de $a=bq_1+r_1=bq_2+r_2$ que $b(q_1-q_2)=r_1-r_2$. Ainsi, $r_1-r_2$ est un multiple de $b$.

Des conditions $0\leqslant r_1$ et $r_2<b$, on déduit que $-b<r_1-r_2$.

Des conditions $r_1<b$ et $0\leqslant r_2$, on déduit que $r_1-r_2<b$.

Ainsi $r_1-r_2$ est un multiple de $b$ compris strictement entre $-b$ et $b$. La seule possibilité est que $r_1-r_2$ soit nul. On en déduit $r_1=r_2$, puis, en allant reprendre l'égalité $b(q_1-q_2)=r_1-r_2$, que $q_1=q_2$.$\square$