La division euclidienne
Exemple :
Éline et Lucie montent un escalier comportant juste un peu moins de 40 marches.
Éline monte les marches 3 par 3, et Lucie, 2 par 2. Aucune d'entre elle n'arrive au sommet. Lorsqu'elles ne peuvent plus monter à leur rythme, elles arrivent toutes les deux sur la même marche.
Combien l'escalier possède t-il de marches ?
Pour résoudre ce type de problèmes, on fait appel à la division euclidienne sur les entiers : celle apprise à l'école primaire. Nous allons rappeler sa définition :
Définition : Propriété et définition de la division euclidienne
Soit \(a\) un entier relatif et \(b\) un entier naturel non nul.
Il existe un couple unique d'entiers \((q ; r)\) tels que \(a=bq+r\) avec \(0 \leqslant r < b\)
\(a\) est le dividende
\(b\) est le diviseur
\(q\) est le quotient de la division euclidienne de \(a\) par \(b\)
\(r\) est le reste.
Exemple :
\(40 = 3\times 13 + 1 = 2\times 2 + 0\)
\(37 = 3\times 12 + 1 = 2\times 18+ 1\)
37 est l'entier immédiatement inférieur à 40 pour lequel les restes des divisions par 2 et par 3 sont égaux. C'est la solution à notre problème d'escalier !
Ce résultat est bien sûr connu de vous depuis l'école primaire. Il n'en est pas trivial pour autant. Nous allons donc le démontrer. La propriété affirme deux choses : l'existence et l'unicité. Cela se rencontre souvent en mathématiques. La preuve comportera donc deux parties bien distinctes et nous commencerons par l'unicité qui est souvent plus simple...
Démonstration de l'unicité
Méthode :
Très souvent pour démontrer l'unicité d'un objet en mathématiques, on raisonne en supposant qu'il y a deux objets vérifiant la propriété étudiée et on finit par montrer que ces deux objets n'en sont qu'un.
On suppose qu'il existe deux couples \((q ; r)\) et \((q' ; r')\). vérifiant \(a = bq + r = bq' + r'\).
On a donc : \(b(q − q') = r' − r\).
Puisque \(q − q'\) est entier, \(r' − r\) est un multiple de \(b\).
Or on sait que \(0 \leqslant r' < b'\)
de même \(0 \leqslant r < b\) ce qui équivaut à \(-b < -r \leqslant 0\)
En ajoutant ces deux inégalités on obtient l'encadrement
\(-b < r'-r < b\)
Mais le seul multiple de \(b\) strictement compris entre \(-b\) et \(b\) est \(0\)
Donc \(r'-r = 0\) soit \(r=r'\)
Et puisque \(b(q − q') = r' − r = 0\) et que \(b\) est non nul, c'est que \(q=q'\).
Cela prouve l'unicité.
Démonstration de l'existence
On distingue 2 cas :
Premier cas : a est un multiple de b
Dans ce cas, il n'y a pas grand chose à faire : \(a = qb = qb+0\) ce qui prouve l'existence d'une forme du type \(a = bq+r\) avec \(r=0\).
Second cas : a n'est pas un multiple de b
La suite des multiples de b est :
\(\ldots ; - kb ;(-k-1) b ; \ldots ;-b ; 0 ; b ; 2b \ldots ; kb ; (k+1)b ; \ldots\)
Dans le cas où \(a\) n'est pas un multiple de \(b\), il existe des entiers de la suite des multiples de \(b\) qui sont inférieurs à \(a\), et d'autres qui sont supérieurs à \(a\). Ce dernier va donc se trouver encadré par deux termes consécutils de la suite :
\(\ldots < (q-1)b < qb < a < (q+1) b < \ldots\)
On définit ainsi un entier \(q\) tel que \(qb\) et \((q+1) b\) encadrent \(a\) :
\(qb < a < (q+1) b \Leftrightarrow 0 < a-qb < b\)
Posons alors \(r=a-qb\), on a alors \(0 < r < b\)
Conclusion
En faisant le bilan des deux cas, on a bien \(a = bq + r\) avec \(0 \leqslant r < b\), le cas \(r=0\) correspondant au cas ou \(b\) divise \(a\).