Division euclidienne - Euclidean division

17 est divisé en 3 groupes de 5, avec 2 comme restes. Ici, le dividende est 17, le diviseur est 5, le quotient est 3, et le reste est 2 (qui est strictement plus petit que le diviseur 5), ou plus symboliquement, 17 = (5 × 3) + 2.

En arithmétique , la division euclidienne - ou division avec reste - est le processus de division d' un entier (le dividende) par un autre (le diviseur), d'une manière qui produit un quotient et un reste plus petit que le diviseur. Une propriété fondamentale est que le quotient et le reste existent et sont uniques, sous certaines conditions. En raison de cette unicité, la division euclidienne est souvent considérée sans se référer à aucune méthode de calcul, et sans calculer explicitement le quotient et le reste. Les méthodes de calcul sont appelées algorithmes de division entière , dont la plus connue est la division longue .

La division euclidienne, et les algorithmes pour la calculer, sont fondamentales pour de nombreuses questions concernant les entiers, comme l' algorithme euclidien pour trouver le plus grand diviseur commun de deux entiers, et l'arithmétique modulaire , pour laquelle seuls les restes sont considérés. L'opération consistant à ne calculer que le reste s'appelle l' opération modulo , et est souvent utilisée à la fois en mathématiques et en informatique.

La tarte a 9 tranches, donc chacune des 4 personnes reçoit 2 tranches et 1 reste.

Théorème de division

La division euclidienne est basée sur le résultat suivant, qui est parfois appelé lemme de division d'Euclide .

Étant donnés deux entiers a et b , avec b ≠ 0 , il existe des entiers uniques q et r tels que

a = bq + r

et

0 r < | b | ,

où | b | désigne la valeur absolue de b .

Dans le théorème ci-dessus, chacun des quatre nombres entiers a son propre nom : a est appelé le dividende , b est appelé le diviseur , q est appelé le quotient et r est appelé le reste .

Le calcul du quotient et du reste du dividende et du diviseur est appelé division ou — en cas d'ambiguïté — division euclidienne . Le théorème est souvent appelé algorithme de division (bien qu'il s'agisse d'un théorème et non d'un algorithme), car sa preuve, telle qu'elle est donnée ci-dessous, se prête à un algorithme de division simple pour calculer q et r (voir la section Preuve pour en savoir plus).

La division n'est pas définie dans le cas où b = 0 ; voir division par zéro .

Pour le reste et l' opération modulo , il existe d'autres conventions que 0 r < | b | , voir § Autres intervalles pour le reste .

Histoire

Bien que la « division euclidienne » porte le nom d' Euclide , il semble qu'il ne connaissait pas le théorème d'existence et d'unicité, et que la seule méthode de calcul qu'il connaissait était la division par soustraction répétée .

Avant la découverte du système de numération hindou-arabe , introduit en Europe au XIIIe siècle par Fibonacci , la division était extrêmement difficile et seuls les meilleurs mathématiciens étaient capables de le faire. Actuellement, la plupart des algorithmes de division , y compris la division longue , sont basés sur cette notation ou ses variantes, telles que les nombres binaires . Une exception notable est la division Newton-Raphson , qui est indépendante de tout système numérique .

Le terme « division euclidienne » a été introduit au cours du 20e siècle comme abréviation de « division des anneaux euclidiens ». Elle a été rapidement adoptée par les mathématiciens pour distinguer cette division des autres types de division des nombres.

Exemple intuitif

Supposons qu'une tarte a 9 tranches et qu'elles doivent être réparties également entre 4 personnes. En utilisant la division euclidienne, 9 divisé par 4 est 2 avec le reste 1. En d'autres termes, chaque personne reçoit 2 parts de tarte, et il reste 1 part.

Cela peut être confirmé en utilisant la multiplication, l'inverse de la division : si chacune des 4 personnes a reçu 2 tranches, alors 4 × 2 = 8 tranches ont été distribuées au total. En ajoutant la 1 tranche restante, le résultat est de 9 tranches. En résumé : 9 = 4 × 2 + 1.

En général, si le nombre de tranches est noté et le nombre de personnes est noté , alors on peut diviser la tarte également entre les personnes de telle sorte que chaque personne reçoive des tranches (le quotient), un certain nombre de tranches étant le reste (le reste ). Dans ce cas, l'équation tient. ${\style d'affichage a}$${\style d'affichage b}$${\style d'affichage q}$${\style d'affichage r<b}$${\style d'affichage a=bq+r}$

À titre d'exemple alternatif, si 9 tranches étaient réparties entre 3 personnes au lieu de 4, chacune en recevrait 3 et aucune tranche ne serait laissée, ce qui signifie que le reste serait égal à zéro, conduisant à la conclusion que 3 divise également 9, ou que 3 divise 9.

La division euclidienne peut également être étendue au dividende négatif (ou diviseur négatif) en utilisant la même formule; par exemple −9 = 4 × (−3) + 3, ce qui signifie que −9 divisé par 4 est −3 avec reste 3.

Exemples

• Si a = 7 et b = 3, alors q = 2 et r = 1, puisque 7 = 3 × 2 + 1.
• Si a = 7 et b = −3, alors q = −2 et r = 1, puisque 7 = −3 × (−2) + 1.
• Si a = −7 et b = 3, alors q = −3 et r = 2, puisque −7 = 3 × (−3) + 2.
• Si a = −7 et b = −3, alors q = 3 et r = 2, puisque −7 = −3 × 3 + 2.

Preuve

La preuve suivante du théorème de division repose sur le fait qu'une suite décroissante d'entiers non négatifs s'arrête finalement. Il est séparé en deux parties : une pour l'existence et une autre pour l'unicité de et . D'autres preuves utilisent le principe du bon ordre (c'est-à-dire l'affirmation que chaque ensemble non vide d' entiers non négatifs a un plus petit élément) pour rendre le raisonnement plus simple, mais ont l'inconvénient de ne pas fournir directement un algorithme pour résoudre la division ( voir § Efficacité pour plus). ${\style d'affichage q}$${\style d'affichage r}$

Existence

Considérons d'abord le cas b < 0 . En fixant b' = – b et q' = – q , l'équation a = bq + r peut être réécrite comme a = b'q' + r et l'inégalité 0 ≤ r < | b | peut être réécrit comme 0 ≤ r < |b ′ | . Ceci réduit l'existence du cas b < 0 à celle du cas b > 0 .

De même, si a < 0 et b > 0 , en définissant a' = – a , q' = – q – 1 , et r' = b – r , l'équation a = bq + r peut être réécrite comme a' = bq' + r ′ , et l'inégalité 0 ≤ r < | b | peut être réécrit comme 0 r' < | b | . Ainsi la preuve de l'existence se réduit au cas a ≥ 0 et b > 0 — qui sera considéré dans la suite de la preuve.

Soit q ₁ = 0 et r ₁ = a , alors ce sont des nombres non négatifs tels que a = bq ₁ + r ₁ . Si r ₁ < b alors la division est complète, donc supposons r ₁ ≥ b . En définissant alors q ₂ = q ₁ + 1 et r ₂ = r ₁ – b , on a a = bq ₂ + r ₂ avec 0 ≤ r ₂ < r ₁ . Comme il n'y a que r ₁ entiers non négatifs inférieurs à r ₁ , il suffit de répéter ce processus au plus r ₁ fois pour atteindre le quotient final et le reste. Autrement dit, il existe un nombre naturel k ≤ r ₁ tel que a = bq _k + r _k et 0 ≤ r _k <| b | .

Cela prouve l'existence et donne également un algorithme de division simple pour calculer le quotient et le reste. Cependant, cet algorithme n'est pas efficace, puisque son nombre de pas est de l'ordre de a / b .

Unicité

Le couple d'entiers r et q tel que a = bq + r est unique, en ce sens qu'il ne peut pas y avoir d'autre couple d'entiers qui satisfasse la même condition dans le théorème de division euclidienne. En d'autres termes, si nous avons une autre division de a par b , disons a = bq' + r' avec 0 ≤ r' < | b | , alors nous devons avoir que

q' = q et r' = r .

Pour prouver cette affirmation, nous commençons d'abord par les hypothèses que

0 r < | b |

0 r' < | b |

a = bq + r

a = bq' + r'

La soustraction des deux équations donne

b ( q - q ' ) = r ' - r .

Donc b est un diviseur de r ′ – r . Comme

| r ′ – r | < | b |

par les inégalités ci-dessus, on obtient

r ' - r = 0 ,

et

b ( q - q ' ) = 0 .

Puisque b 0 , nous obtenons que r = r ′ et q = q ′ , ce qui prouve la partie unicité du théorème de division euclidienne.

Efficacité

En général, une preuve d'existence ne fournit pas d'algorithme pour calculer le quotient et le reste existants, mais la preuve ci-dessus fournit immédiatement un algorithme (voir algorithme de division#Division par soustraction répétée ), même s'il n'est pas très efficace car il nécessite autant d'étapes que la taille du quotient. Ceci est lié au fait qu'il n'utilise que des additions, des soustractions et des comparaisons d'entiers, sans impliquer de multiplication, ni de représentation particulière des entiers telle que la notation décimale.

En termes de notation décimale, la division longue fournit un algorithme beaucoup plus efficace pour résoudre les divisions euclidiennes. Sa généralisation à la notation binaire et hexadécimale offre une flexibilité et une possibilité supplémentaires pour la mise en œuvre informatique. Cependant, pour les grandes entrées, les algorithmes qui réduisent la division à la multiplication, tels que Newton-Raphson , sont généralement préférés, car ils n'ont besoin que d'un temps qui est proportionnel au temps de la multiplication nécessaire pour vérifier le résultat - indépendamment de l'algorithme de multiplication qui est utilisé (pour en savoir plus, voir Algorithme de division#Méthodes de division rapide ).

Variantes

La division euclidienne admet un certain nombre de variantes, dont certaines sont énumérées ci-dessous.

Autres intervalles pour le reste

Dans la division euclidienne avec d comme diviseur, le reste est supposé appartenir à l' intervalle [0, d ) de longueur | d | . Tout autre intervalle de même longueur peut être utilisé. Plus précisément, étant donnés des entiers , , avec , il existe des entiers uniques et avec tels que . ${\style d'affichage m}$${\style d'affichage a}$${\style d'affichage d}$${\style d'affichage m>0}$${\style d'affichage q}$${\style d'affichage r}$${\displaystyle d\leq r<m+d}$${\style d'affichage a=mq+r}$

En particulier, si alors . Cette division est appelée division centrée , et son reste est appelé reste centré ou le moindre reste absolu .${\displaystyle d=-\left\lfloor {\frac {m}{2}}\right\rfloor }$${\displaystyle -\left\lfloor {\frac {m}{2}}\right\rfloor \leq r<m-\left\lfloor {\frac {m}{2}}\right\rfloor }$${\style d'affichage r}$

Ceci est utilisé pour l'approximation des nombres réels : la division euclidienne définit la troncature , et la division centrée définit l' arrondi .

Division de Montgomery

Compte tenu des nombres entiers , et avec et laisser le inverse multiplicatif modulaire de (c. - à être un multiple du ), alors il existe des entiers uniques et de telle sorte que . Ce résultat généralise la division impaire de Hensel (1900). ${\style d'affichage a}$${\style d'affichage m}$${\style d'affichage R,}$${\style d'affichage m>0}$${\displaystyle \gcd(R,m)=1,}$${\displaystyle R^{-1}}$${\style d'affichage R}$${\style d'affichage 0<R^{-1}<m}$${\style d'affichage R^{-1}R-1}$${\style d'affichage m}$${\style d'affichage q}$${\style d'affichage r}$${\style d'affichage 0\leq r<m}$${\displaystyle a=mq+R^{-1}\cdot r}$

La valeur est le N- résidu défini dans la réduction de Montgomery . ${\style d'affichage r}$

Dans les domaines euclidiens

Les domaines euclidiens (également connus sous le nom d' anneaux euclidiens ) sont définis comme des domaines intégraux qui soutiennent la généralisation suivante de la division euclidienne :

Etant donné un élément a et un élément b non nul dans un domaine euclidien R muni d'une fonction euclidienne d (également appelée valuation euclidienne ou fonction de degré ), il existe q et r dans R tels que a = bq + r et soit r = 0 ou d ( r ) < d ( b ) .

L'unicité de q et r n'est pas requise. Cela ne se produit que dans des cas exceptionnels, généralement pour les polynômes univariés , et pour les entiers, si la condition supplémentaire r 0 est ajoutée.

Des exemples de domaines euclidiens incluent les champs , les anneaux polynomiaux dans une variable sur un champ et les entiers gaussiens . La division euclidienne des polynômes a fait l'objet de développements spécifiques.

Voir également

• Lemme d'Euclide
• Algorithme euclidien

Remarques

Les références

• Fraleigh, John B. (1993), Un premier cours d'algèbre abstraite (5e éd.), Addison-Wesley, ISBN 978-0-201-53467-2
• Rotman, Joseph J. (2006), Un premier cours d'algèbre abstraite avec applications (3e éd.), Prentice-Hall, ISBN 978-0-13-186267-8