Euklidische Teilung - Euclidean division

17 ist in 3 Gruppen von 5 unterteilt, wobei 2 übrig bleiben. Hier beträgt der Dividenden 17, der Divisor 5, der Quotient 3 und der Rest 2 (was streng genommen kleiner als der Divisor 5 ist) oder symbolischer 17 = (5 × 3) + 2.

In der Arithmetik ist die euklidische Division – oder Division mit Rest – der Vorgang, bei dem eine ganze Zahl (den Dividenden) durch eine andere (den Divisor) so dividiert wird , dass ein Quotient und ein Rest kleiner als der Divisor erhalten werden. Eine grundlegende Eigenschaft ist, dass der Quotient und der Rest existieren und unter bestimmten Bedingungen eindeutig sind. Wegen dieser Eindeutigkeit wird die euklidische Division oft ohne Bezugnahme auf eine Berechnungsmethode und ohne explizite Berechnung des Quotienten und des Rests betrachtet. Die Berechnungsmethoden werden Ganzzahldivisionsalgorithmen genannt , von denen die bekannteste die lange Division ist .

Die euklidische Division und Algorithmen zu ihrer Berechnung sind grundlegend für viele Fragen zu ganzen Zahlen, wie den euklidischen Algorithmus zum Finden des größten gemeinsamen Teilers von zwei ganzen Zahlen und die modulare Arithmetik , bei der nur Reste berücksichtigt werden. Die Operation, bei der nur der Rest berechnet wird, wird als Modulo-Operation bezeichnet und wird sowohl in der Mathematik als auch in der Informatik häufig verwendet.

Die Torte hat 9 Scheiben, so dass jede der 4 Personen 2 Scheiben erhält und 1 übrig bleibt.

Divisionssatz

Die euklidische Division basiert auf dem folgenden Ergebnis, das manchmal als Euklids Divisionslemma bezeichnet wird .

Gegeben zwei ganze Zahlen a und b , mit b 0 , existieren eindeutige ganze Zahlen q und r mit

a = bq + r

und

0 ≤ r < | b | ,

wo | b | bezeichnet den Absolutwert von b .

Im obigen Satz hat jede der vier ganzen Zahlen einen eigenen Namen: a heißt Dividende , b heißt Divisor , q heißt Quotient und r heißt Rest .

Die Berechnung des Quotienten und des Restes aus Dividende und Divisor nennt man Division oder – bei Mehrdeutigkeit – Euklidische Division . Das Theorem wird häufig als Divisionsalgorithmus bezeichnet (obwohl es ein Theorem und kein Algorithmus ist), weil sich sein Beweis wie unten angegeben für einen einfachen Divisionsalgorithmus zur Berechnung von q und r eignet (siehe Abschnitt Beweis für mehr).

Für den Fall b = 0 ist die Division nicht definiert ; siehe Division durch Null .

Für den Rest und die Modulo-Operation gibt es andere Konventionen als 0 ≤ r < | b | , siehe § Andere Intervalle für den Rest .

Geschichte

Obwohl "Euklidische Division" nach Euklid benannt ist , scheint es, dass er das Existenz- und Eindeutigkeitstheorem nicht kannte und dass die einzige Berechnungsmethode, die er kannte, die Division durch wiederholte Subtraktion war .

Vor der Entdeckung des hindu-arabischen Zahlensystems , das im 13. Jahrhundert von Fibonacci in Europa eingeführt wurde , war die Teilung äußerst schwierig und nur die besten Mathematiker waren in der Lage, dies zu tun. Gegenwärtig basieren die meisten Divisionsalgorithmen , einschließlich der langen Division , auf dieser Notation oder ihren Varianten, wie z. B. binären Zahlen . Eine bemerkenswerte Ausnahme ist die Newton-Raphson-Division , die von jedem Zahlensystem unabhängig ist .

Der Begriff „Euklidische Teilung“ wurde im 20. Jahrhundert als Abkürzung für „Teilung der euklidischen Ringe “ eingeführt. Es wurde von Mathematikern schnell angenommen, um diese Division von den anderen Arten der Division von Zahlen zu unterscheiden.

Intuitives Beispiel

Angenommen, ein Kuchen hat 9 Scheiben und diese sollen gleichmäßig auf 4 Personen aufgeteilt werden. Bei der euklidischen Division ist 9 geteilt durch 4 2 mit Rest 1. Mit anderen Worten, jede Person erhält 2 Stück Kuchen und es bleibt 1 Stück übrig.

Dies kann durch Multiplikation bestätigt werden – die Umkehrung der Division: Wenn jede der 4 Personen 2 Scheiben erhielt, dann wurden 4 × 2 = 8 Scheiben insgesamt ausgegeben. Addiert man das verbleibende 1 Slice, ergibt das 9 Slices. Zusammengefasst: 9 = 4 × 2 + 1.

Im Allgemeinen, wenn die Anzahl der Scheiben und die Anzahl der Personen bezeichnet wird , kann man den Kuchen gleichmäßig auf die Personen aufteilen, so dass jede Person Scheiben erhält (den Quotienten), wobei eine gewisse Anzahl von Scheiben übrig bleibt (der Rest ). In diesem Fall gilt die Gleichung . ${\displaystyle a}$${\displaystyle b}$${\displaystyle q}$${\displaystyle r<b}$${\displaystyle a=bq+r}$

Wenn als alternatives Beispiel 9 Scheiben auf 3 statt auf 4 Personen aufgeteilt würden, würde jeder 3 erhalten und es würde keine Scheibe übrig bleiben, was bedeutet, dass der Rest Null wäre, was zu dem Schluss führt, dass 3 gleichmäßig 9 teilt oder dass 3 teilt 9.

Die euklidische Division kann mit derselben Formel auch auf einen negativen Dividenden (oder negativen Divisor) ausgedehnt werden; zum Beispiel −9 = 4 × (−3) + 3, was bedeutet, dass −9 dividiert durch 4 −3 mit Rest 3 ist.

Beispiele

• Wenn a = 7 und b = 3, dann q = 2 und r = 1, da 7 = 3 × 2 + 1.
• Wenn a = 7 und b = −3, dann q = −2 und r = 1, da 7 = −3 × (−2) + 1.
• Wenn a = −7 und b = 3, dann q = −3 und r = 2, da −7 = 3 × (−3) + 2.
• Wenn a = −7 und b = −3, dann q = 3 und r = 2, da −7 = −3 × 3 + 2.

Beweis

Der folgende Beweis des Divisionssatzes beruht auf der Tatsache, dass eine absteigende Folge von nichtnegativen ganzen Zahlen irgendwann aufhört. Es ist in zwei Teile unterteilt: einen für die Existenz und einen für die Einzigartigkeit von und . Andere Beweise verwenden das Wohlordnungsprinzip (dh die Behauptung, dass jede nicht-leere Menge von nicht-negativen ganzen Zahlen ein kleinstes Element hat), um die Argumentation zu vereinfachen, haben jedoch den Nachteil, dass sie keinen direkten Algorithmus zum Lösen der Division bereitstellen ( siehe § Wirksamkeit für mehr). ${\displaystyle q}$${\displaystyle r}$

Existenz

Betrachten Sie zunächst den Fall b < 0 . Bei b' = – b und q' = – q kann die Gleichung a = bq + r umgeschrieben werden als a = b'q' + r und die Ungleichung 0 ≤ r < | b | kann umgeschrieben werden als 0 ≤ r < |b ′ | . Dies reduziert die Existenz für den Fall b < 0 auf die des Falls b > 0 .

Wenn a < 0 und b > 0 , a' = – a , q' = – q – 1 und r' = b – r gesetzt wird , kann die Gleichung a = bq + r in ähnlicher Weise umgeschrieben werden als a' = bq' + r ′ , und die Ungleichung 0 ≤ r < | b | kann umgeschrieben werden als 0 ≤ r' < | b | . Damit reduziert sich der Existenzbeweis auf den Fall a ≥ 0 und b > 0 — was im weiteren Beweis betrachtet wird.

Sei q ₁ = 0 und r ₁ = a , dann sind dies nicht-negative Zahlen mit a = bq ₁ + r ₁ . Wenn r ₁ < b ist, ist die Division abgeschlossen, also sei r ₁ ≥ b . Dann definiert man q ₂ = q ₁ + 1 und r ₂ = r ₁ – b , man hat a = bq ₂ + r ₂ mit 0 ≤ r ₂ < r ₁ . Da es nur r ₁ nicht-negative ganze Zahlen kleiner als r _{1 gibt} , muss man diesen Vorgang nur höchstens r ₁ Mal wiederholen , um den endgültigen Quotienten und den Rest zu erreichen. Das heißt, es gibt eine natürliche Zahl k ≤ r ₁ , so dass ein = bq _k + r _k und 0 ≤ r _k <| b | .

Dies beweist die Existenz und liefert auch einen einfachen Divisionsalgorithmus zur Berechnung des Quotienten und des Rests. Dieser Algorithmus ist jedoch nicht effizient, da seine Schrittzahl in der Größenordnung von a / b liegt .

Einzigartigkeit

Das Paar von ganzen Zahlen r und q , so dass ein = bq + r einzigartig ist, in dem Sinne , dass es keine anderes Paar von ganzen Zahlen sein kann , dass die gleiche Bedingung erfüllt , in der Division mit Rest - Theorem. Mit anderen Worten, wenn wir eine andere Division von a durch b haben , sagen wir a = bq' + r' mit 0 ≤ r' < | b | , dann müssen wir das haben

q' = q und r' = r .

Um diese Aussage zu beweisen, beginnen wir zunächst mit den Annahmen, dass

0 ≤ r < | b |

0 ≤ r' < | b |

a = bq + r

a = bq' + r'

Subtrahieren der beiden Gleichungen ergibt

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

Also ist b ein Teiler von r ′ – r . Wie

| r ′ – r | < | b |

durch die obigen Ungleichungen erhält man

r ′ – r = 0 ,

und

b ( q - q ' ) = 0 .

Da b ≠ 0 , erhalten wir r = r ′ und q = q ′ , was den Eindeutigkeitsteil des euklidischen Divisionssatzes beweist.

Wirksamkeit

Im Allgemeinen liefert ein Existenzbeweis keinen Algorithmus zur Berechnung des vorhandenen Quotienten und Restes, aber der obige Beweis liefert sofort einen Algorithmus (siehe Divisionsalgorithmus#Division durch wiederholte Subtraktion ), obwohl er nicht sehr effizient ist, da er erfordert so viele Schritte wie die Größe des Quotienten. Dies hängt damit zusammen, dass nur Additionen, Subtraktionen und Vergleiche von ganzen Zahlen verwendet werden, ohne dass eine Multiplikation erforderlich ist, noch eine bestimmte Darstellung der ganzen Zahlen wie die Dezimalschreibweise.

In Bezug auf die dezimale Notation bietet die lange Division einen viel effizienteren Algorithmus zum Lösen von euklidischen Divisionen. Seine Verallgemeinerung auf binäre und hexadezimale Notation bietet weitere Flexibilität und Möglichkeiten für die Computerimplementierung. Für große Eingaben werden jedoch in der Regel Algorithmen bevorzugt, die Division auf Multiplikation reduzieren, wie Newton-Raphson , da sie nur eine Zeit benötigen, die proportional zur Zeit der Multiplikation ist, die benötigt wird, um das Ergebnis zu überprüfen – unabhängig vom Multiplikationsalgorithmus, der verwendet wird (weitere Informationen finden Sie unter Divisionsalgorithmus#Schnelle Divisionsmethoden ).

Varianten

Die euklidische Teilung lässt eine Reihe von Varianten zu, von denen einige unten aufgeführt sind.

Andere Intervalle für den Rest

Bei der euklidischen Division mit d als Teiler soll der Rest zum Intervall [0, d ) der Länge | . gehören d | . Jedes andere Intervall der gleichen Länge kann verwendet werden. Genauer gesagt gibt es bei gegebenen ganzen Zahlen , , mit eindeutige ganze Zahlen und mit solchen, dass . ${\displaystyle m}$${\displaystyle a}$${\displaystyle d}$${\displaystyle m>0}$${\displaystyle q}$${\displaystyle r}$${\displaystyle d\leq r<m+d}$${\displaystyle a=mq+r}$

Insbesondere wenn dann . Diese Division wird zentrierte Division genannt , und ihr Rest wird zentrierter Rest oder kleinster absoluter Rest genannt .${\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}$${\displaystyle r}$

Dies wird zur Approximation reeller Zahlen verwendet : Die euklidische Division definiert das Abschneiden und die zentrierte Division definiert das Runden .

Abteilung Montgomery

Gegeben ganze Zahlen , und mit und lassen Sie das seine modulare multiplikative Inverse von (dh mit einem Vielfachen des Sein ), dann gibt es eindeutige Zahlen und mit so dass . Dieses Ergebnis verallgemeinert die ungerade Division von Hensel (1900). ${\displaystyle a}$${\displaystyle m}$${\displaystyle R,}$${\displaystyle m>0}$${\displaystyle \gcd(R,m)=1,}$${\displaystyle R^{-1}}$${\displaystyle R}$${\displaystyle 0<R^{-1}<m}$${\displaystyle R^{-1}R-1}$${\displaystyle m}$${\displaystyle q}$${\displaystyle r}$${\displaystyle 0\leq r<m}$${\displaystyle a=mq+R^{-1}\cdot r}$

Der Wert ist der in der Montgomery-Reduktion definierte N- Rest . ${\displaystyle r}$

In euklidischen Domänen

Euklidische Domänen (auch bekannt als euklidische Ringe ) werden als integrale Domänen definiert, die die folgende Verallgemeinerung der euklidischen Teilung unterstützen:

Bei einem gegebenes Elemente a und ein von Null verschiedenen Elemente b in einem euklidischen R ausgerüstet mit einer euklidischen Funktion d (auch bekannt als einen euklidischen Bewertungs oder Gradfunktion ,) gibt es q und r in R , so dass ein = bq + r und entweder r = 0 oder d ( r ) < d ( b ) .

Eindeutigkeit von q und r ist nicht erforderlich. Sie tritt nur in Ausnahmefällen auf, typischerweise bei univariaten Polynomen und bei ganzen Zahlen, wenn die weitere Bedingung r ≥ 0 hinzugefügt wird.

Beispiele für euklidische Domänen umfassen Felder , Polynomringe in einer Variablen über einem Feld und die Gaußschen ganzen Zahlen . Die euklidische Division von Polynomen war Gegenstand spezifischer Entwicklungen.

Siehe auch

• Euklids Lemma
• Euklidischer Algorithmus

Anmerkungen

Verweise

• Fraleigh, John B. (1993), Ein erster Kurs in abstrakter Algebra (5. Aufl.), Addison-Wesley, ISBN 978-0-201-53467-2
• Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications (3. Aufl.), Prentice-Hall, ISBN 978-0-13-186267-8