Division euclidienne

Infos
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 aux entiers naturels non nuls, elle se généralise aux entiers relatifs et aux polynômes, par exemple. Cette division est à la base de l'arithmétique modulaire et donne lieu à la création des con
Division euclidienne

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 aux entiers naturels non nuls, elle se généralise aux entiers relatifs et aux polynômes, par exemple. Cette division est à la base de l'arithmétique modulaire et donne lieu à la création des congruences sur les entiers.

Définitions

Division euclidienne dans les entiers positifs

\forall (a, b)\in\mathbb\times\mathbb^
-, \exists ! (q, r)\in\mathbb\times\mathbb, a=b.q+r \quad et \quad r < b À deux entiers a et b, avec b non nul, la division euclidienne associe un unique quotient q et un unique reste r, tout deux entiers, vérifiant :
- a = b.q+r\,
- r < b\; L'affirmation de l'existence et de l'unicité du reste et du quotient est appelée Théorème de la division euclidienne pour les entiers positifs. boîte déroulante|align=left|titre=Démonstration|contenu= Soient a et b deux entiers positifs, avec b non nul. :Existence Considérons l'ensemble E défini par : :E = \left\ x \in \mathbb\quad | \quad \exist z \in \mathbb\, x = a - bz\right\ 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 donc est strictement négatif, ce qui montre que r est strictement plus petit que b. L'existence est alors démontrée. :Unicité Supposons qu'il existe quatre entiers q1, q2, r1 et r2 formant deux couples de solutions. Par différence, (q1 - q2).b + (r1 - r2) est nul. Cette égalité montre que b divise r1 - r2 . Commer1 et r2 sont strictement plus petit que b et positifs, r1 - r2 est strictement compris entre - b et b. La seule valeur multiple de b possible pour r1 - r2 est donc zéro. En conclusion r1 est égal à r2 donc q1 est aussi égal à q2.

Division euclidienne dans les entiers relatifs

\forall (a, b)\in\mathbb\times\mathbb^
-, \exists q, r\in\mathbb / 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 tel 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

La division euclidienne selon les puissances décroissantes existe si l'anneau est défini sur un corps : \forall (A, B)\in\mathbb\times\mathbb^
-, \quad \exists !Q, R\in\mathbb, A=B.Q+R \quad avec \quad \operatorname(R) < \operatorname(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(R) < \operatorname(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.

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 ou v(r) < v(b) v étant une application de A - dans \mathbb N appelée stathme euclidien. Cette application 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). Ces anneaux sont appelés anneaux euclidiens.

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 (a_i) définie par une relation de récurrence de pas 1 : a_0=a, puis a_=a_i-b=a-(i+1)\times b. Il existe donc un plus petit entier I tel que a_Ia \, . Le nombre d'étapes pour trouver cet entier est de l'ordre de log_2\left (\frac\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 (\alpha_n) et (\beta_n) ; l'une stockera des minorants du quotient cherché, l'autre des majorants stricts. On pose donc \alpha_0=2^ et \beta_0=2^N, puis par récurrence : : si \frac\alpha_n+\beta_n\times b\le a, alors on peut affiner le minorant, et on pose donc \alpha_=\frac\alpha_n+\beta_n et \beta_=\beta_n\, : en revanche, si \frac\alpha_n+\beta_n\times b > a, on peut affiner le majorant, et on pose \beta_=\frac\alpha_n+\beta_n, et \alpha_=\alpha_n\, . On montre facilement par récurrence qu'à chaque étape n de ce deuxième calcul, \alpha_n et \beta_n sont deux entiers, tous deux multiples de 2^ et dont la différence vaut 2^ ; cette remarque permet notamment de montrer que les suites sont bien définies jusqu'à n=N-1, et que \alpha_ et \beta_ ne diffèrent que de 1 ; puisqu'ils sont respectivement un minorant large et un majorant strict du quotient, \alpha_est le quotient cherché. Le nombre maximal d'étapes pour ce calcul est de l'ordre de log_2\left (\frac\right ) (une des dichotomies a pu donner le bon quotient avant la N - 1 é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, 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^\geq a ; d'après le théorème de division euclidienne, il existe alors un unique entier 0\leq q_1
Sujets connexes
Algorithmique   Anneau euclidien   Arithmétique modulaire   Base (arithmétique)   Complexité algorithmique   Congruence sur les entiers   Divisibilité   Entier naturel   Entier relatif   Monôme   Polynôme   Poser une division  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^