L’Algorithme de la Division

Dans ce cours, nous développerons l’algorithme de la division comme le principe qui formalise, pour les entiers, la décomposition unique b=qa+r avec 0\le r<|a|. On démontre d’abord l’existence du quotient et du reste, puis leur unicité. Enfin, on interprète la signification du reste, on relie la théorie à l’algorithme long de la division en tant que procédure de calcul, et on anticipe sa connexion naturelle avec l’arithmétique modulaire et les applications informatiques.

Objectifs d’Apprentissage

À l’issue de ce cours, l’étudiant sera capable de :

1. Identifier les concepts et rôles de base de la division entière (dividende, diviseur, quotient, reste) ainsi que la notion de divisibilité comme cas exact.
2. Expliquer l’énoncé de l’algorithme/théorème de la division euclidienne, y compris les conditions qui fixent le reste (0\le r<|a|) et leur objectif d’éviter les ambiguïtés.
3. Appliquer la décomposition euclidienne b=qa+r pour déterminer q et r dans des exemples concrets, en vérifiant la borne du reste.
4. Analyser le traitement des cas selon le signe du dividende et du diviseur, en justifiant pourquoi la convention euclidienne maintient un reste non négatif.
5. Exécuter l’algorithme long de la division comme procédure mécanique fondée sur la représentation positionnelle afin d’obtenir q et r.

INDEX DES CONTENUS:
Division et divisibilité
Théorème de la division euclidienne
Démonstration de la division euclidienne
Interprétation du quotient et du reste
Algorithme long de la division
Conclusion
Exercices proposés et résolus

Division et divisibilité

En arithmétique, la divisibilité décrit le cas « exact » : a\mid b signifie que b s’écrit exactement comme un multiple de a. Cependant, même s’il n’y a pas toujours divisibilité entre deux entiers quelconques, nous pouvons encore nous demander « combien de fois un nombre tient dans un autre et, s’il n’y tient pas exactement, ce qu’il en reste ». C’est dans ce contexte qu’apparaît l’algorithme de la division, qui garantit qu’un entier quelconque b peut s’écrire comme un multiple de a plus un « reste ».

À titre d’exemple, considérons a=3 et b=16. Il est clair que 3 ne divise pas 16. Toutefois, il est possible de trouver un quotient et un reste pour l’opération de division, car

16 = 5\cdot 3 + 1

En conséquence, en divisant b=16 par a=3 (où b est le dividende et a est le diviseur), représenté par 16/3 ou 16\div 3, on obtient comme quotient q=5 et comme reste r=1. En général, l’algorithme de la division affirme que, pour tous entiers a (diviseur) et b (dividende) avec a\neq 0, il existe des entiers uniques q et r tels que

b=qa+r,\qquad 0\le r<|a|

Dans cet exemple, 16=3\cdot 5+1, et la condition 0\le r<|a| est vérifiée car 0\le 1<3. Cette formulation évite les ambiguïtés lorsque le diviseur (ou le dividende) peut être négatif et garantit que le reste est toujours non négatif et strictement inférieur à la valeur absolue du diviseur.

Théorème de la division euclidienne

Le résultat de l’application de l’algorithme de la division est ce que l’on appelle la division euclidienne, et il repose sur le résultat suivant.

Théorème : Soient a,b\in\mathbb{Z} avec a\neq 0. Alors il existe des q,r\in\mathbb{Z} uniques tels que

b=qa+r,\qquad 0\le r<|a|.

L’entier q est appelé quotient et r est appelé reste de la division de b par a.

Démonstration de la division euclidienne

Cette démonstration se divise en deux parties : on démontre d’abord que le quotient et le reste existent ; puis, étant donné qu’ils existent, qu’ils sont uniques.

Existence

Soient a,b\in\mathbb{Z} avec a\neq 0 et définissons d=|a|, de sorte que d>0. Nous traiterons d’abord le cas b\ge 0 : nous montrerons qu’il existe des q,r\in\mathbb{Z} tels que b=dq+r et 0\le r<d. Nous traiterons ensuite le cas b<0. Enfin, nous remplacerons d par |a| afin d’obtenir la forme b=qa+r avec 0\le r<|a|.

Pour b\in\mathbb{Z} avec b\ge 0, nous établissons la proposition P(b) : « il existe des q,r\in\mathbb{Z} tels que b=dq+r et 0\le r<d ». Nous démontrerons par récurrence que P(b) est valable pour tout b\ge 0.

Cas de base : Pour b=0, en prenant q=0 et r=0, on obtient 0=d\cdot 0+0 et 0\le 0<d. Par conséquent, P(0) est vraie.

Étape inductive : Soit k\ge 0 et supposons que P(k) est vraie. Il existe alors des q,r\in\mathbb{Z} tels que

k=dq+r,\qquad 0\le r<d.

En ajoutant 1 aux deux membres, on obtient

k+1=dq+(r+1).

De plus, de 0\le r<d, il découle que r+1\le d. En conséquence, seuls les cas r+1<d ou r+1=d peuvent se produire.

Cas 1 : Si r+1<d, nous définissons q'=q et r'=r+1. Alors

k+1=dq'+r',\qquad 0\le r'<d.

Cas 2 : Si r+1=d, alors k+1=dq+d=d(q+1)+0. Nous définissons q'=q+1 et r'=0, et l’on a

k+1=dq'+r',\qquad 0\le r'<d.

Dans les deux cas, nous avons construit des entiers q',r' tels que k+1=dq'+r' et 0\le r'<d. Par conséquent, P(k+1) est vraie. Nous concluons par récurrence que P(b) est valable pour tout b\ge 0.

Considérons maintenant le cas b<0. Alors -b>0. En appliquant le résultat précédent à -b, il existe des q,r\in\mathbb{Z} tels que

-b=dq+r,\qquad 0\le r<d.

En multipliant par -1, on obtient

b=-dq-r.

Si r=0, il suffit de prendre q_1=-q et r_1=0, ce qui donne b=dq_1+r_1 et 0\le r_1<d.

Si r>0, nous définissons q_1=-q-1 et r_1=d-r. Comme 0<r<d, on a 0<d-r<d, c’est-à-dire 0\le r_1<d. De plus,

dq_1+r_1=d(-q-1)+(d-r)=-dq-d+d-r=-dq-r=b.

En conséquence, pour tout b\in\mathbb{Z}, il existe des q_1,r_1\in\mathbb{Z} tels que b=dq_1+r_1 et 0\le r_1<d.

Enfin, rappelons que d=|a|. Si a>0, alors d=a et l’égalité b=dq_1+r_1 s’écrit b=aq_1+r_1, avec 0\le r_1<|a|.

Si a<0, alors d=-a et b=dq_1+r_1=(-a)q_1+r_1=a(-q_1)+r_1. En définissant q=-q_1 et r=r_1, on obtient

b=qa+r,\qquad 0\le r<|a|.

Ainsi est démontrée l’existence de q et r pour tous a,b\in\mathbb{Z} avec a\neq 0.

Unicité

Supposons qu’il existe des q,q',r,r'\in\mathbb{Z} tels que

b=qa+r=q'a+r',\qquad 0\le r,r'<|a|.

En soustrayant les deux expressions, on obtient

a(q-q')=r'-r.

Comme 0\le r,r'<|a|, on a |r'-r|<|a|. En revanche, le membre de gauche est un multiple de a, et donc aussi un multiple de |a|. Le seul multiple entier de |a| dont la valeur absolue est strictement inférieure à |a| est 0 ; en effet, si |a| m \neq 0 avec m\in\mathbb{Z}, alors \big| |a| m \big| \ge |a| . Par conséquent, r'-r=0, c’est-à-dire r=r', et en remplaçant dans b=qa+r, on déduit q=q'. La décomposition est donc unique.

Interprétation du quotient et du reste

• Que signifie « reste ». Si b=qa+r, alors r=b-qa est ce qui « reste » lorsqu’on retranche de b le multiple qa. En d’autres termes, r est le résidu obtenu en ajustant b sur la grille des multiples de a.
• Pourquoi impose-t-on 0\le r<|a|. Sans cette condition, le couple (q,r) ne serait pas unique. En effet, si b=qa+r, alors on a aussi b=a(q+1)+(r-a). La condition 0\le r<|a| force le reste à appartenir à une fenêtre fixe \{0,1,2,\dots,|a|-1\}, ce qui bloque les infinies « ré-étiquetages » d’un même nombre.
• Que se passe-t-il si a est négatif. Le théorème reste valable sans modification : le reste demeure non négatif et borné par |a|. Cela est pertinent car certains langages de programmation utilisent la troncature vers zéro et peuvent produire des restes négatifs, tandis qu’en mathématiques on adopte la convention 0\le r<|a| afin que le reste soit un représentant « standard ».

  De plus, lorsque a>0, le quotient coïncide avec la partie entière inférieure :

  q=\left\lfloor \frac{b}{a}\right\rfloor,\qquad r=b-a\left\lfloor \frac{b}{a}\right\rfloor.

Algorithme long de la division

À partir de la division euclidienne, il est possible de mettre en œuvre l’algorithme long de la division, en exploitant la représentation positionnelle des nombres. Cet algorithme est une technique de calcul qui permet de trouver rapidement les valeurs q et r lorsqu’on souhaite calculer b\div a avec a,b\in\mathbb{Z} et a\neq 0.

Pour le décrire, examinons d’abord quelques exemples qui illustrent le processus et les situations possibles au cours de l’exécution de l’algorithme.

1. Supposons que nous souhaitions calculer 57\div 4. Ici, 57 est le dividende et 4 le diviseur. Pour y parvenir, nous effectuerons la séquence de calculs suivante :

   \begin{array}{rll} (1) & \color{red}57 \div 4 =\color{black} \\ & \text{Écrire l’opération de division.} \\ \\ (2) & \color{red}5'\color{black}7 \div 4 = \\ & \text{Séparer le premier préfixe (depuis la gauche) du dividende qui}\\ &\text{soit supérieur ou égal au diviseur, en l’occurrence 5.} \\ \\ (3) & 5'7 \div 4 = \color{red}1\color{black} \\ & \text{Chercher le plus grand nombre qui, multiplié par $4$,}\\ &\text{soit inférieur ou égal à $5$ et l’écrire à droite de l’égalité. C’est 1.} \\ \\ (4) & \begin{array}{ll}\phantom{-|}5'7 \div 4 &= 1 \\ \color{red}-|\underline{4}\color{black} & \\ \color{red}\phantom{-|}1\color{black} & \end{array} \\ & \text{Multiplier le résultat par le diviseur et le soustraire de la valeur sélectionnée.} \\ \\ (5) & \begin{array}{ll}\phantom{-|}5'\color{red}7'\color{black} \div 4 &= 1 \\ -|\underline{4} & \\ \phantom{-|}1\color{red}7\color{black} & \end{array} \\ & \text{Sélectionner et « abaisser » le chiffre suivant.} \\ \\ (6) & \begin{array}{ll}\phantom{-|}5'7' \div 4 &= 1\color{red}4\color{black} \\ -|\underline{4} & \\ \phantom{-|}17 & \\ \color{red}-|\underline{16}\color{black} & \\ \color{red}\phantom{-|}1\color{black} \end{array} \\ & \text{Répéter la séquence avec le dernier nombre obtenu.} \end{array}

   L’algorithme se termine lorsque tous les chiffres à « abaisser » ont été épuisés, donnant comme résultat le quotient q=14 et le reste r=1. En particulier, le reste sera toujours inférieur au diviseur.

2. Supposons que nous souhaitions calculer 132\div 5. Pour y parvenir, nous effectuerons la séquence de calculs suivante :

   \begin{array}{rl} (1) &1'32 \div 5 = \\ & \text{Séparer le premier préfixe du dividende et chercher un entier naturel qui,}\\ & \text{multiplié par 5, soit inférieur ou égal à celui-ci. Si cela n’est pas possible,}\\ & \text{incorporer le chiffre suivant jusqu’à ce que cela le soit.} \\ \\ (2) &\begin{array}{ll}\phantom{-|}13'2 \div 5 &= 2 \\ -|\underline{10} & \\ \phantom{-|1}3 & \end{array}\\ & \text{Lorsque l’étape précédente fonctionne, exécuter l’algorithme normalement.} \\ \\ (3) &\begin{array}{ll}\phantom{-|}13'2' \div 5 &= 26 \\ -|\underline{10} & \\ \phantom{-|1}32 & \\ \phantom{\,} -|\underline{30} & \\ \phantom{-|30} 2 & \end{array} \end{array}

3. Si le dividende comporte davantage de chiffres, la procédure s’exécute de la même manière. Par exemple, en calculant 3521\div 12, on obtient :

   \begin{array}{ll} \phantom{-|}35'2'1' \div 12 & = 293 \\ -|\underline{24} & \\ \phantom{-|}112 & \\ -|\underline{108} & \\ \phantom{-|10}41 & \\ \phantom{0}-|\underline{36} & \\ \phantom{10-|}5 & \\ \end{array}

4. Si l’un des nombres est négatif, il existe deux façons acceptables de présenter le résultat. Toutefois, la forme standard en théorie des nombres est celle dans laquelle le reste est positif et, par conséquent, cohérente avec la division d’Euclide. Par exemple, si nous calculons -598\div 21, on obtient les développements possibles suivants, tous deux corrects comme identités :

   • Avec reste négatif : Celui-ci s’obtient en supprimant le signe au début de l’opération et en le rétablissant à la fin.

     \begin{array}{ll} \phantom{-}59'8' \div 21 &= 28 \\ -|\underline{42} & \\ \phantom{-|'}178 & \\ \phantom{\,}-|\underline{168} & \\ \phantom{-|00}10 & \\ \end{array}

     À partir de cela, on a :

     598 = 21 \times 28 + 10

     Puis, si l’on multiplie toute l’égalité par -1, on obtient :

     -598 = 21 \times (-28) - 10

     De sorte que, dans cette représentation, le résultat de -598\div 21 est le quotient q=-28 et le reste r=-10.

     Et si l’on multiplie de nouveau toute l’égalité par -1, on obtient :

     598 = (-21)\times(-28) + 10

     De sorte que le résultat de 598\div (-21) est le quotient q=-28 et le reste r=10.

   • Avec reste positif et cohérent avec la division d’Euclide : À partir du développement précédent, on a :

     -598 = 21 \times (-28) - 10

     Puis, en ajoutant 0=21-21 au membre droit de cette égalité, on obtient :

     -598 = 21 \times (-28) - 10 \color{red}+ 21 - 21\color{black} = 21\times(-29) + 11

     Par conséquent, en restant cohérents avec la division d’Euclide, le résultat du calcul -598\div 21 donne un quotient q=-29 et un reste r=11.

   En ce qui concerne la convention de la division d’Euclide, seul le résultat avec reste positif correspond au quotient et au reste euclidiens. Toutefois, les deux expressions sont des identités correctes et peuvent être utiles dans des contextes différents. Bien que l’algorithme de la division longue puisse produire des restes négatifs, cela s’avère pratique pour obtenir des résultats de manière mécanique et effectuer des manipulations algébriques sans étapes supplémentaires. En revanche, les résultats avec reste positif, cohérents avec la division d’Euclide, permettent de fixer un représentant canonique de chaque classe résiduelle (par exemple, dans \{0,1,\dots,n-1\}), ce qui facilite l’étiquetage des entiers de manière précise et sans ambiguïté. Il convient de noter qu’il existe également d’autres conventions de représentants, telles que les résidus symétriques, tout aussi valides une fois la règle fixée.

Conclusion

L’algorithme de la division garantit que toute division entière peut être exprimée de manière unique sous la forme b=qa+r avec 0\le r<|a|, ce qui fixe un critère standard pour interpréter le quotient et le reste même lorsque des nombres négatifs interviennent. L’algorithme long de la division n’est rien d’autre qu’une implémentation pratique de cette décomposition, fondée sur la représentation positionnelle, et permet de calculer q et r de manière mécanique. Enfin, cette forme euclidienne évite non seulement les ambiguïtés, mais se connecte également de manière naturelle à l’arithmétique modulaire : le reste r agit comme un représentant canonique de la classe résiduelle de b modulo a, base de nombreuses techniques en théorie des nombres et en applications informatiques qui pourront être examinées dans de prochaines livraisons.

Exercices proposés et résolus

Division euclidienne

1. (résolu) Trouver q et r tels que

   137 = 9q + r,\qquad 0\le r\lt 9.

   Solution : Cherchez le plus grand nombre qui, multiplié par 9, ne dépasse pas 137. On a 15\times 9 = 135 et 16\times 9 = 144 ; par conséquent, le quotient recherché est q=15. Calculez maintenant le reste r=137-9q et vérifiez que 0\le r\lt 9. En effectuant la vérification, on obtient :

   r=137-9\cdot 15=137-135=2.

   Par conséquent, 137=9\cdot 15+2 avec 0\le 2\lt 9.

2. (résolu) Trouver q et r tels que

   2025 = 37q + r,\qquad 0\le r\lt 37.

   Solution : Cherchez le plus grand nombre qui, multiplié par 37, ne dépasse pas 2025. On observe que 37\times 54 = 1998 et 37\times 55 = 2035 ; par conséquent, le quotient recherché est q=54. Calculez maintenant le reste r=2025-37q et vérifiez que 0\le r\lt 37. En effectuant la vérification, on obtient :

   r=2025-37\cdot 54=2025-1998=27.

   Par conséquent, 2025=37\cdot 54+27 avec 0\le 27\lt 37.

3. Trouver q et r tels que

   745 = 23q + r,\qquad 0\le r\lt 23.

4. Trouver q et r tels que

   -314 = 11q + r,\qquad 0\le r\lt 11.

5. Trouver q et r tels que

   598 = (-21)q + r,\qquad 0\le r\lt |-21|.

6. Reste fixé et recherche d’entiers. Soit a=12.

   (a) Décrire l’ensemble de tous les entiers b dont la division euclidienne par 12 a pour reste r=5.

   (b) Trouver le plus petit entier b\gt 1000 satisfaisant cette condition et déterminer le quotient q correspondant.

Algorithme long de la division

Dans chaque cas, appliquer l’algorithme long de la division pour calculer le quotient q et le reste r. Transformer le résultat en division euclidienne lorsque l’algorithme fournit un reste négatif.

1. 84\div 6.
2. 197\div 8.
3. 1256\div 7.
4. -3521\div 12.
5. -98765\div 24.
6. 845\div -13.
7. -12345\div -37.