2.1. Ganze Zahlen

Der zentrale Forschungsgegenstand der elementare Zahlentheorie ist die Menge der ganzen Zahlen \(\Z = \lbrace0, \pm 1, \pm 2, \pm 3, \ldots \rbrace\). Vergleicht man die Menge der ganzen Zahlen mit anderen Zahlsystemen so gilt bekanntermaßen:

\[\N \subset \Z \subset \Q \subset \R \subset \C\]

Im Gegensatz zu den natürlichen Zahlen \(\N\) ist die Menge \(\Z\) nicht nach unten beschränkt. Andererseits besitzt jede nach unten beschränkte Menge von ganzen Zahlen ein kleinstes Element, was z.B. in den reellen Zahlen \(\R\) im Allgemeinen nicht gilt. Analog gilt natürlich auch, dass jede nach oben beschränkte Menge von ganzen Zahlen ein größtes Element besitzt. Die Existenz eines solchen Elements führt uns zu folgender nützlichen Definition.

Definition 2.1 (Abrundungsfunktion)

Sei \(\alpha \in \R\) eine reelle Zahl, so definieren wir die Abrundung (oder auch untere Gaußklammer) von \(\alpha\) als:

\[\lfloor\alpha\rfloor \ \coloneqq \ \max \lbrace b \in \Z \: | \: b \leq \alpha \rbrace.\]

Somit ist \(\lfloor \alpha \rfloor\) also die größte ganze Zahl \(b\), die kleiner oder gleich \(\alpha\) ist.

Obwohl die Rundungsfunktion allgemein bekannt sein sollte, wollen wir deren Anwendung für ganze Zahlen kurz in einem Beispiel verdeutlichen.

Beispiel 2.1 (Abrundungsfunktion)

Wir stellen fest, dass für die Abrundungsfunktion gilt:

\[\lfloor 3.14 \rfloor = 3, \qquad \lfloor -3.14 \rfloor = -4, \qquad \lfloor -1 \rfloor = -1.\]

Es ist leicht einzusehen, dass für beliebige Zahlen \(\alpha \in \R\) gilt:

\[\floor{\alpha} \ \le \ \alpha \ < \ \floor{\alpha}+1.\]

Gilt außerdem \(\alpha \in \R^+_0\), so erhält man den Wert \(\floor{\alpha} \in \Z\) durch einfaches Abschneiden der Nachkommastellen der nichtnegativen, reellen Zahl \(\alpha\).

2.1.1. Teilbarkeit

Das Konzept der Teilbarkeit von ganzen Zahlen ist zentral für viele kryptographische Verfahren, die wir in dieser Vorlesung diskutieren werden. Daher widmen wir uns in diesem kurzen Abschnitt dediziert diesem elementaren Konzept.

Definition 2.2 (Teilbarkeit)

Für \(a,b\in\Z\) sagt man \(a\) teilt \(b\)  (oder \(a\) ist ein Teiler von \(b\)  oder \(b\) ist ein Vielfaches von \(a\)), falls eine ganze Zahl \(c\in\Z\) existiert, so dass gilt \(b=ca\).

Ist \(a\) ein Teiler von \(b\) so schreibt man \(a\mid b\). Teil \(a\) die Zahl \(b\) nicht, so schreibt man hingegen \(a\nmid b\).

Folgendes einfaches Beispiel soll die Notation nochmal konkret verdeutlichen.

Beispiel 2.2 (Teiler)

Es ist klar, dass die Zahl \(4\) ein Teiler der Zahl \(20\) ist, d.h. \(4 \mid 20\), da gilt \(20 = 5\cdot 4\). Andererseits teilt die Zahl \(4\) nicht die Zahl \(19\), d.h, \(4 \nmid 19\), da keine ganze Zahl \(c \in \Z\) existiert, so dass \(19 = c \cdot 4\) gilt.

Das folgende Lemma fasst die wichtigsten Inklusionen und elementaren Rechenregeln für die Teilbarkeit von ganzen Zahlen zusammen.

Lemma 2.1 (Eigenschaften von Teilern)

Für ganze Zahlen \(a,b,c,d\in\Z\) gelten die folgenden Teilbarkeitsregeln:

1. \(a\mid a\), \(1\mid a\), \(a\mid 0\).

2. \(a\mid b \ \wedge \ b\mid c \quad \Longrightarrow \quad a\mid c\) (Transitivität).

3. \(a\mid b \quad \iff \quad \pm a\mid \pm b\).

4. \(a\mid b \ \wedge \ b\mid a \quad \iff \quad a=\pm b\).

5. \(a\mid 1 \quad \iff \quad a=\pm 1\).

6. \(0\mid a \quad \iff \quad a=0\).

7. \(d\mid a \ \wedge \ d\mid b \quad \Longrightarrow \quad d\mid (ma+nb) \quad \forall m,n\in\Z\).

8. \(a\mid b \ \wedge \ a\ne 0 \quad \iff \quad \frac{b}{a}\in\Z\).

9. \(a\mid b \ \wedge \ a\ne 0 \quad \iff \quad b\bmod a=0\).

Proof. In den Hausaufgaben zu zeigen. ◻

Für betraglich kleine Zahlen benötigen wir meist keinen Algorithmus, um zu testen ob eine Zahl eine andere Zahl teilt. Anders sieht es jedoch aus, wenn wir mit sehr großen Zahlen arbeiten, wie es in der modernen Kryptographie typisch ist. Um zu beantworten, ob die Zahl \(a = 11111111111111\) ein Teiler von \(b = 12345678910987654321\) ist, benötigen wir effiziente Algorithmen, die uns eine klare Aussage liefern. Sobald wir in Modulare Arithmetik lernen wie man Divisionsreste algorithmisch ausrechnen kann, wird speziell die letzte Eigenschaft in Lemma 2.1 nützlich um die Teilbarkeit von zwei Zahlen zu testen.

2.1.2. Speicher- und Rechenaufwand

Zur Analyse und Bewertung kryptographischer Algorithmen ist es entscheidend abzuschätzen wie viele Berechnungen und Speicherplatz benötigt werden. Für den Rechenaufwand zählt man in der Regel die benötigte Anzahl an Additionen, Multiplikationen und Vergleichsoperationen. Angegeben wird der Rechenaufwand häufig in Floating Point Operations (abgekürzt als FLOPs), bei welchen historisch bedingt eine Addition und eine Multiplikation zu einer Rechenoperation zusammengefasst werden. Mit Hinblick auf moderne Mikroprozessorarchitekturen und paralleler Datenverarbeitung ist dies natürlich eine sehr starke Vereinfachung von realen Rechenwerken.

Um den Speicher- und Rechenaufwand eines Algorithmus oder Computerprogramms in eine Klasse von Funktionen einzuordnen, verwendet man typischerweise die Landausche \(\mathcal{O}\)-Notation.

Definition 2.3 (Landau-Notation)

Sind \(f:\N\to \R\), \(g:\N\to \R\) zwei reellwertige Funktionen, so schreibt man

\[f=\mathcal{O}(g)\quad \text{ oder }\quad f(n)=\mathcal{O}(g(n)),\]

falls Zahlen \(C\in\R^+\) und \(n_0\in\N\) existieren, so dass gilt

\[|f(n)| \ \le \ C g(n) \quad \forall n \geq n_0.\]

In diesem Fall ist \(g\) also eine asymptotisch obere Schranke für \(f\) und man sagt: \(f\) ist in Groß-O von \(g\).

Obwohl man \(f=\mathcal{O}(g)\) schreibt, hat hier das Gleichheitszeichen nicht die übliche Bedeutung. So gilt beispielsweise in der \(\mathcal{O}\)-Notation \(n=\mathcal{O}(n^2)\) und \(n=\mathcal{O}(n^3)\), aber die Funktionen \(n^2\) und \(n^3\) verhalten sich asymptotisch nicht gleich. In der Regel versuchen wir eine möglichst genaue (man spricht auch von scharfer) obere Schranke anzugeben.

Um das oben eingeführte abstrakte Konzept von asymptotischen Schranken verständlicher zu machen wollen wir einige konkrete Beispiele für die \(\mathcal{O}\)-Notation angeben.

Beispiel 2.3 (Rechenaufwand)

1. Sei der Rechenaufwand eines Algorithmus gegeben durch

   \[f(n) = 123n^2-33n+7+\ln n.\]

   Wir erkennen, dass \(f(n) = \mathcal{O}(n^2)\), da eine Konstante \(C \coloneqq 123 > 0\) und ein Index \(n_0 \coloneqq 1 > 0\) existieren, so dass gilt:

   \[|123n^2 - 33n + 7 + \ln n| \ \leq \ C n^2 \ = \ 123 n^2, \quad \forall n \geq n_0 = 1.\]

2. Die Anzahl der Vergleiche, die man beim Suchen eines Werts in einer unsortierten Menge aus \(n\) Elementen benötigt liegt in \(\mathcal{O}(n)\), da man jedes Element einzeln überprüfen muss.

   Ist die Menge bereits sortiert, so liegt die Anzahl der benötigten Vergleichsoperationen mit dem Intervallhalbierungsverfahren in \(\mathcal{O}(\operatorname{log} n)\).

In verschiedenen Teilen der Mathematik, beispielsweise in der analytischen Zahlentheorie oder in der numerischen Mathematik, ist auch folgende Schreibweise nützlich, um das Laufzeitverhalten von Algorithmen noch genauer anzugeben.

Definition 2.4 (Landau-Notation für Restglieder)

Seien \(f,g,h:\N\to\R\) drei reellwertige Funktionen, so schreibt man

\[f=g+\mathcal{O}(h)\quad\text{ oder }\quad f(n)=g(n)+\mathcal{O}(h(n)),\]

falls für das Restglied \(f(n)-g(n)=\mathcal{O}(h(n))\) gilt.

Für große \(n\) ist immer nur die führende Ordnung der asymptotischen Schranke für den Rechenaufwand interessant. Deshalb ist es nicht so wichtig die weiteren Ordnungen genauer zu bestimmen. So werden wir für ein Verfahren, dass beispielsweise \(2n^2+4n + 3\) Operationen benötigt, als Aufwand typischerweise \(2n^2 + \mathcal{O}(n)\) angeben. Diese Schreibweise wird auch zur Beschreibung von Fehlertermen und Restgliedern in Reihenentwicklungen genutzt, wie das folgende Beispiel illustriert.

Beispiel 2.4 (Harmonische Reihe)

Für die (divergierende) harmonische Reihe \(\sum_{k=1}^n\frac{1}{k}\) kann man schreiben

\[\sum_{k=1}^n\frac{1}{k} \ = \ \ln n+C + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} + \mathcal{O}\left(\frac{1}{n^6}\right) \ = \ \ln n+C+\mathcal{O}\left(\frac{1}{n}\right)\]

mit der Euler-Mascheroni Konstanten \(C=0.5772156649\dots\).

2.1.3. Zahldarstellungen

Definition 2.5 (b-adische Zahldarstellung)

Sei im Folgenden \(b\in\N\) eine natürliche Zahl mit \(b \ge 2\), die auch Basis genannt wird. Dann lässt sich jede natürliche Zahl \(n\in\N\) eindeutig in einem Stellenwertsystem bezüglich der Basis \(b\) schreiben als

\[n=\sum_{i=0}^{k-1}n_i\cdot b^i\quad\text{ mit }\quad n_i\in\{0,1,\dots,b-1\}.\]

Häufig notiert man die Koeffizienten \(n_0, \dots, n_{k-1}\) dieser Darstellung in Form eines Tupels:

\[n=(n_{k-1}n_{k-2}\dots n_1n_0)_b %\quad\text{ oder }\quad n=(n_{k-1},n_{k-2},\dots,n_1,n_0)_b\]

und nennt dies die \(\mathbf{b}\)-adische Darstellung der Zahl \(n\).

Ist \(n_{k-1}\ne 0\), so nennt man \(k\in\N\) die Stellenzahl der Zahl \(n\) in der \(b\)-adischen Darstellung.

Im Folgenden wollen wir einige Beispiele für unterschiedliche \(b\)-adische Zahldarstellung in Abhängigkeit der Basis diskutieren.

Beispiel 2.5 (b-adische Zahldarstellungen)

Wir betrachten in diesem Beispiel unterschiedliche Zahldarstellungen der natürlichen Zahl \(n=431\).

• Für die gewählte Basis \(b=10\) erhält man die übliche Dezimaldarstellung mit den Ziffern \(0,1,\dots,9\). Statt \((n_{k-1}\dots n_1n_0)_{10}\) schreiben wir typischerweise \(n_{k-1}\dots n_1n_0\). In diesem Fall gilt einfach:

  \[431 \ = \ 1\cdot 10^0 + 3\cdot 10^1 + 4\cdot10^2 \ = \ (431)_{10}.\]

• Für die Basis \(b=2\) hat man die Binärdarstellung mit den Ziffern \(0\) und \(1\), wie sie für die Zahldarstellung in Computern verwendet wird. In diesem Fall gilt:

  \[431 \ = \ 1\cdot 2^0 + 1\cdot 2^1 + 1\cdot 2^2 + 1\cdot 2^3 + 0\cdot 2^4 + 1\cdot 2^5 + 0\cdot 2^6 + 1\cdot 2^7 + 1\cdot 2^8 \ = \ (110101111)_2\]

• Für die Basis \(b=16\) hat man die Hexadezimaldarstellung. Als Ziffern benutzt man hierbei in der Regel \(0,1,\dots,9\),a,b,c,d,e,f oder \(0,1,\dots,9\),A,B,C,D,E,F. In diesem Fall gilt:

  \[431 \ = \ 15\cdot 16^0 + 10\cdot 16^1 + 1\cdot 16^2 \ = \ (1\texttt{AF})_{16}.\]

Wie Beispiel 2.5 zeigt, lässt sich eine natürliche Zahl äquivalent in unterschiedlichen Zahldarstellungen repräsentieren, wie beispielsweise die folgende \(27\)-Bit-Zahl:

\[(123456789)_{10} \ = \ (111010110111100110100010101)_2 \ = \ (75\texttt{BCD}15)_{16}.\]

Während Computer intern ausschließlich mit der binären Zahldarstellung operieren, wird in der Kryptographie häufig die Hexadezimaldarstellung zur Darstellung von Zahlen verwendet. Dies liegt zum Einen daran, dass diese Darstellung durch die größere Basis \(b = 16 > 10\) kompakter ist als die herkömmliche Zahldarstellung. Zum Anderen bildet die Hexadezimaldarstellung eine einfache Brücke zur Binärdarstellung, da jeweils zwei Zeichen unabhängig zu einem Byte (\(256 = 16^2\) mögliche Zahlen) zusammengefasst werden können und man anschließend die entstehenden Bytes nur noch konkatenieren muss, um die Binärdarstellung zu erhalten.

Bemerkung 2.1 (Konversion von Zahldarstellungen in Python)

1. In Python lassen sich Zahlen in Binärdarstellung durch Voranstellen der Zeichen 0b beispielsweise wie folgt definieren:

   n = 0b1011010011.
   

   Die Konversion einer natürlichen Zahl \(n\in\N\) in Binärdarstellung lässt sich durch bin(n){.python} realisieren. Mit int('0100111010', 2){.python} erhält man aus einer Binärzahl wieder eine natürliche Zahl in gewohnter Dezimaldarstellung.

2. In Python lassen sich Zahlen in Hexadezimaldarstellung durch Voranstellen der Zeichen 0x beispielsweise wie folgt definieren:

   n = 0xa3fc36a27b.
   

   Die Konversion einer natürlichen Zahl \(n\in\N\) in Hexadezimaldarstellung lässt sich durch hex(n){.python} realisieren. Mit int('13f45ac', 2){.python} erhält man aus einer Hexadezimalzahl wieder eine natürliche Zahl in gewohnter Dezimaldarstellung.

Mit Hilfe der Logarithmus-Funktion und der Abrundungsfunktion lässt sich die benötigte Anzahl an Stellen für eine \(b-\)adische Zahldarstellung exakt angeben, wie folgendes Lemma festhält.

Lemma 2.2 (Stellenanzahl)

Ist \(n\in\N\) eine natürliche Zahl und \(b\in\N, b \geq 2\) eine Basis, so hat \(n\) in der \(b\)-adischen Darstellung genau \(k\in \N\) Stellen mit:

\[k=\floor{\frac{\ln n}{\ln b}}+1.\]

Proof. Sei

\[n=\sum_{i=0}^{k-1}n_i\cdot b^i\quad\text{ mit }\quad n_i\in\{0,1,\dots,b-1\}\quad\text{ und }\quad n_{k-1}\ne 0.\]

Dann gilt

\[b^{k-1} \ \le \ n \ \le \ \sum_{i=0}^{k-1}(b-1)b^i \ = \ b^k-1 \ < \ b^k,\]

und damit \((k-1)\ln b\le \ln n<k \ln b\), also

\[k-1 \ \le \ \frac{\ln n}{\ln b} \ < \ k.\]

Dann ist

\[k-1 \ = \ \floor{\frac{\ln n}{\ln b}},\]

und damit

\[k \ = \ \floor{ \frac{\ln n}{\ln b}} + 1,\]

wie behauptet. ◻

Mit dem Landau-Symbol kann man die Stellenzahl einer natürlichen Zahl \(n\in\N\) also berechnen als

\[k \ = \ \left\lfloor\frac{\ln n}{\ln b}\right\rfloor+1.\]

Insbesondere ist \(k = O(\ln n)\), d.h. die Stellenzahl von \(n\) wächst wie \(\ln n\). Die Anzahl der Bits von \(n\) ist die Anzahl der Stellen in der Binärdarstellung und lässt sich konkret berechnen als \(\lfloor \frac{\ln n}{\ln 2}\rfloor +1\).

2.1.4. Modulare Arithmetik

Ganze Zahlen kann man addieren, subtrahieren und multiplizieren ohne die Menge \(\Z\) zu verlassen, d.h. die ganzen Zahlen sind abgeschlossen unter diesen mathematischen Operationen. Hierbei sind zudem eine Reihe von Gesetzmäßigkeiten erfüllt, wie beispielsweise die Assoziativität und Kommutativität von Addition und Multiplikation und die Distributivgesetze.

Anders sieht es jedoch mit der Division aus. Um zu gewährleisten, dass das Ergebnis der Division zweier ganzer Zahlen \(a,b \in \Z\) noch in den ganzen Zahlen liegt, muss \(a\) ein Teiler von \(b\) sein (siehe Teilbarkeit). Dies unterscheidet die ganzen Zahlen von den reellen Zahlen, für die zu jedem Element \(\alpha \in \R\setminus\lbrace 0\rbrace\) (d.h. außer der Null) ein multiplikativ inverses Element \(\frac{1}{\alpha} \in \R\) existiert. Algebraisch gesprochen bilden die reellen Zahlen \(\R\) mit den Verknüpfungen \(+\) und \(\cdot\) somit einen Körper, wohingegen die ganzen Zahlen \(\Z\) mit Addition und Multiplikation lediglich einen Integritätsring bilden. Dieser fundamentale Unterschied bildet die Grundlage für viele moderne kryptographische Verfahren.

Um die Nichtabgeschlossenheit der ganzen Zahlen \(\Z\) unter Division etwas abzumildern betrachtet man stattdessen für natürlichen Zahlen die Division mit Rest.

Definition 2.6 (Division mit Rest)

Teilt man eine natürliche Zahl \(a\in\N_0\) durch eine positive, natürliche Zahl \(b\in\N\), so erhält man bei der Division mit Rest einen Quotienten \(q\in\N_0\) und einen Rest \(r\in\N_0\), so dass gilt:

\[a:b \, = \, q \text{ mit Rest } r,\]

wobei der Rest \(r\) echt kleiner als der Divisor \(b\) ist.

Mathematisch lässt sich dies in der folgenden Form kompakt schreiben als:

\[a=qb+r\quad\text{ mit }\quad q,r\in\N_0\quad\text{ und }\quad 0\le r < b.\]

Wir rufen uns das aus der Schule bekannte Verfahren zur schriftlichen Division mit Rest mit folgendem Beispiel wieder ins Gedächtnis.

Beispiel 2.6 (Division mit Rest)

Wir teilen die Zahl 12345 durch 987 schriftlich mit folgendem schrittweisen Algorithmus:

\[\begin{matrix} 1 & 2 & 3 & 4 & 5 & : & 9 & 8 & 7 & = & 1 & 2 \\ - & - & - & - & \\ 1 & 2 & 3 & 4 \\ - & 9 & 8 & 7 \\ - & - & - & - \\ & 2 & 4 & 7 & 5 \\ - & 1 & 9 & 7 & 4 \\ & - & - & - & - \\ & & 5 & 0 & 1 \end{matrix}\]

Eine Division von 12345 durch 987 ergibt also 12 mit Rest 501.

Man kann die oben diskutierte Division mit Rest auch leicht auf ganze Zahlen ausdehnen, wobei wir uns hier lediglich auf den Fall \(a\in\Z\) und \(b\in\N\) beschränken.

Lemma 2.3 (Division mit Rest in den ganzen Zahlen)

Sei \(a\in\Z\) eine ganze Zahl und \(b\in\N\) eine natürliche Zahl. Wir definieren den Quotienten \(q \in \Z\) und den Divisionrest \(r \in \N_0\) als:

\[q := \floor{\frac{a}{b}}\qquad\text{ und }\qquad r := a-\floor{\frac{a}{b}}\,b.\]

Dann gilt schon für die Division mit Rest in \(\Z\) der Zusammenhang:

\[a=qb+r\quad\text{ mit }\quad q\in\Z\quad\text{ und }\quad r \in \N_0, 0\le r < b.\]

Proof. Wir setzen direkt die Definitionen des Quotienten \(q = \floor{\frac{a}{b}}\) und ebenfalls des Divisionsrests \(r = a-\floor{\frac{a}{b}}\,b\) ein und erhalten:

\[qb + r \ = \ \floor{\frac{a}{b}} b + a-\floor{\frac{a}{b}}\,b \ = \ a + \underbrace{\left( \floor{\frac{a}{b}} - \floor{\frac{a}{b}}\right)}_{=\,0} b \ = \ a.\]

◻

Für den Divisionsrest \(r \in \Z\) hat sich in diesem Kontext eine eigene Schreibweise eingebürgert.

Definition 2.7 (Modulo-Operation)

Für \(a\in\Z\) und \(b\in\N\) wird die Bezeichnung \(a\) modulo \(b\)  definiert als

\[a\bmod b \ := \ a-\floor{\frac{a}{b}}\,b.\]

Für \(a\in\Z\), \(b\in\N\) gilt also mit der eingeführten Modulo-Schreibweise

\[a \ = \ qb + r \ = \ \floor{\frac{a}{b}}\,b+(a\bmod b)\quad\text{ und }\quad 0\le (a\bmod b) < b.\]

Bemerkung 2.2 (Division mit Rest und Modulo-Operation)

1. Bei genauer Betrachtung stellt man fest, dass der Rechenaufwand für die Division mit Rest linear mit der Stellenzahl \(k\in\N\) des Divisors \(a \in \N\) wächst. Mit Lemma 2.2 erhalten wir somit einen Rechenaufwand von \(\mathcal{O}(k) = \mathcal{O}(\ln a)\).

2. Leider taucht die Bezeichung mod  in der Vorlesung in zwei leicht unterschiedlichen Bedeutungen auf. In Definition 2.7 bezeichnet mod  eigentlich eine Funktion

   \[\bmod:\Z\times \N\to\Z,\quad (a,b)\mapsto a-\floor{\frac{a}{b}}b,\]

   die aber anstatt wie üblich mit \(\bmod(a,b)\) traditionell in der Infix-Schreibweise \(a\bmod b\) geschrieben wird. Um \(a\bmod b\) als errechneten Funktionswert zu kennzeichnen schreiben wir daher auch manchmal \((a\bmod b)\).

3. Die Division mit Rest macht den Ring der ganzen Zahlen \(\Z\) algebraisch gesprochen zu einem euklidischen Ring.

4. In der Programmiersprache Python erhält man für \(a\in\Z\) und \(b\in\Z\) den Divisionsrest \(r = a\bmod b\) und den Quotienten \(q = \floor{\frac{a}{b}}\) wie folgt:

   a = 12345; b = 987
   
   q = a//b; q
   12
   
   r = a%b; r
   501
   

Das folgende Lemma zeigt, dass der Quotient \(q\) und der Divisionrest \(r\) durch die Bedingungen \(a=qb+r\) und \(0\le r\le b-1\) schon eindeutig bestimmt sind.

Lemma 2.4 (Eindeutigkeit des Quotienten und Divisionsrests in \Z)

Zu \(a\in\Z\) und \(b\in\N\) gibt es genau eine ganze Zahl \(q\in\Z\) und eine ganze Zahl \(r\in\Z\), so dass gilt

\[a=qb+r\qquad\text{ und }\qquad 0\le r < b.\]

Insbesondere sind diese eindeutigen Zahlen gegeben durch

\[q=\floor{\frac{a}{b}}\qquad\text{ und }\qquad r=(a\bmod b).\]

Proof. Wir wissen aus Lemma 2.3 bereits, dass \(q=\floor{\frac{a}{b}}\) und \(r=(a\bmod b)=a-\floor{\frac{a}{b}}b\) die Gleichung \(a=qb+r\) und die Abschätzung \(0\le r\ < b\) erfüllen. Seien nun umgekehrt zwei ganze Zahlen \(q,r\in\Z\) gegeben die für gegebenes \(a \in \Z\) und \(b \in \N\) folgende Bedingungen erfüllen:

\[a=qb+r\qquad\text{ und }\qquad 0\le r < b.\]

Eine Division der linken Gleichung durch \(b\) liefert nun

\[\frac{a}{b}=q+\frac{r}{b}.\]

Wegen der Ungleichung \(r\ge 0\) ist

\[q \ = \ \frac{a-r}{b} \ \le \ \frac{a}{b}.\]

Da außerdem die Ungleichung \(r\le b-1\) gilt, folgt

\[\frac{a}{b} \ = \ q+\frac{r}{b} \ \le \ q+\frac{b-1}{b} \ < \ q+\frac{b}{b} \ = \ q+1.\]

Damit haben wir eine untere und obere Schranke für den Quotienten gefunden, denn es gilt:

\[q \ \le \ \frac{a}{b} \ < \ q+1.\]

Da \(q \in \Z\) gelten muss folgt damit schon:

\[q=\floor{\frac{a}{b}} \qquad\text{ und damit }\qquad r=a-qb \ = \ a-\floor{\frac{a}{b}}b \ = \ (a\bmod b).\]

Dies beweist unsere Behauptung. ◻

Die Ungleichung \(0 \leq r < b\) ist für die Eindeutigkeit des Quotienten \(q \in \Z\) und des Divisionsrests \(r \in \Z\) im Beweis von Lemma 2.4 entscheidend. Ohne diese Bedingung gäbe es für gegebene Zahlen \(a\in \Z\) und \(b \in \N\) unendlich viele Zerlegungen der Art \(a = qb + r\), wie z.B. für die Zahlen \(a := 17, b = 4\):

\[17 = 4\cdot 4 + 1 \qquad \text{ und } \qquad 17 = 3 \cdot 4 + 5 \qquad \text{ und } \qquad 17 = 2 \cdot 4 + 9 \qquad \text{ und } \qquad \dots\]

Außerdem deckt sich die Bedingung \(0 \leq r < b\) mit der in der Praxis gängigen Vorstellung, dass man so viele volle Anteile der Größe \(b \in \N\) von einer Größe \(a \in \Z\) entnehmen möchte, wie möglich.