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 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.

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.

On peut aussi définir une division euclidienne sur d'autres ensembles comme l'ensemble des polynômes ou dans certains anneaux.

Sommaire

1 En arithmétique
2 Division euclidienne dans d'autres ensembles
- 2.1 Division euclidienne dans l'ensemble des polynômes
- 2.2 Division euclidienne dans un anneau
3 Algorithmes de calcul
4 Notes et références
5 Voir aussi
- 5.1 À lire avant
- 5.2 À lire après

En arithmétique

Première approche

Comment distribuer 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

Distribution équitable :Comment distribuer équitablement 30 billes entre 7 personnes ?

On prend 7 billes que l'on donne à chaque personne. il reste alors 23 billes

On continue en prenant 7 autres billes que l'on distribue à chacune des 7 personnes. Celles-ci possèdent alors chacune 2 billes et il en reste 16 dans le sac

...

À la dernière étape, chaque personne possède 4 billes et il en reste 2 dans le sac

Nombre de parts de taille donnée : Combien de règles de longueur 7 peut-on placer dans une règle de longueur 30 ?

Selon le même raisonnement, on conclut que l'on peut placer 4 règles et qu'il reste 2 cases.

On dit que la division de 30 par 7 a pour quotient 4 et pour reste 2 et l'on écrit

$30 = 7 \times 4 + 2\,$

On aurait pu, à chaque étape, écrire

$30=7\times 1 + 23,\qquad 30=7\times 2 +16,\qquad 30=7\times 3 + 9$

qui sont des égalités justes mais ne correspondent pas à une division euclidienne car la distribution n'est pas complète. La distribution ne sera complète que lorsque le nombre de billes restantes sera inférieur à 7

Ainsi, effectuer la division euclidienne de 30 par 7 c'est écrire que $30 = 7 \times 4 + 2\,$ après avoir vérifié que 2 < 7

Dans une règle de longueur 30, on peut placer 4 règles de longueur 7 et il reste deux cases.

Le principe même de cette division interdit que l'on puisse diviser un nombre par 0.

La division euclidienne est, avec l'addition, la soustraction, et la multiplication une des quatre opérations élémentaires sur les nombres entiers.

Le nom de division euclidienne est un hommage rendu à Euclide qui en explique le principe par soustractions successives dans ses Éléments. Mais elle apparait 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^[1]La présence d'un reste les conduit d'ailleurs à travailler sur le concept de fraction. Une démarche analogue existe dans les mathématiques babyloniennes. On retrouve cette opération 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^[2].

Division euclidienne dans les entiers positifs

À deux entiers naturels a et b, avec b non nul, la division euclidienne associe un quotient q et un reste r, tous deux entiers naturels, vérifiant :

$a = b.q+r\,$
$r < b\;$

Le couple (q, r) est unique.

Plus formellement :

$\forall (a,b)\in\mathbb{N}\times\mathbb{N}^*, \exists! (q, r) \in\mathbb{N}^2 / a=b.q+r \quad \text{et} \quad r< b$

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

Démonstration

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{N}\quad | \quad \exist z \in \mathbb{N}\, 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 q₁,q₂, r₁ et r₂ formant deux couples de solutions. Par différence, (q₁ - q₂).b + (r₁ - r₂) est nul. Cette égalité montre que b divise r₁ - r₂ . Comme r₁ et r₂ sont strictement plus petits que b et positifs, r₁ - r₂ est strictement compris entre - b et b. La seule valeur multiple de b possible pour r₁ - r₂ est donc zéro. En conclusion r₁ est égal à r₂ donc q₁ est aussi égal à q₂.

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, tous deux entiers, vérifiant :

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

Plus formellement :

$\forall (a,b)\in\mathbb{Z}\times\mathbb{Z}^*, \exists q, r\in\mathbb{Z} / a=b.q+r \quad et \quad |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.

L'unicité du quotient et du reste ne peut être établie qu'en imposant une condition supplémentaire . Assez traditionnellement, elle consiste à supposer le reste positif, le quotient étant, lorsque b est positif, le plus grand entier relatif q tel que bq soit inférieur ou égal à a. Il est aussi possible de définir le quotient comme le quotient de la division euclidienne de |a| par |b| affectée du signe adéquat. Cependant, toute condition de ce type rend alors la définition incompatible avec la définition générale de la division dans les anneaux euclidiens.

Démonstration

La définition de la division euclidienne sur les entiers naturels permet de prouver l'existence de deux entiers naturels q₁ et r₁ tels que

| a | = | b | q 1 + r 1

avec

r 1 < | b |

Une petite étude sur les signes respectifs de a et b permet de proubver l'existence d'au moins un quotient et un reste pour la division euclidienne de a par b

pour a et b négatifs, quotient q₁ et reste - r₁

pour a négatif et b positf, quotient - q₁ et reste - r₁

pour a positif et b négatif, quotient - q₁ et reste r₁

Pour a et b positifs, quotient q₁ et reste r₁

Mais l'unicité n'est pas toujours acquise si l'on n'impose pas r positif ou nul. En effet si a = bq + r avec r strictement positif alors a = b(q+1) + r - b dans lequel

| r - b | < | b |

fournit un autre couple solution.

Utilisations

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 nombre 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 a'b' 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 Z/nZ.

Division euclidienne dans d'autres ensembles

Division euclidienne dans l'ensemble des polynômes

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

Si les polynômes ont pour coefficients des éléments d'un corps 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 unique quotient Q et un unique reste R, tout deux polynômes, vérifiant :

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

Plus formellement

$\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)$

L'unicité est ici garantie, 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 le coefficient du monôme dominant de B est inversible.

Division euclidienne dans un anneau

Article détaillé : 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 $\mathbb N$ appelée stathme euclidien et vérifiant, pour tout élément a et b non nuls

si b divise a alors

$\nu(b)\le \nu(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 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

C'est la méthode décrite par Euclide. 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 i)$ de raison (-b) :

a 0 = a

$a_{i+1}=a_i-b=a-(i+1)\times b$ .

Il existe donc un plus petit entier I tel que $a I < b$ : c'est-à-dire vérifiant

$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$ c'est-à-dire la partie entière de $\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 binaire

Ce principe est à l'origine de la technique de la division dans l'Égypte antique^[3]. 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 correspondante de la première colonne on obtient le quotient de la division.

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

1	7
2	14
4	28
8	56

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 dichotomique suivant utilise le même principe mais économise la place mémoire car il est inutile de conserver tous 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 $2 n$ . 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 = 2 N - 1$ et $β 0 = 2 N$ , 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 $2 N - 1 - n$ et dont la différence vaut $2 N - 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 - 1$ est 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 décimale

C'est la méthode utilisée dans les civilisation ayant adopté le système décimal. Elle est à l'origine de la technique enseignée dans les écoles primaire pour poser une division. Elle est présente en Chine très tôt^[4]. Elle consiste à effectuer la division en commençant par les poids forts

La méthode chinoise présente l'algorithme dans un tableau à trois lignes

dans la première ligne se constituera progressivement le quotient
dans la seconde ligne sera écrit le dividende qui évolue au cours du calcul
la troisième ligne est consacrée à placer le diviseur.

On commence par placer le diviseur le plus à gauche possible et on effectue la division en ne s'occupant pas de ce qui est à droite, le quotient se place dans la première ligne, le reste de cette première division vient remplacer les chiffres correspondants du dividende et on recommence l'opération

Ainsi pour diviser 3564 par 17 on remplit le tableau de la manière suivante:

				Quotient
3	5	6	4	Dividende
1	7			Diviseur

et on effectue la division de 35 par 17, quotient 2 reste 1

2			Quotient
1	6	4	Dividende
			Diviseur

On déplace le diviseur sur la droite jusqu'à ce qu'une nouvelle division soit possible.

2			Quotient
1	6	4	Dividende
	1	7	Diviseur

On effectue la division de 164 par 17, quotient 9 reste 11.

2		9	Quotient
	1	1	Dividende
			Diviseur

La mise à place générale de cet algorithme se développe de la manière suivante: soit deux entiers naturels a et b non nul. On cherche à effectuer la division de a par b .

On commence par trouver la plus petite puissance de 10 telle que $b.10^{N_1+1}> 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 pose alors $a_1 =a-q_1\times 10^{N_1}\times b$ .et on effectuer la division de $a 1$ 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 1$ sera strictement plus petite que $10^{N_1+1}$ ; on la note $10^{N_2+1}$ .

On construit ainsi une suite d'entiers naturels $(N i)$ 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çon qu'on a construit $q 1$ . Le quotient cherché sera $\sum_i q_i10^{N_i}$ : en effet l'inégalité qui donne $q r$ pour la première occurrence de $N r = 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 $q i$ associés au différentes puissances de 10 inférieures à la puissance assez grande obtenue. Pour chaque calcul de $q i$ , 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.

Notes et références

↑ Maurice Caveing, Essai sur le savoir mathématique dans la Mésopotamie et l'Égypte anciennes, p 263
↑ Karine Chemla, Guo Shuchun, Neuf Chapitres. Le Classique de la Chine ancienne et ses commentaires. Édition critique. [détail des éditions], pp 16-20
↑ Maurice Caveing, Essai sur le savoir mathématique dans la Mésopotamie et l'Égypte anciennes, pp 258-263
↑ Karine Chemla suppose qu'elle est antérieure à l'écriture des Neuf chapitre soit 2 siècles avant Jésus-Christ, Karine Chemla, Guo Shuchun, Neuf Chapitres. Le Classique de la Chine ancienne et ses commentaires. Édition critique. [détail des éditions], p 16

Voir aussi

Regardez d'autres dictionnaires:

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… … 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

Dictionnaires et Encyclopédies sur 'Academic'

Division euclidienne

Sommaire

En arithmétique

Première approche

Division euclidienne dans les entiers positifs

Division euclidienne dans les entiers relatifs

Utilisations

Division euclidienne dans d'autres ensembles

Division euclidienne dans l'ensemble des polynômes

Division euclidienne dans un anneau

Algorithmes de calcul

Méthode naïve

Méthode binaire

Méthode décimale

Notes et références

Voir aussi

À lire avant

À lire après

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Division euclidienne

Sommaire

En arithmétique

Première approche

Division euclidienne dans les entiers positifs

Division euclidienne dans les entiers relatifs

Utilisations

Division euclidienne dans d'autres ensembles

Division euclidienne dans l'ensemble des polynômes

Division euclidienne dans un anneau

Algorithmes de calcul

Méthode naïve

Méthode binaire

Méthode décimale

Notes et références

Voir aussi

À lire avant

À lire après

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link