Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I/Vorlesung 14/latex
\setcounter{section}{14}
\epigraph { Kunst gibt nicht das Sichtbare wieder, sondern Kunst macht sichtbar } { Paul Klee }
\zwischenueberschrift{Division mit Rest}
Jede natürliche Zahl lässt sich bekanntlich als eine Ziffernfolge \anfuehrung{im Zehnersystem}{} ausdrücken. Dies beruht auf der \zusatzklammer {sukzessiven} {} {} Division mit Rest. Eine natürliche Zahl ist nicht durch jede natürliche Zahl teilbar, die Division mit Rest liefert eine Operation, die stets durchführbar ist.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Pie division.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Pie division.svg } {} {Dcoetzee} {Commons} {PD} {}
\inputfaktbeweis
{Division mit Rest/N/Induktion/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Es sei $d$ eine fixierte positive natürliche Zahl.}
\faktfolgerung {Dann gibt es zu jeder natürlichen Zahl $n$ eine eindeutig bestimmte natürliche Zahl $q$ und eine eindeutig bestimmte natürliche Zahl\zusatzfussnote {Bei $q$ denke man an Quotient und bei $r$ an Rest} {.} {}
\mathbed {r} {}
{0 \leq r \leq d-1} {}
{} {} {} {,} mit
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {qd+r
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
\teilbeweis {Zur Existenz.\leerzeichen{}}{Dies wird durch Induktion über $n$ bewiesen.\leerzeichen{}}{}
{Es sei
\mavergleichskette
{\vergleichskette
{ d
}
{ > }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
fixiert. Der Induktionsanfang für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ergibt sich direkt mit
\mavergleichskette
{\vergleichskette
{q
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ r
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Für den Induktionsschluss sei die Aussage für $n$ bewiesen, d.h. wir haben eine Darstellung
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ d q+r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ r
}
{ < }{ d
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und müssen eine ebensolche Darstellung für
\mathl{n+1}{} finden. Wenn
\mavergleichskette
{\vergleichskette
{ r
}
{ < }{ d-1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so ist
\mavergleichskettedisp
{\vergleichskette
{ n+1
}
{ =} { d q+r +1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und wegen
\mavergleichskette
{\vergleichskette
{ r+1
}
{ < }{ d
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist dies eine gesuchte Darstellung. Ist hingegen
\mavergleichskette
{\vergleichskette
{ r
}
{ = }{ d -1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so ist
\mavergleichskettedisp
{\vergleichskette
{ n+1
}
{ =} { d q+r +1
}
{ =} { dq + d
}
{ =} { d (q+1) +0
}
{ } {
}
}
{}{}{,}
und dies ist eine gesuchte Darstellung.}
{}
\teilbeweis {Zur Eindeutigkeit.\leerzeichen{}}{}{}
{Sei
\mavergleichskette
{\vergleichskette
{ qd+r
}
{ = }{ n
}
{ = }{ \tilde{q}d + \tilde{r}
}
{ }{
}
{ }{
}
}
{}{}{,}
wobei die Bedingungen jeweils erfüllt seien. Es sei ohne Einschränkung
\mavergleichskette
{\vergleichskette
{ \tilde{r}
}
{ \geq }{ r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann gilt
\mavergleichskette
{\vergleichskette
{ (q-\tilde{q})d
}
{ = }{ \tilde{r} -r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Diese Differenz ist nichtnegativ und kleiner als $d$, links steht aber ein Vielfaches von $d$, so dass die Differenz $0$ sein muss und die beiden Darstellungen übereinstimmen.}
{}
\inputbemerkung
{}
{
Zu gegebenen natürlichen Zahlen
\mathl{n,d}{} mit
\mavergleichskette
{\vergleichskette
{d
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
findet man die Division mit Rest, also die Darstellung
\mavergleichskette
{\vergleichskette
{n
}
{ = }{qd+r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
indem man der Reihe nach die Vielfachen von $d$ betrachtet. Das größte Vielfache von $d$
\zusatzklammer {gleich oder} {} {}
unterhalb von $n$ ist das gesuchte $qd$, insbesondere muss das nächste Vielfache
\mavergleichskette
{\vergleichskette
{(q+1)d
}
{ > }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sein. Der Rest ergibt sich dann als
\mavergleichskette
{\vergleichskette
{r
}
{ = }{n-qd
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
In der Schule verwendet man häufig eine Darstellung für die Division mit Rest wie
\mathdisp {n \text{ durch } d \text{ ist } q \text{ Rest } r} { . }
Dies ist in Hinblick auf die mathematische Weiterverarbeitung ungünstiger als die im Satz verwendete Gleichungsform.
\zwischenueberschrift{Zifferndarstellung für natürliche Zahlen}
Mit der Division mit Rest können wir die Existenz und Eindeutigkeit der üblichen Zifferndarstellung einer natürlichen Zahl beweisen. Hinter der Zifferndarstellung verbirgt sich eine Mischung aus Addition, Multiplikation und Potenzierung. Wir konzentrieren uns hauptsächlich auf die Ziffernentwicklung im \stichwort {Dezimalsystem} {} \zusatzklammer {oder \stichwort {Zehnersystem} {}} {} {.}
\inputfaktbeweis
{Natürliche Zahl/Eindeutige Darstellung im Zehnersystem/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Zu jeder natürlichen Zahl $n$}
\faktfolgerung {gibt es eindeutig bestimmte natürliche Zahlen $k$ und
\mathl{r_0,r_1, r_2 , \ldots , r_k}{} mit
\mavergleichskette
{\vergleichskette
{0
}
{ \leq }{r_i
}
{ \leq }{9
}
{ }{
}
{ }{
}
}
{}{}{}
und mit
\mavergleichskette
{\vergleichskette
{ r_k
}
{ \neq }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {außer bei
\mavergleichskettek
{\vergleichskettek
{ n
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {}
mit der Eigenschaft
\mavergleichskettedisp
{\vergleichskette
{ n
}
{ =} { \sum_{i = 0}^k r_i 10^{i}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
\teilbeweis {}{}{}
{Wir beweisen die Existenzaussage durch Induktion über $n$. Für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
wählt man
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{r_0
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.} Es sei nun
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und die Aussage für kleinere Zahlen schon bewiesen. Nach
Satz 14.1
mit
\mavergleichskette
{\vergleichskette
{d
}
{ = }{ 10
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es eine Darstellung
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} { q \cdot 10 +r_0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit $r_0$ zwischen $0$ und $9$. Es ist
\mavergleichskette
{\vergleichskette
{q
}
{ < }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
deshalb gilt nach Induktionsvoraussetzung die Aussage für $q$. D.h. man kann
\mavergleichskettedisp
{\vergleichskette
{q
}
{ =} { \sum_{i = 0}^\ell s_i 10^i
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{0
}
{ \leq }{ s_i
}
{ \leq }{ 9
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {bei \mathlk{q=0}{} ist dies als leere Summe zu lesen} {} {}
und mit
\mavergleichskette
{\vergleichskette
{ s_\ell
}
{ \neq }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
schreiben. Daher ist
\mavergleichskettealign
{\vergleichskettealign
{ n
}
{ =} {q \cdot 10 +r_0
}
{ =} { { \left( \sum_{i = 0}^\ell s_i 10^i \right) } \cdot 10 +r_0
}
{ =} { \sum_{i = 0}^\ell { \left( s_i 10^{i +1} \right) } + r_0
}
{ =} { \sum_{j = 1}^{\ell+1} { \left( s_{j-1} 10^{j} \right) } + r_0
}
}
{}
{}{}
eine Darstellung der gesuchten Art. Dabei ist
\mavergleichskette
{\vergleichskette
{ r_j
}
{ = }{ s_{j-1}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für
\mavergleichskette
{\vergleichskette
{j
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ \ell +1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
{}
\teilbeweis {}{}{}
{Die Eindeutigkeit folgt ebenfalls aus der Eindeutigkeit bei der Division mit Rest, siehe
Aufgabe 14.11.}
{}
Eine natürliche Zahl wird im Zehnersystem einfach dadurch angegeben, dass die Ziffern nebeneinander hingeschrieben werden, wobei links die höchststellige Ziffer
\zusatzklammer {die vorderste Ziffer} {} {}
und rechts die niedrigststellige Ziffer, also die Einerziffer, steht. Die Zahl
\mathdisp {4 \cdot 10^5 + 6 \cdot 10^4+3 \cdot 10^3+0 \cdot 10^2 + 7 \cdot 10^1 +5 \cdot 10^0} { }
wird also einfach als
\mathdisp {463075} { }
geschrieben
\zusatzklammer {in der gemischten Summen-und Produktdarstellung hätte man den Ausdruck
\mathl{0 \cdot 10^2}{} auch weglassen können, nicht aber in der Dezimaldarstellung} {} {.}
Eine beliebige natürliche Zahl im Dezimalsystem mit $k$ Ziffern gibt man als
\mathdisp {a_{k-1}a_{k-2} \ldots a_2a_1a_0} { }
an, was die Zahl
\mathdisp {a_{k-1} 10^{k-1} + a_{k-2} 10^{k-2} + \cdots + a_2 10^2 + a_1 10 +a_0} { }
bedeutet. Man beachte, dass wegen der gewünschten Kongruenz
\mathl{a_i 10^{i}}{} die Durchnummerierung der Ziffern bei $0$ anfängt, und somit bei insgesamt $k$ Ziffern die höchststellige Ziffer die Nummer
\mathl{k-1}{} besitzt. Wenn man von der $i$-ten Ziffer spricht, meint man die Ziffer, die sich auf
\mathl{10^{i}}{} bezieht. Von daher spricht man besser von der Einerziffer
\zusatzklammer {bezieht sich auf
\mavergleichskette
{\vergleichskette
{1
}
{ = }{10^0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {,}
der Zehnerziffer, der Hunderterziffer, der Tausenderziffer u.s.w. Gelegentlich ist es sinnvoll, auch Ziffernentwicklungen zuzulassen, die vorne mit Nullen beginnen, beispielsweise wenn man bei der Addition zweier natürlicher Zahlen gleich viele Ziffern haben möchte.
\inputbemerkung
{}
{
Aus dem Beweis zu Satz 14.1 kann man ablesen, wie man zu einer irgendwie gegebenen natürlichen Zahl $n$ die Entwicklung im Zehnersystem erhält. Man dividiert die Zahl $n$ durch $10$ und der Rest ergibt die Endziffer. Dann zieht man von $n$ diesen Rest ab und weiß, dass diese Zahl ein Vielfaches von $10$ ist. Man dividiert sie durch $10$ und bestimmt für das Ergebnis erneut den Rest, der die Zehnerziffer gibt, u.s.w. Bei diesem Verfahren berechnet man also die Ziffern von hinten nach vorne.
Ein anderes Verfahren, bei dem man die Ziffern von vorne nach hinten berechnet, geht folgendermaßen: Man bestimmt die maximale Zehnerpotenz
\mathl{10^k}{,} die in $n$ hineinpasst, es muss also
\mavergleichskettedisp
{\vergleichskette
{10^k
}
{ \leq} {n
}
{ <} {10^{k+1}
}
{ } {
}
{ } {
}
}
{}{}{}
gelten. Dann findet man das maximale Vielfache von
\mathl{10^k}{,} das in $n$ hineinpasst, also die Zahl $z$ mit
\mavergleichskettedisp
{\vergleichskette
{z \cdot 10^k
}
{ \leq} {n
}
{ <} {(z+1) 10^{k}
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Zahl muss zwischen
\mathkor {} {1} {und} {9} {}
liegen. Der Wert
\mavergleichskettedisp
{\vergleichskette
{z
}
{ =} {0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
kann nicht sein, da ansonsten
\mavergleichskette
{\vergleichskette
{n
}
{ < }{10^k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
im Widerspruch zur Wahl der Zehnerpotenz wäre, ein Wert
\mavergleichskette
{\vergleichskette
{z
}
{ \geq }{10
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
kann nicht sein, da ansonsten
\mavergleichskettedisp
{\vergleichskette
{n
}
{ \geq} { z 10^k
}
{ \geq} { 10^{k+1}
}
{ } {
}
{ } {
}
}
{}{}{}
wäre, was wieder der Wahl der Zehnerpotenz widerspricht. Diese Ziffer
\mavergleichskette
{\vergleichskette
{z
}
{ = }{ c_k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist dann die Anfangsziffer der Dezimalentwicklung. Nun rechnet man
\mathdisp {n- c_k10^k} { }
und weiß nach der Wahl von
\mathkor {} {k} {und} {c_k} {,}
dass diese neue Zahl $\tilde{n}$ echt kleiner als
\mathl{10^{k}}{} ist. Man bestimmt das maximale Vielfache von
\mathl{10^{k-1}}{} unterhalb von $\tilde{n}$, der Vorfaktor
\zusatzklammer {der jetzt auch $0$ sein kann} {} {}
ergibt die Ziffer
\mathl{c_{k-1}}{} und man zieht das Vielfache von $\tilde{n}$ ab und wiederholt das Verfahren.
}
\inputbemerkung
{}
{
Es sei eine natürliche Zahl in der Form
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{n
}
{ =} {c_k 10^k + c_{k-1} 10^{k-1} + \cdots + c_2 10^2 + c_1 10^1 + c_0 10^0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gegeben, wobei die $c_i$ beliebige natürliche Zahlen sind, also nicht unbedingt kleiner als $10$ sein müssen. Die zu $n$ gehörige Dezimalentwicklung erhält man sukzessive durch folgende Vorgehensweise. Man führt für $c_0$
die Division mit Rest
durch $10$ durch und erhält eine Darstellung
\mavergleichskettedisp
{\vergleichskette
{c_0
}
{ =} { 10 \cdot q_0 + a_0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit einem Rest
\mathbed {a_0} {}
{0 \leq a_0 < 10} {}
{} {} {} {.}
Damit ist
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{n
}
{ =} {c_k 10^k + c_{k-1} 10^{k-1} + \cdots + c_2 10^2 + c_1 10^1 + c_0 10^0
}
{ =} {c_k 10^k + c_{k-1} 10^{k-1} + \cdots + c_2 10^2 + c_1 10^1 + { \left( 10 \cdot q_0 + a_0 \right) } 10^0
}
{ =} {c_k 10^k + c_{k-1} 10^{k-1} + \cdots + c_2 10^2 + c_1 10^1 + q_0 10 + a_0 10^0
}
{ =} {c_k 10^k + c_{k-1} 10^{k-1} + \cdots + c_2 10^2 + { \left( c_1 + q_0 \right) } 10^1 + a_0 10^0
}
}
{}
{}{.}
Somit haben wir eine neue Darstellung von $n$, bei der die Einerziffer kleiner als $10$ ist. Als nächstes arbeitet man den neuen Vorfaktor
\zusatzklammer {also \mathlk{c_1+q_0}{}} {} {}
zu $10^1$ ab und bringt ihn auf die erlaubte Zifferngestalt, wobei der davor liegenden Vorfaktor wieder geändert wird. Dies führt letztlich zur Darstellung im Dezimalsystem.
}
\inputbemerkung
{}
{
Für Rechnungen ist das Dezimalsystem sehr gut geeignet, wie die aus der Schule bekannten und im Laufe der Vorlesung zu entwickelnden Algorithmen zeigen werden, für theoretische Überlegungen und Beweise, auch über das Dezimalsystem selbst, ist die obige gemischte Summen- und Produktdarstellung besser geeignet, da darin die grundlegenden Verknüpfungen auf den natürlichen Zahlen sichtbar werden.
}
Eine zu
Satz 14.1
entsprechende Aussage gilt für jede Basis
\mathl{g \geq 2}{} statt
\mathl{g=10}{.} Bei
\mavergleichskette
{\vergleichskette
{g
}
{ = }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
spricht man vom \stichwort {Dualsystem} {,} die einzigen Ziffern sind
\mathkor {} {0} {und} {1} {,}
bei
\mathl{g=3}{} vom \stichwort {Dreiersystem} {} mit den Ziffern
\mathl{0,1,2}{} u.s.w. Bei
\mavergleichskette
{\vergleichskette
{g
}
{ = }{16
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
spricht man vom \stichwort {Hexadezimalsystem} {} und verwendet die Ziffern
\mathl{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}{.}
Dass das Dezimalsystem nur eine unter vielen möglichen Darstellungen einer natürlichen Zahl ist, wird besonders deutlich, wenn man Darstellungen in verschiedenen Ziffernsystemen \zusatzklammer {oder \stichwort {Stellenwertsystemen} {}} {} {} ineinander umrechnet.
\inputbeispiel{}
{
Wir wollen die im Dezimalsystem gegebene Zahl
\mathl{187}{} im Dreiersystem ausdrücken. Dazu müssen wir
\zusatzklammer {analog zur zweiten Methode aus
Bemerkung *****} {} {}
die größte Dreierpotenz finden, die unterhalb $187$ liegt. Das ist
\mavergleichskettedisp
{\vergleichskette
{81
}
{ =} {3^4
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {da
\mavergleichskette
{\vergleichskette
{ 243
}
{ = }{ 3^5
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zu groß ist} {} {.}
Für diese Potenz müssen wir schauen, wie oft sie in $187$ hineingeht. Wegen
\mavergleichskettedisp
{\vergleichskette
{ 2 \cdot 81
}
{ =} {162
}
{ <} { 187
}
{ } {
}
{ } {
}
}
{}{}{}
sind das zweimal. Wir wissen daher, dass die Entwicklung der Zahl im Dreiersystem
\mathl{2 \cdot 3^4}{} beinhaltet, die Ziffer $2$ steht somit als Anfangsziffer fest. Die weitere Ziffernentwicklung hängt jetzt nur von der Differenz
\mavergleichskettedisp
{\vergleichskette
{187 -162
}
{ =} { 25
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ab. Diese Zahl ist kleiner als
\mavergleichskettedisp
{\vergleichskette
{27
}
{ =} {3^3
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
was bedeutet, dass die dritte Dreierpotenz \anfuehrung{gar nicht}{} und das heißt hier mit der Ziffer $0$ vorkommt. Wir arbeiten dann mit $25$ und mit der nächstkleineren Dreierpotenz weiter, also mit
\mavergleichskettedisp
{\vergleichskette
{9
}
{ =} {3^2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese hat wieder zweimal Platz in $25$, die Differenz ist
\mavergleichskettedisp
{\vergleichskette
{25 -18
}
{ =} {7
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Die
\mavergleichskettedisp
{\vergleichskette
{3
}
{ =} {3^1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
passt wieder zweimal rein, übrig bleibt $1$. Im Dreiersystem lautet also die Ziffernentwicklung
\mathdisp {20221} { . }
Diese Ziffernfolge kann man sukzessive notieren
\zusatzklammer {Nullen nicht vergessen} {} {}
oder aber in der Rechnung stets deutlich machen, auf welche Potenz sich der jeweilige Rechenschritt bezieht und dann zum Schluss daraus die Ziffernfolge ablesen.
}
| << | Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I | >> |
|---|