Der Divisionsalgorithmus

In dieser Unterrichtseinheit entwickeln wir den Divisionsalgorithmus als das Prinzip, das für ganze Zahlen die eindeutige Zerlegung b=qa+r mit 0\le r<|a| formalisiert. Zunächst wird die Existenz von Quotient und Rest bewiesen und anschließend ihre Eindeutigkeit. Abschließend wird die Bedeutung des Restes interpretiert, die Theorie mit dem schriftlichen Divisionsalgorithmus als Rechenverfahren verknüpft und seine natürliche Verbindung zur modularen Arithmetik sowie zu rechnerischen Anwendungen aufgezeigt.

Lernziele

Nach Abschluss dieser Unterrichtseinheit ist der Studierende in der Lage:

1. Zu identifizieren die grundlegenden Begriffe und Rollen der ganzzahligen Division (Dividend, Divisor, Quotient, Rest) sowie den Begriff der Teilbarkeit als exakten Spezialfall.
2. Zu erklären die Aussage des Algorithmus/Theorems der euklidischen Division, einschließlich der Bedingungen, die den Rest festlegen (0\le r<|a|), und ihres Zwecks zur Vermeidung von Mehrdeutigkeiten.
3. Anzuwenden die euklidische Zerlegung b=qa+r, um q und r in konkreten Beispielen zu bestimmen und dabei die Schranke für den Rest zu überprüfen.
4. Zu analysieren die Behandlung von Fällen in Abhängigkeit vom Vorzeichen des Dividenden und des Divisors und zu begründen, warum die euklidische Konvention einen nichtnegativen Rest beibehält.
5. Auszuführen den schriftlichen Divisionsalgorithmus als mechanisches Verfahren auf der Grundlage der Stellenwertdarstellung zur Bestimmung von q und r.

INHALTSVERZEICHNIS:
Division und Teilbarkeit
Satz der euklidischen Division
Beweis der euklidischen Division
Interpretation von Quotient und Rest
Schriftlicher Divisionsalgorithmus
Schlussfolgerung
Vorgeschlagene und gelöste Übungen

Division und Teilbarkeit

In der Arithmetik beschreibt die Teilbarkeit den „exakten“ Fall: a\mid b bedeutet, dass b sich exakt als ein Vielfaches von a schreiben lässt. Obwohl jedoch nicht immer Teilbarkeit zwischen zwei beliebigen ganzen Zahlen besteht, können wir dennoch fragen, „wie oft eine Zahl in eine andere hineinpasst und, falls nicht exakt, was übrig bleibt“. In diesem Kontext entsteht der Divisionsalgorithmus, der garantiert, dass eine beliebige ganze Zahl b als ein Vielfaches von a plus einem „Rest“ geschrieben werden kann.

Als Beispiel betrachten wir a=3 und b=16. Es ist klar, dass 3 die 16 nicht teilt. Dennoch ist es möglich, einen Quotienten und einen Rest für die Division zu finden, denn

16 = 5\cdot 3 + 1

Folglich erhält man beim Dividieren von b=16 durch a=3 (wobei b der Dividend und a der Divisor ist), dargestellt durch 16/3 oder 16\div 3, als Quotient q=5 und als Rest r=1. Allgemein besagt der Divisionsalgorithmus, dass es für beliebige ganze Zahlen a (Divisor) und b (Dividend) mit a\neq 0 eindeutige ganze Zahlen q und r gibt, so dass

b=qa+r,\qquad 0\le r<|a|

In diesem Beispiel gilt 16=3\cdot 5+1, und die Bedingung 0\le r<|a| ist erfüllt, da 0\le 1<3. Diese Formulierung vermeidet Mehrdeutigkeiten, wenn der Divisor (oder der Dividend) negativ sein kann, und stellt sicher, dass der Rest stets nichtnegativ und strikt kleiner als der Betrag des Divisors ist.

Satz der euklidischen Division

Das Ergebnis der Anwendung des Divisionsalgorithmus ist das, was als euklidische Division bezeichnet wird, und beruht auf dem folgenden Resultat.

Satz: Seien a,b\in\mathbb{Z} mit a\neq 0. Dann existieren eindeutige q,r\in\mathbb{Z}, so dass

b=qa+r,\qquad 0\le r<|a|.

Die ganze Zahl q heißt Quotient und r heißt Rest der Division von b durch a.

Beweis der euklidischen Division

Dieser Beweis gliedert sich in zwei Teile: Zunächst wird gezeigt, dass Quotient und Rest existieren; und anschließend, dass sie, sofern sie existieren, eindeutig sind.

Existenz

Seien a,b\in\mathbb{Z} mit a\neq 0 und definieren wir d=|a|, so dass d>0 gilt. Zunächst betrachten wir den Fall b\ge 0: Wir zeigen, dass es q,r\in\mathbb{Z} gibt, so dass b=dq+r und 0\le r<d. Anschließend behandeln wir den Fall b<0. Am Ende ersetzen wir d durch |a|, um die Form b=qa+r mit 0\le r<|a| zu erhalten.

Für b\in\mathbb{Z} mit b\ge 0 formulieren wir die Aussage P(b): „Es existieren q,r\in\mathbb{Z} derart, dass b=dq+r und 0\le r<d gilt.“ Wir werden durch Induktion zeigen, dass P(b) für alle b\ge 0 gültig ist.

Induktionsanfang: Für b=0 erhält man durch Wahl von q=0 und r=0 die Gleichung 0=d\cdot 0+0 sowie 0\le 0<d. Daher ist P(0) wahr.

Induktionsschritt: Sei k\ge 0 und es gelte die Induktionsannahme, dass P(k) wahr ist. Dann existieren q,r\in\mathbb{Z} mit

k=dq+r,\qquad 0\le r<d.

Addiert man 1 auf beiden Seiten, so erhält man

k+1=dq+(r+1).

Ferner folgt aus 0\le r<d, dass r+1\le d gilt. Folglich können nur die Fälle r+1<d oder r+1=d eintreten.

Fall 1: Falls r+1<d, definieren wir q'=q und r'=r+1. Dann gilt

k+1=dq'+r',\qquad 0\le r'<d.

Fall 2: Falls r+1=d, so ist k+1=dq+d=d(q+1)+0. Wir setzen q'=q+1 und r'=0, und es gilt

k+1=dq'+r',\qquad 0\le r'<d.

In beiden Fällen haben wir ganze Zahlen q',r' konstruiert, so dass k+1=dq'+r' und 0\le r'<d gilt. Damit ist P(k+1) wahr. Wir schließen durch vollständige Induktion, dass P(b) für alle b\ge 0 gilt.

Betrachten wir nun den Fall b<0. Dann ist -b>0. Wendet man das vorherige Ergebnis auf -b an, so existieren q,r\in\mathbb{Z} mit

-b=dq+r,\qquad 0\le r<d.

Durch Multiplikation mit -1 erhält man

b=-dq-r.

Ist r=0, so genügt es, q_1=-q und r_1=0 zu wählen; dann gilt b=dq_1+r_1 und 0\le r_1<d.

Ist hingegen r>0, so definieren wir q_1=-q-1 und r_1=d-r. Da 0<r<d gilt, folgt 0<d-r<d, also 0\le r_1<d. Außerdem gilt

dq_1+r_1=d(-q-1)+(d-r)=-dq-d+d-r=-dq-r=b.

Folglich existieren für jedes b\in\mathbb{Z} ganze Zahlen q_1,r_1\in\mathbb{Z} derart, dass b=dq_1+r_1 und 0\le r_1<d gilt.

Schließlich erinnern wir daran, dass d=|a| ist. Ist a>0, so gilt d=a und die Gleichung b=dq_1+r_1 lässt sich als b=aq_1+r_1 schreiben, mit 0\le r_1<|a|.

Ist a<0, so gilt d=-a und b=dq_1+r_1=(-a)q_1+r_1=a(-q_1)+r_1. Definiert man q=-q_1 und r=r_1, so erhält man

b=qa+r,\qquad 0\le r<|a|.

Damit ist die Existenz von q und r für beliebige a,b\in\mathbb{Z} mit a\neq 0 bewiesen.

Eindeutigkeit

Es sei angenommen, dass es q,q',r,r'\in\mathbb{Z} gibt, so dass

b=qa+r=q'a+r',\qquad 0\le r,r'<|a|.

Durch Subtraktion beider Ausdrücke erhält man

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

Da 0\le r,r'<|a| gilt, folgt |r'-r|<|a|. Dagegen ist die linke Seite ein Vielfaches von a und damit auch ein Vielfaches von |a|. Das einzige ganzzahlige Vielfache von |a| mit streng kleinerem Absolutwert als |a| ist 0; denn gilt |a| m \neq 0 mit m\in\mathbb{Z}, so ist \big| |a| m \big| \ge |a| . Folglich ist r'-r=0, das heißt r=r', und durch Einsetzen in b=qa+r folgt q=q'. Damit ist die Zerlegung eindeutig.

Interpretation von Quotient und Rest

• Was „Rest“ bedeutet. Gilt b=qa+r, so ist r=b-qa das, was „übrig bleibt“, wenn man von b das Vielfache qa abzieht. Mit anderen Worten ist r der Überschuss, der entsteht, wenn b an das Gitter der Vielfachen von a angepasst wird.
• Warum 0\le r<|a| gefordert wird. Ohne diese Bedingung wäre das Paar (q,r) nicht eindeutig. In der Tat gilt: Ist b=qa+r, so auch b=a(q+1)+(r-a). Die Bedingung 0\le r<|a| zwingt den Rest, in einem festen Intervall \{0,1,2,\dots,|a|-1\} zu liegen, und verhindert damit die unendlichen „Um-Etikettierungen“ derselben Zahl.
• Was geschieht, wenn a negativ ist. Der Satz bleibt unverändert gültig: Der Rest bleibt nichtnegativ und durch |a| beschränkt. Dies ist relevant, da einige Programmiersprachen eine Trunkierung gegen null verwenden und negative Reste liefern können, während in der Mathematik die Konvention 0\le r<|a| gewählt wird, damit der Rest ein „standardmäßiger“ Repräsentant ist.

  Außerdem stimmt bei a>0 der Quotient mit der Abrundungsfunktion (Floor) überein:

  q=\left\lfloor \frac{b}{a}\right\rfloor,\qquad r=b-a\left\lfloor \frac{b}{a}\right\rfloor.

Schriftlicher Divisionsalgorithmus

Ausgehend von der euklidischen Division lässt sich der schriftliche Divisionsalgorithmus implementieren, wobei die Stellenwertdarstellung der Zahlen genutzt wird. Dieser Algorithmus ist ein Rechenverfahren, das es ermöglicht, die Werte q und r schnell zu bestimmen, wenn man b\div a mit a,b\in\mathbb{Z} und a\neq 0 berechnen möchte.

Zu seiner Beschreibung betrachten wir zunächst einige Beispiele, die den Ablauf und die möglichen Situationen während der Ausführung des Algorithmus veranschaulichen.

1. Angenommen, wir möchten 57\div 4 berechnen. Dabei ist 57 der Dividend und 4 der Divisor. Dazu führen wir die folgende Abfolge von Rechnungen aus:

   \begin{array}{rll} (1) & \color{red}57 \div 4 =\color{black} \\ & \text{Die Division hinschreiben.} \\ \\ (2) & \color{red}5'\color{black}7 \div 4 = \\ & \text{Das erste Präfix (von links) des Dividenden abtrennen, das}\\ &\text{größer oder gleich dem Divisor ist, in diesem Fall 5.} \\ \\ (3) & 5'7 \div 4 = \color{red}1\color{black} \\ & \text{An die größte Zahl denken, die mit $4$ multipliziert}\\ &\text{kleiner oder gleich $5$ ist, und sie rechts der Gleichung notieren. Es ist 1.} \\ \\ (4) & \begin{array}{ll}\phantom{-|}5'7 \div 4 &= 1 \\ \color{red}-|\underline{4}\color{black} & \\ \color{red}\phantom{-|}1\color{black} & \end{array} \\ & \text{Das Ergebnis mit dem Divisor multiplizieren und vom gewählten Wert subtrahieren.} \\ \\ (5) & \begin{array}{ll}\phantom{-|}5'\color{red}7'\color{black} \div 4 &= 1 \\ -|\underline{4} & \\ \phantom{-|}1\color{red}7\color{black} & \end{array} \\ & \text{Die nächste Ziffer auswählen und „herunterholen“.} \\ \\ (6) & \begin{array}{ll}\phantom{-|}5'7' \div 4 &= 1\color{red}4\color{black} \\ -|\underline{4} & \\ \phantom{-|}17 & \\ \color{red}-|\underline{16}\color{black} & \\ \color{red}\phantom{-|}1\color{black} \end{array} \\ & \text{Die Sequenz mit der zuletzt erhaltenen Zahl wiederholen.} \end{array}

   Der Algorithmus endet, wenn keine Ziffern mehr „herunterzuholen“ sind, und liefert als Ergebnis den Quotienten q=14 und den Rest r=1. Insbesondere ist der Rest stets kleiner als der Divisor.

2. Angenommen, wir möchten 132\div 5 berechnen. Dazu führen wir die folgende Abfolge von Rechnungen aus:

   \begin{array}{rl} (1) &1'32 \div 5 = \\ & \text{Das erste Präfix des Dividenden abtrennen und eine natürliche Zahl suchen, die,}\\ & \text{mit 5 multipliziert, kleiner oder gleich diesem ist. Falls dies nicht möglich ist,}\\ & \text{die nächste Ziffer einbeziehen, bis es möglich ist.} \\ \\ (2) &\begin{array}{ll}\phantom{-|}13'2 \div 5 &= 2 \\ -|\underline{10} & \\ \phantom{-|1}3 & \end{array}\\ & \text{Sobald der vorherige Schritt funktioniert, den Algorithmus regulär ausführen.} \\ \\ (3) &\begin{array}{ll}\phantom{-|}13'2' \div 5 &= 26 \\ -|\underline{10} & \\ \phantom{-|1}32 & \\ \phantom{\,} -|\underline{30} & \\ \phantom{-|30} 2 & \end{array} \end{array}

3. Hat der Dividend mehr Ziffern, wird das Verfahren in gleicher Weise ausgeführt. Beispielsweise erhält man bei der Berechnung von 3521\div 12:

   \begin{array}{ll} \phantom{-|}35'2'1' \div 12 & = 293 \\ -|\underline{24} & \\ \phantom{-|}112 & \\ -|\underline{108} & \\ \phantom{-|10}41 & \\ \phantom{0}-|\underline{36} & \\ \phantom{10-|}5 & \\ \end{array}

4. Ist eine der Zahlen negativ, gibt es zwei zulässige Arten, das Ergebnis darzustellen. Die Standardform in der Zahlentheorie ist jedoch jene, bei der der Rest positiv ist und somit mit der euklidischen Division übereinstimmt. Berechnen wir zum Beispiel -598\div 21, so ergeben sich die folgenden möglichen Entwicklungen, die beide als Identitäten korrekt sind:

   • Mit negativem Rest: Dieser wird erhalten, indem man das Vorzeichen zu Beginn der Rechnung entfernt und es am Ende wiederherstellt.

     \begin{array}{ll} \phantom{-}59'8' \div 21 &= 28 \\ -|\underline{42} & \\ \phantom{-|'}178 & \\ \phantom{\,}-|\underline{168} & \\ \phantom{-|00}10 & \\ \end{array}

     Daraus folgt:

     598 = 21 \times 28 + 10

     Multipliziert man anschließend die gesamte Gleichung mit -1, so erhält man:

     -598 = 21 \times (-28) - 10

     Somit ist in dieser Darstellung das Ergebnis von -598\div 21 der Quotient q=-28 und der Rest r=-10.

     Multipliziert man erneut die gesamte Gleichung mit -1, so erhält man:

     598 = (-21)\times(-28) + 10

     Damit ist das Ergebnis von 598\div (-21) der Quotient q=-28 und der Rest r=10.

   • Mit positivem Rest und konsistent mit der euklidischen Division: Ausgehend von der vorherigen Entwicklung gilt:

     -598 = 21 \times (-28) - 10

     Addiert man anschließend 0=21-21 auf der rechten Seite dieser Gleichung, so erhält man:

     -598 = 21 \times (-28) - 10 \color{red}+ 21 - 21\color{black} = 21\times(-29) + 11

     Folglich ergibt die Berechnung von -598\div 21, in Übereinstimmung mit der euklidischen Division, den Quotienten q=-29 und den Rest r=11.

   Hinsichtlich der Konventionen der euklidischen Division entspricht nur das Ergebnis mit positivem Rest dem euklidischen Quotienten und Rest. Dennoch sind beide Darstellungen korrekte Identitäten und können in unterschiedlichen Kontexten nützlich sein. Obwohl der schriftliche Divisionsalgorithmus negative Reste liefern kann, ist dies praktisch, um Ergebnisse auf mechanische Weise zu erhalten und algebraische Manipulationen ohne zusätzliche Zwischenschritte durchzuführen. Andererseits ermöglichen Ergebnisse mit positivem Rest, die mit der euklidischen Division konsistent sind, die Festlegung eines kanonischen Repräsentanten jeder Restklasse (beispielsweise in \{0,1,\dots,n-1\}), was die präzise und eindeutige Kennzeichnung der ganzen Zahlen erleichtert. Es sei darauf hingewiesen, dass es auch andere Konventionen für Repräsentanten gibt, wie etwa symmetrische Reste, die ebenfalls gültig sind, sobald die entsprechende Regel festgelegt ist.

Schlussfolgerung

Der Divisionsalgorithmus garantiert, dass jede ganzzahlige Division eindeutig in der Form b=qa+r mit 0\le r<|a| dargestellt werden kann, wodurch ein Standardkriterium zur Interpretation von Quotient und Rest festgelegt wird, selbst wenn negative Zahlen beteiligt sind. Der schriftliche Divisionsalgorithmus ist nichts anderes als eine praktische Umsetzung dieser Zerlegung, gestützt auf die Stellenwertdarstellung, und ermöglicht die mechanische Berechnung von q und r. Schließlich vermeidet diese euklidische Form nicht nur Mehrdeutigkeiten, sondern stellt auch eine natürliche Verbindung zur modularen Arithmetik her: Der Rest r fungiert als kanonischer Repräsentant der Restklasse von b modulo a, Grundlage vieler Techniken in der Zahlentheorie und in rechnerischen Anwendungen, die in zukünftigen Beiträgen behandelt werden.

Vorgeschlagene und gelöste Übungen

Euklidische Division

1. (gelöst) Bestimme q und r so, dass

   137 = 9q + r,\qquad 0\le r\lt 9.

   Lösung: Suche die größte Zahl, die, mit 9 multipliziert, 137 nicht überschreitet. Es gilt 15\times 9 = 135 und 16\times 9 = 144; daher ist der gesuchte Quotient q=15. Berechne nun den Rest r=137-9q und überprüfe, dass 0\le r\lt 9 gilt. Bei der Überprüfung erhält man:

   r=137-9\cdot 15=137-135=2.

   Somit gilt 137=9\cdot 15+2 mit 0\le 2\lt 9.

2. (gelöst) Bestimme q und r so, dass

   2025 = 37q + r,\qquad 0\le r\lt 37.

   Lösung: Suche die größte Zahl, die, mit 37 multipliziert, 2025 nicht überschreitet. Man beobachtet, dass 37\times 54 = 1998 und 37\times 55 = 2035 gilt; daher ist der gesuchte Quotient q=54. Berechne nun den Rest r=2025-37q und überprüfe, dass 0\le r\lt 37 gilt. Bei der Überprüfung erhält man:

   r=2025-37\cdot 54=2025-1998=27.

   Somit gilt 2025=37\cdot 54+27 mit 0\le 27\lt 37.

3. Bestimme q und r so, dass

   745 = 23q + r,\qquad 0\le r\lt 23.

4. Bestimme q und r so, dass

   -314 = 11q + r,\qquad 0\le r\lt 11.

5. Bestimme q und r so, dass

   598 = (-21)q + r,\qquad 0\le r\lt |-21|.

6. Festgelegter Rest und Suche nach ganzen Zahlen. Sei a=12.

   (a) Beschreibe die Menge aller ganzen Zahlen b, deren euklidische Division durch 12 den Rest r=5 hat.

   (b) Bestimme die kleinste ganze Zahl b\gt 1000, die dies erfüllt, und bestimme den entsprechenden Quotienten q.

Schriftlicher Divisionsalgorithmus

Wende in jedem Fall den schriftlichen Divisionsalgorithmus an, um den Quotienten q und den Rest r zu berechnen. Überführe das Ergebnis in die euklidische Division, wenn der Algorithmus einen negativen Rest liefert.

1. 84\div 6.
2. 197\div 8.
3. 1256\div 7.
4. -3521\div 12.
5. -98765\div 24.
6. 845\div -13.
7. -12345\div -37.