Division euclidienne

thumb|Écriture de la division euclidienne de 30 par 7, le quotient est 4 et le reste 2.En mathématiques, et plus précisément en arithmétique, la division euclidienne ou division entière est une procédure de calcul qui, à deux entiers naturels appelés dividende et diviseur, associe deux autres entiers appelés quotient (quotient euclidien s'il y a ambiguïté) et reste. Initialement définie pour deux entiers naturels non nuls, elle se généralise aux entiers relatifs. Cette division est au fondement des théorèmes de l'arithmétique élémentaire et de l'arithmétique modulaire qui traite des congruences sur les entiers.

La division euclidienne s'étend aussi à d'autres anneaux, comme celui des polynômes, dits anneaux euclidiens.

En arithmétique Première approche thumb|Comment distribuer équitablement 30 billes entre 7 personnes ? Distribuer 4 billes à chacun et il reste 2 billes.30 = 7 × 4 + 2. La division euclidienne permet de répondre à des questions du type suivant : Distribution équitable : Comment distribuer équitablement 30 billes entre 7 personnes ? On donne 1 bille à chacune des 7 personnes. On a alors distribué 7 billes. Il reste 23 billes. On recommence en distribuant encore 1 bille à chacune des 7 personnes. Celles-ci possèdent alors chacune 2 billes et il en reste 16 dans le sac… Finalement, chaque personne possède 4 billes et il en reste 2 dans le sac. On dit alors que la division de 30 par 7 a pour quotient 4 et pour reste 2 et l'on écrit :

On aurait pu, à chaque étape, écrire : . Ces égalités sont exactes mais ne correspondent pas à une division euclidienne, celle-ci consistant à "épuiser" les billes entre les joueurs. La distribution ne sera complète que lorsque le nombre de billes restantes sera inférieur au nombre de joueurs, ici 7. Le principe même de cette division interdit que l'on puisse diviser un nombre par 0.

Origine historique Le nom de division euclidienne est un hommage rendu à Euclide qui pose les fondements de l'arithmétique dans ses Éléments. Mais elle apparaît très tôt dans l'histoire des mathématiques. Caveing en signale la présence dans les mathématiques égyptiennes où il s'agit par exemple de mesurer 30 avec l'unité 7.. Par ailleurs, la présence d'un reste a conduit les arpenteurs égyptiens à approfondir le concept de fraction. Une démarche analogue existe dans les mathématiques babyloniennes. On retrouve cette procédure décrite dans les mathématiques chinoises avec un algorithme proche du système actuel consistant à poser une division. Les Chinois ont un mot pour désigner le dividende, le diviseur et le quotient en cours de calcul, p. 16-20..

Théorème de la division euclidienne Dans les entiers naturels Le théorème de la division euclidienne dans les entiers naturels (les nombres entiers pris à partir de 0) s'énonce ainsi. À deux entiers et , on associe de façon unique deux entiers naturels, le quotient et le reste , qui vérifient : ; . Autrement dit : il existe un unique entier naturel tel que

ou encore . Cet entier est déterminé par : est le plus grand multiple de inférieur ou égal à .

Extension aux entiers relatifs Le théorème de la division euclidienne peut s'étendre aux entiers relatifs de la manière suivanteDivision euclidienne, Université de Lyon-1, th.2.1. À deux entiers relatifs et , , on associe de façon unique un entier relatif (le quotient) et un entier naturel (le reste) qui vérifient des conditions analogues (celle pour le reste doit être précisée) : ; . Par exemple la division de –17 par 5 donne , soit un quotient de –4 et un reste de 3. la division de 17 par –5 donne , soit un quotient de –3 et un reste de 2. la division de –17 par –5 donne , soit un quotient de 4 et un reste de 3.

En restreignant ce théorème aux entiers positifs ou nuls, on obtient bien le théorème précédent pour les entiers naturels. Il s'en déduit en distinguant suivant les signes de et , ou se démontre directement de façon analogue.

Cette définition assure l'unicité du quotient et du reste mais ne correspond plus à la définition générale de la division dans un anneau euclidien à l'aide d'un stathme euclidien qui donnerait la définition suivanteAnneaux et corps, Irem, Université de la Réunion, p.3 §3, b). : À deux entiers relatifs et , , on associe tout couple d'entiers relatifs (le quotient) et (le reste) vérifiant ; . Avec cette acception plus générale, on aurait aussi pour la division de –17 par 5, , soit un quotient de –3 et un reste de –2. C'est cette non-unicité qui explique le caractère non-univoque de sa mise en œuvre informatique.

Utilisation La division euclidienne est un outil de base de l'arithmétique. Elle permet de déterminer le PGCD de deux nombres en utilisant l'algorithme d'Euclide. Elle est également utilisée pour écrire un entier en base b.

Elle est à l'origine d'une branche de l'arithmétique, l'arithmétique modulaire, dans laquelle on s'intéresse non pas au quotient de la division de a par n mais à son reste. On dit que deux nombres a et a sont congrus modulo n si et seulement s'ils ont même reste dans la division par n. Cette propriété se transmet à la somme et au produit : si a et a ont même reste modulo n et s'il en est de même de b et b, alors ab a même reste que ab modulo n et a + b a même reste que a + b modulo n.

Cette transmissibilité permet le développement d'une arithmétique sur les restes et la création d'un ensemble nouveau, l'anneau ℤ/nℤ.

Mise en œuvre informatique de la division euclidienne Les divisions entières peuvent réserver parfois des surprises lorsqu'on utilise les fonctions intégrées dans les langages de programmation ou les logiciels de calcul, en particulier lorsque le diviseur ou le dividende sont négatifs.

Ainsi, dans le tableur Excel, la fonction « MOD » a pour objet de retourner le reste d'une division euclidienne. La convention choisie par le concepteur consiste à prendre toujours un reste du même signe que le diviseurComment utiliser la formule MOD() pour calculer le reste d'une division euclidienne sur Excel - Excel formation. Dans une cellule de feuille de calcul, la formule « =MOD(-201;23) » a pour résultat le reste 6 de la division de –201 par 23, conformément à la définition ci-dessus, mais la formule « =MOD(10;-3)» a pour résultat le reste -2 . En langage de macro VBA Excel, l'instruction « R = -201 MOD 23 » donne pour résultat –17, soit l'opposé du reste de la division de 201 par 23. En langage C, le choix du signe du reste et de la valeur du quotient, dans le cas de diviseur ou dividende négatif, dépend de la machine sur laquelle le programme fonctionneBrian W. Kernigan et Dennis M. Ritchie, The C Programming Language p.39 2.5 Arithmetics operators. .

Généralisations

Division euclidienne polynomiale

Si les polynômes ont pour coefficients des éléments d'un corps commutatif K, on peut définir une division euclidienne sur les polynômes appelée division selon les puissances décroissantes.

À deux polynômes A et B à coefficients dans un corps K, avec B non nul, la division euclidienne associe un quotient Q et un reste R, tous deux polynômes, vérifiant :

L'unicité d'un couple (Q, R) vérifiant ces propriétés est garantie par les lois d'anneau (unitaire), en revanche il est nécessaire que K soit un corps pour que l'existence le soit aussi. Sinon la division est encore parfois possible, si par exemple le coefficient du monôme dominant de B est égal à 1, ou plus généralement si ce coefficient est inversible.

Anneau euclidien

La construction d'une division euclidienne dans un anneau intègre A nécessite l'existence d'une application de A\{0} dans ℕ appelée stathme euclidien et vérifiant, pour tous éléments a et b non nuls si b divise a alors (b) ≤ (a) ; si b ne divise pas a alors il existe q et r dans A vérifiant les deux propriétés a = bq + r (r) < (b). S'il existe un stathme euclidien sur l'anneau A, l'anneau est appelé anneau euclidien. Ainsi dans l'anneau des entiers relatifs, le stathme choisi était la valeur absolue et dans celui des polynômes, le stathme était le degré du polynôme.

La définition d'un stathme euclidien diffère d'un auteur à l'autre. Les rapports logiques entre les différentes définitions sont abordés dans l'article détaillé.

Algorithmes de calcul On s'intéresse au calcul de division euclidienne de deux entiers, connaissant au préalable les opérations d'addition, de soustraction, de multiplication, et de comparaison, entre des nombres entiers. Il est facile de ramener le problème à deux entiers positifs, et on se restreint à ce cas.

Les algorithmes décrits ci-dessous calculent le quotient de la division euclidienne ; il est bien clair que le reste s'en déduit. Attention, le contraire ne serait pas vrai.

La première méthode, naturelle mais naïve, demande beaucoup trop de calculs pour des grands nombres. On présente ensuite deux méthodes courantes, de complexité semblable : la première convient pour des calculs en base 2, et donc pour une programmation informatique ; la deuxième méthode, essentiellement équivalente, est une adaptation pour la base de numération habituelle, la base décimale, et convient donc pour des calculs à la main. C'est l'algorithme enseigné à l'école.

Méthode naïve C'est la méthode décrite par Euclide dans sa recherche d'un pgcd. Elle procède par soustractions successives. Pour effectuer la division euclidienne de a par b, on soustrait b à a, et on recommence tant que cela est possible.

On construit ainsi une suite arithmétique strictement décroissante (a ) de raison –b :

. Il existe donc un plus petit entier tel que , c'est-à-dire vérifiant , ce qui s'écrit encore .

Le quotient de la division cherchée est donc , et le reste .

Le nombre de pas de cet algorithme est donc , c'est-à-dire la partie entière de ; chaque étape requiert une soustraction et une comparaison. La complexité de calcul croît linéairement avec , c'est-à-dire exponentiellement avec la taille de — si l'on convient de mesurer la taille d'un entier par le nombre de chiffres que requiert son développement binaire (ou décimal si on préfère, cela ne modifie les choses que d'une constante), cette taille est de l'ordre du logarithme de l'entier.

Méthode binaire

Ce principe est à l'origine de la technique de la division dans l'Égypte antique, .. Il s'appuie sur une construction à l'envers d'une multiplication égyptienne et consiste à remplir un tableau donnant les puissances de 2 et leur produit par b. On s'arrête juste avant de dépasser a dans la seconde colonne. On essaie ensuite de constituer le plus grand multiple de b inférieur à a en sommant certaines cases de la seconde colonne. En sommant les cases correspondantes de la première colonne on obtient le quotient de la division.

Ainsi pour diviser 93 par 7 on remplit le tableau suivant : 17214428856

Pour construire le plus grand multiple de 7 inférieur à 93, il faut prendre : 56 ; 28 ce qui donne pour somme 56 + 28 = 84 ; pas 14 car 84 +14 dépasse 93 ; 7 ce qui donne pour somme 84 + 7 = 91 ; le quotient est donc 8 + 4 + 1 = 13 et le reste est 2.

L'algorithme de dichotomie suivant utilise le même principe mais économise la place mémoire car il est inutile de conserver toutes les puissances de 2 et leur produit par b.

Au lieu de parcourir comme dans la méthode naïve, tous les entiers depuis 0 en attendant de tomber sur le bon quotient, on va commencer par trouver rapidement un entier dont on sera sûr qu'il est plus grand que le quotient cherché ; dans la liste finie de quotients possibles restants, on fera une recherche dichotomique.

Le premier calcul se fait simplement en considérant la suite géométrique . Tant que , on incrémente n de 1 à chaque étape. Soit le plus petit entier tel que . Le nombre d'étapes pour trouver cet entier est de l'ordre de . Chacune de ces étapes ne demande qu'une multiplication par deux (encore plus facile qu'une addition, pour une écriture binaire), et une comparaison.