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 :

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


         © UJF Grenoble, 2011                              Mentions légales