Histoire des mathématiques Théorème

division euclidienne

Théorème

opération qui, à deux entiers naturels (ou relatifs) appelés dividende et diviseur, associe deux autres entiers appelés quotient et reste

Son histoire

En Égypte, on savait déjà mesurer 30 avec une unité de 7, bien avant Euclide. Le reste de l'opération pousse les arpenteurs à approfondir les fractions. Une démarche analogue existe à Babylone. En Chine, une méthode proche de notre division posée nomme la quantité à partager, celle qui divise et le résultat provisoire.

Vers 300 avant notre ère, Euclide cherche dans ses Éléments le plus grand nombre qui en divise exactement deux autres. Son procédé porte le nom de « soustraction réciproque » chez les Grecs. À chaque étape, on retire la plus petite quantité à l'autre, là où nous ferions une division.

Quelques siècles plus tard, le procédé est retrouvé séparément en Inde et en Chine pour l'astronomie et les calendriers. Au Ve siècle, Aryabhata le surnomme le « pulvérisateur », tant il est efficace dans les calculs en nombres entiers. En Europe, diviser reste longtemps une affaire de spécialistes. Fibonacci y introduit les chiffres indo-arabes au XIIIe siècle.

La division « en galère » laisse une silhouette de bateau, faite de chiffres barrés et empilés. Elle demande moins d'écriture que notre manière de poser l'opération. Son origine reste discutée : longtemps tenue pour arabe, elle serait chinoise selon les recherches de Lam Lay Yong. Certaines écoles d'Afrique du Nord l'enseignent encore.

L'expression « division euclidienne » n'apparaît qu'au XXe siècle. L'appellation s'impose pour distinguer cette opération des autres façons de diviser.

Sources : J.-P. Escofier, Petite histoire des mathématiques (2016) ; A. Dahan-Dalmedico et J. Peiffer, Une histoire des mathématiques (1986) ; Wikipédia, articles « Division euclidienne », « Algorithme d'Euclide », « Anneau euclidien », « Euclidean division » et « Galley division ».

Énoncé

$$a,b \in \mathbb{Z} \land b \neq 0 \implies \exists! q,r \mid a=bq+r \land 0 \leq r < |b|$$

Pour comprendre

Conditions d'application

  • Le diviseur \(b\) doit être non nul.
  • C'est l'encadrement \(0 \le r < |b|\) qui rend le quotient et le reste uniques ; sans lui, plusieurs écritures existent, comme \(17 = 5 \times 3 + 2 = 5 \times 4 - 3\).
  • Hors des entiers, par exemple pour les polynômes, une division euclidienne existe dès qu'on dispose d'une taille qui permet de dire que le reste est plus petit que le diviseur, comme le degré pour les polynômes.

Cas d’usage

  • Convertir une durée en heures, minutes et secondes : on divise le nombre total de secondes par 3600 puis par 60, et chaque quotient, avec son reste, donne l'unité correspondante.
  • Informatique : écrire un nombre en base 2 ou en base 16 revient à enchaîner des divisions successives ; c'est aussi ce que calculent les opérateurs de quotient et de reste de la plupart des langages de programmation.
  • Clés de contrôle des identifiants (ISSN, numéro de sécurité sociale) : le ou les derniers chiffres d'un identifiant sont calculés à partir du reste d'une division par un nombre fixé, ce qui permet de repérer automatiquement une erreur de saisie.
  • Chiffrement RSA : chiffrer un message revient à élever un nombre à une puissance puis à garder le reste de sa division par un très grand nombre ; ce reste, c'est la division euclidienne qui le fournit.
  • Calculer le plus grand diviseur commun de deux nombres : l'algorithme d'Euclide divise le plus grand par le plus petit, recommence avec le diviseur et le reste, et s'arrête sur un reste nul ; le dernier reste non nul est le plus grand diviseur commun, car \(\mathrm{PGCD}(a,b) = \mathrm{PGCD}(b,r)\).

Liens

porte le nom de

Sources