Division Euclidienne


Division Euclidienne

Division euclidienne

En mathématiques, et plus précisément en arithmétique, la division euclidienne ou division entière est une opération qui, à deux entiers naturels appelés dividende et diviseur, associe deux entiers appelés quotient et reste. Initialement définie pour deux entiers naturels non nuls, elle se généralise aux entiers relatifs et 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.

Sommaire

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 a-1 au sens large. L'entier q est appelé quotient de la division de a par b, et l'entier r reste de cette division.


Division euclidienne dans les entiers relatifs

\forall (a,b)\in\mathbb{Z}\times\mathbb{Z}^*, \exists q, r\in\mathbb{Z} / a=b.q+r \quad et \quad |r| < |b|

À 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 :

  • a = b.q+r\,
  • |r| < |b|\;

L'affirmation de l'existence du reste et du quotient est appelée Théorème de la division euclidienne pour les entiers.

S'il était possible 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.


Division euclidienne dans l'ensemble des polynômes

Article détaillé : Division d'un polynôme.

La division euclidienne selon les puissances décroissantes existe si l'anneau est défini sur un corps : \forall (A,B)\in\mathbb{K}[X]\times\mathbb{K}[X]^*,\quad \exists !Q, R\in\mathbb{K}[X], A=B.Q+R \quad avec \quad \operatorname{deg}(R) < \operatorname{deg}(B)

À deux polynômes A et B à coefficients 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 :

  • A=B.Q+R\,
  • \operatorname{deg}(R) < \operatorname{deg}(B)

L'unicité est ici garantie, en revanche il est nécessaire que K soit un corps. 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 le coefficient du monôme dominant de B est inversible.

Division euclidienne dans un anneau

Article détaillé : Anneau euclidien.

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 \mathbb N appelé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) \scriptstyle {\leq} v(a). Un anneau admettant un stathme euclidien est appelé anneau euclidien. 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 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 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

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 a_{i+1}=a_i-b=a-(i+1)\times b. Il existe donc un plus petit entier I tel que aI < b : c'est-à-dire a-I\times b<b\leq a-(I-1)\times b, ce qui s'écrit encore 0\leq a-I\times b<b. Le quotient de la division cherchée est donc I, et le reste a-I\times b.

Le nombre de pas de cet algorithme est donc I=\frac{a}{b} ; 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 précédemment 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 2n. Tant que 2^n\times b \le a, on incrémente n de 1 à chaque étape. Soit N le plus petit entier tel que 2^N\times b >a \,. Le nombre d'étapes pour trouver cet entier est de l'ordre de log_2\left (\frac{a}{b}\right ) . 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 donc α0 = 2N − 1 et β0 = 2N, puis par récurrence :

si \frac{\alpha_n+\beta_n}{2}\times b\le a, alors on peut affiner le minorant, et on pose donc \alpha_{n+1}=\frac{\alpha_n+\beta_n}{2} et \beta_{n+1}=\beta_n\,
en revanche, si \frac{\alpha_n+\beta_n}{2}\times b > a, on peut affiner le majorant, et on pose \beta_{n+1}=\frac{\alpha_n+\beta_n}{2}, et \alpha_{n+1}=\alpha_n\,.

On montre facilement 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 notamment de montrer que les suites sont bien définies jusqu'à n = N − 1, et que αN − 1 et βN − 1 ne diffèrent que de 1 ; puisqu'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 log_2\left (\frac{a}{b}\right ) (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 évidemment 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 \frac{a}{b}, et donc linéairement avec la taille de a . L'amélioration est donc très nette.

Méthode courante, décimale

Soit deux entiers naturels a et b\neq 0 dont on veut effectuer la division. On commence par trouver la plus petite puissance de 10 telle que b\times 10^{N_1+1}\geq a ; d'après le théorème de division euclidienne, il existe alors un unique entier 0\leq q_1<10 tel que : q_1\times 10^{N_1}\times b\leq a< (q_1+1)\times 10^{N_1}\times b. On se ramène donc à faire la division de a-q_1\times 10^{N_1}\times b par b ; l'inégalité précédente montre que la première puissance de 10 telle que 10^{N_2}\times b excèdera a-q_1\times 10^{N_1}\times b sera strictement plus petite que 10^{N_1+1} ; on la note 10^{N_2+1}. On construit ainsi une suite d'entiers naturels (Ni) strictement décroissante ; elle vaut donc 0 à un certain rang ; on construit la suite d'entiers 0\leq q_i< 10 associée de la même façonqu'on a construit q1. Le quotient cherché sera \sum_i q_i10^{N_i} : en effet l'inégalité qui donne qr pour la première occurrence de Nr = 0 sera : 0\leq a-b\times\sum_i q_i10^{N_i}<10^{N_r}\times b=b, 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 : d'abord 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 tous les coefficients 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 seulement parmi les entiers de 0 à 9 ; il se fait donc 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

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Division euclidienne ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Division Euclidienne de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Division euclidienne — é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 opération qui, à deux entiers naturels appelés dividende… …   Wikipédia en Français

  • Division entière — Division euclidienne En mathématiques, et plus précisément en arithmétique, la division euclidienne ou division entière est une opération qui, à deux entiers naturels appelés dividende et diviseur, associe deux entiers appelés quotient et reste.… …   Wikipédia en Français

  • division — [ divizjɔ̃ ] n. f. • 1120; lat. divisio, onis 1 ♦ Action de diviser; état de ce qui est divisé (rare en emploi concret).⇒ dis ; tomie. Division d un corps en plusieurs parties. ⇒ bipartition, coupure, déchirement, fission, fractionnement,… …   Encyclopédie Universelle

  • Division (mathématiques) — Division Pour les articles homonymes, voir division (homonymie). La division est une loi de composition qui à deux nombres associe le produit du premier par l inverse du second. Si un nombre est non nul, la fonction division par ce nombre est la… …   Wikipédia en Français

  • Division d'un polynôme — En algèbre, l anneau K[X] des polynôme à une indéterminée X et à coefficients dans un corps commutatif K, comme celui des nombres rationnels, réels ou complexes, dispose d une division euclidienne, qui ressemble formellement à celle des nombres… …   Wikipédia en Français

  • Division longue — Poser une division En arithmétique, la division longue ou la méthode de la potence sont des algorithmes de division euclidienne d un nombre entier a (appelé le dividende) par un nombre entier b (appelé le diviseur) pour obtenir le quotient et le… …   Wikipédia en Français

  • Division polynomiale — Poser une division En arithmétique, la division longue ou la méthode de la potence sont des algorithmes de division euclidienne d un nombre entier a (appelé le dividende) par un nombre entier b (appelé le diviseur) pour obtenir le quotient et le… …   Wikipédia en Français

  • Division synthétique — Méthode de Ruffini Horner Connue sous le nom de méthode de Horner, règle de Ruffini ou algorithme de Ruffini Horner, cette méthode se décline sur plusieurs niveaux. Elle permet de calculer la valeur d un polynôme en . Elle présente un algorithme… …   Wikipédia en Français

  • Division — Pour les articles homonymes, voir division (homonymie). La division est une loi de composition qui à deux nombres associe le produit du premier par l inverse du second. Si un nombre est non nul, la fonction « division par ce nombre »… …   Wikipédia en Français

  • Division Harmonique — (A, B, C, D) est une division harmonique : En géométrie affine quatre points alignés sont en division harmonique quand ils vérifient l égalité des rappo …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.