Division euclidienne
En mathématiques, et plus exactement en arithmétique, la division euclidienne ou division entière est une opération qui, à deux entiers naturels nommés dividende et diviseur, associe deux entiers nommés quotient et reste.

Catégories :
Divisibilité et factorisation - Arithmétique élémentaire - Mathématiques élémentaires - Opération - Anneau - Arithmétique modulaire
Page(s) en rapport avec ce sujet :
- Soit a et b deux entiers naturels, tel que b soit non nul. Le quotient de la division euclidienne d'a par b est l'unique entier naturel q tel que b q... (source : euler.ac-versailles)
En mathématiques, et plus exactement en arithmétique, la division euclidienne ou division entière est une opération qui, à deux entiers naturels nommés dividende et diviseur, associe deux entiers nommés quotient et reste. Originellement définie pour deux entiers naturels non nuls, elle se généralise aux entiers relatifs ainsi qu'aux polynômes, par exemple.
Cette division est à la base des théorèmes de l'arithmétique élémentaire, comme celle de l'arithmétique modulaire qui donne lieu à la création des congruences sur les entiers.
Définitions
Division euclidienne dans les entiers positifs
Le théorème de division euclidienne pour des entiers positifs s'énonce ainsi : pour tous entiers a et b positifs, avec b non nul, il existe un unique couple d'entiers q et r tel que la relation a=bq+r soit vérifiée, et tel que r soit compris entre 0 et b-1 au sens large. L'entier q est nommé quotient de la division de a par b, et l'entier r reste de cette division.
Soient a et b deux entiers positifs, avec b non nul.
- Existence
Considérons la totalité E défini par :
E est non vide car il contient a. Comme E est une partie non vide de N, par axiome, le minimum de E existe. Notons r ce minimum et q l'entier qui le définit, c'est-à-dire celui vérifiant l'égalité a - b. q = r, Par construction r est un entier naturel. L'entier r - b ne peut être élément de E et par conséquent est strictement négatif, ce qui montre que r est strictement plus petit que b. L'existence est alors démontrée.
- Unicité
Division euclidienne dans les entiers relatifs
À deux entiers a et b, avec b non nul, la division euclidienne associe un quotient q et un reste r, tout deux entiers, vérifiant :
L'affirmation de l'existence du reste et du quotient est nommée Théorème de la division euclidienne pour les entiers.
S'il était envisageable de définir une division telle que l'unicité du quotient et du reste soit garantie, elle serait néanmoins incompatible avec le cas général de la division dans les anneaux euclidiens.
La définition de la division euclidienne sur les entiers naturels sert à prouver l'existence de deux entiers naturels q1 et r1 tels que
- | a | = | b | q1 + r1 avec r1 < | b |
Une petite étude sur les signes respectifs de a et b sert à donner pour la division euclidienne d'a par b
- pour a et b négatifs, quotient q1 et reste - r1
- pour a négatif et b positf, quotient - q1 et reste - r1
- pour a positif et b négatif, quotient - q1 et reste r1
- Pour a et b positifs, quotient q1 et reste r1
Division euclidienne dans la totalité des polynômes
La division euclidienne selon les puissances décroissantes existe si l'anneau est défini sur un corps :
À deux polynômes A et B à cœfficients dans un corps K avec B non nul, la division euclidienne associe un unique quotient Q et un unique reste R, tout deux polynômes, vérifiant :
L'unicité est ici garantie, par contre il est indispensable que K soit un corps. Sinon la division est toujours quelquefois envisageable, si par exemple le cœfficient du monôme dominant de B est égal à 1, ou d'une façon plus générale si le cœfficient du monôme dominant de B est inversible.
Division euclidienne dans un anneau
Dans certains types d'anneaux commutatifs unitaires intègres, on peut définir une division euclidienne par
- a = bq + r avec r = 0 où v (r) < v(b) v étant une application de A - { 0 } dans
nommée stathme euclidien.
S'il existe un stathme euclidien sur l'anneau A, il en existe un qui vérifie la propriété suivante : si a et b sont deux éléments de A tel que b divise a, alors v (b) v (a). Un anneau admettant un stathme euclidien est nommé anneau euclidien. La définition d'un stathme euclidien change d'un auteur à l'autre. Les rapports logiques entre les différentes définitions sont abordés dans l'article Anneau euclidien.
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 énormément trop de calculs pour des grands nombres. On présente ensuite deux méthodes courantes, de complexité identique : la première convient pour des calculs en base 2, et par conséquent pour une programmation informatique ; la seconde méthode, principalement équivalente, est une adaptation pour la base de numération habituelle, la base décimale, et convient par conséquent pour des calculs à la main. C'est l'algorithme enseigné à l'école.
Méthode naïve
Pour effectuer la division euclidienne de a par b, on construit une suite strictement décroissante (ai) définie par une relation de récurrence de pas 1 : a0 = a, puis . Il existe par conséquent un plus petit entier I tel que aI < b : c'est-à-dire
, ce qui s'écrit toujours
. Le quotient de la division cherchée est par conséquent I, et le reste
.
Le nombre de pas de cet algorithme est par conséquent ; chaque étape requiert une soustraction et une comparaison ; la complexité de calcul croît linéairement avec a, c'est-à-dire exponentiellement avec la taille de a - si 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 courante, binaire
Une simple amélioration consiste à faire une recherche dichotomique, sur le quotient : au lieu de parcourir comme auparavant l'ensemble des 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 envisageables restants, on fera une recherche dichotomique.
Le premier calcul se fait simplement en considérant la suite géométrique 2n. Tant que , on incrémente n de 1 à chaque étape. Soit N le plus petit entier tel que
. Chacune de ces étapes ne demande qu'une multiplication par deux (encore plus facile qu'une addition, pour une écriture binaire), et une comparaison.
Pour le deuxième calcul, on construit deux suites (αn) et (βn) ; l'une stockera des minorants du quotient cherché, l'autre des majorants stricts. On pose par conséquent α0 = 2N − 1 et β0 = 2N, puis par récurrence :
- si
, alors on peut affiner le minorant, et on pose par conséquent
et
- en revanche, si
, et
.
On montre aisément par récurrence qu'à chaque étape n de ce deuxième calcul, αn et βn sont deux entiers, tous deux multiples de 2N − 1 − n et dont la différence vaut 2N − 1 − n ; cette remarque permet surtout de montrer que les suites sont bien définies jusqu'à n = N − 1, et que αN − 1 et βN − 1 ne changent que de 1 ; dans la mesure où ils sont respectivement un minorant large et un majorant strict du quotient, αN − 1est le quotient cherché.
Le nombre maximal d'étapes pour ce calcul est de l'ordre de (une des dichotomies a pu donner le bon quotient avant la N - 1ème étape, c'est le cas d'égalité de la comparaison, auquel cas on peut arrêter l'algorithme avant), qui chacune n'exige qu'une addition, une division par deux (facile en écriture binaire, ce n'est bien entendu pas une division euclidienne cachée), une multiplication (qui peut être évitée, en gérant plus de variables), et une comparaison.
En concaténant les résultats des deux calculs, on voit que cet algorithme a une complexité qui croît logarithmiquement avec , et par conséquent linéairement avec la taille de a. Le perfectionnement est par conséquent particulièrement nette.
Méthode courante, décimale
Soit deux entiers naturels a et dont on veut effectuer la division. On débute par trouver la plus petite puissance de 10 telle que
; selon le théorème de division euclidienne, il existe alors un unique entier
tel que :
. On se ramène par conséquent à faire la division de
par b ; l'inégalité précédente montre que la première puissance de 10 telle que
excèdera
sera strictement plus petite que
; on la note
. On construit ainsi une suite d'entiers naturels (Ni) strictement décroissante ; elle vaut par conséquent 0 à un certain rang ; on construit la suite d'entiers
associée de la même façonqu'on a construit q1. Le quotient cherché sera
: en effet l'inégalité qui donne qr pour la première occurrence de Nr = 0 sera :
, ce qui est bien la définition du quotient.
On remarque que cette méthode se divise comme la précédente en deux étapes : en premier lieu une recherche d'une puissance assez grande, ce qui demande à nouveau un nombre de calcul logarithmique en a, c'est-à-dire linéaire en la taille de a ; ensuite un calcul de l'ensemble des cœfficients qi associés au différentes puissances de 10 inférieures à la puissance assez grande obtenue. Pour chaque calcul de qi, l'algorithme demande en fait un calcul de division euclidienne intermédiaire ; mais le quotient est à chercher uniquement parmi les entiers de 0 à 9 ; il se fait par conséquent rapidement en utilisant des tables.
Cette méthode est celle utilisée en primaire lorqu'il s'agit de poser une division.
Dans d'autres anneaux
Voir aussi
À lire avant
À lire après
Recherche sur Amazon (livres) : |
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.