Kurs:Vorkurs Mathematik (Osnabrück 2021)/Vorlesung 1/latex
\setcounter{section}{1}
\zwischenueberschrift{Ganze Zahlen und Rechengesetze}
Wir arbeiten mit den folgenden Mengen, deren Kenntnis wir voraussetzen.
\mavergleichskettedisp
{\vergleichskette
{ \N
}
{ =} { \{0,1,2, \ldots \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
die Menge der \stichwort {natürlichen Zahlen} {}
\zusatzklammer {mit der $0$} {} {.}
\mavergleichskettedisp
{\vergleichskette
{ \Z
}
{ =} { \{\ldots, -2,-1, 0,1,2, \ldots \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
die Menge der \stichwort {ganzen Zahlen} {.}
Diese Mengen sind mit den natürlichen Operationen Addition und Multiplikation versehen, an deren Eigenschaften wir erinnern
Die Addition auf $\Z$ erfüllt die folgenden Eigenschaften.
\aufzaehlungvier{Es ist
\mavergleichskettedisp
{\vergleichskette
{ (a+b)+c
}
{ =} { a+ (b+c)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für beliebige
\zusatzklammer {alle} {} {}
Zahlen
\mavergleichskette
{\vergleichskette
{a,b,c
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
d.h. die Addition ist \stichwort {assoziativ} {.}
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{a+b
}
{ =} {b+a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für beliebige Zahlen
\mavergleichskette
{\vergleichskette
{a,b
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
d.h. die Addition ist \stichwort {kommutativ} {.}
}{Es gilt
\mavergleichskettedisp
{\vergleichskette
{a+0
}
{ =} {a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für jedes
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {man sagt, dass $0$ das \stichwort {neutrale Element} {}
der Addition ist} {} {.}
}{Zu jedem
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
besitzt
\mathl{-a}{} die Eigenschaft
\mavergleichskettedisp
{\vergleichskette
{a + (-a)
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {man sagt, dass $-a$ das \stichwort {negative Element} {}
zu $a$ ist} {} {.}
}
Die Multiplikation auf $\Z$ erfüllt die folgenden Eigenschaften.
\aufzaehlungdrei{Es ist
\mavergleichskettedisp
{\vergleichskette
{ (a \cdot b) \cdot c
}
{ =} { a \cdot (b \cdot c)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für beliebige
\zusatzklammer {alle} {} {}
Zahlen
\mavergleichskette
{\vergleichskette
{a,b,c
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
d.h. die Multiplikation ist \stichwort {assoziativ} {.}
}{Es ist
\mavergleichskettedisp
{\vergleichskette
{ a \cdot b
}
{ =} { b \cdot a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für beliebige Zahlen
\mavergleichskette
{\vergleichskette
{a,b
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
d.h. die Multiplikation ist \stichwort {kommutativ} {.}
}{Es gilt
\mavergleichskettedisp
{\vergleichskette
{a \cdot 1
}
{ =} {a
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für jedes
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {man sagt, dass $1$ das \stichwort {neutrale Element} {}
der Multiplikation ist} {} {.}
}
Man spricht auch vom Assoziativgesetz der Addition u.s.w.. Addition und Multiplikation sind durch das sogenannte \stichwort {Distributivgesetz} {} miteinander verbunden. Dieses besagt
\mavergleichskettedisp
{\vergleichskette
{ a \cdot (b+c)
}
{ =} { { \left( a \cdot b \right) } + { \left( a \cdot c \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{ a,b,c
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Auf den ganzen Zahlen ist die \stichwort {Größer/Gleich-Beziehung} {}
\zusatzklammer {oder \stichwort {Ordnungsbeziehung} {}} {} {}
definiert. Man schreibt
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wenn $a$ mindestens so groß wie $b$ ist. Eine ganze Zahl $a$ ist genau dann eine natürliche Zahl, wenn
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Die Beziehung
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt genau dann, wenn es eine natürliche Zahl $c$ mit
\mavergleichskette
{\vergleichskette
{a
}
{ = }{b+c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt. Für die Ordnungsbeziehung gelten die folgenden Regeln, und zwar für beliebige ganze Zahlen
\mavergleichskette
{\vergleichskette
{a,b,c
}
{ \in }{ \Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{:}
\aufzaehlungsechs{Es ist
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {dies nennt man die \stichwort {Reflexivität} {} der Ordnung} {} {.}
}{Aus
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{b
}
{ \geq }{c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {dies nennt man die \stichwort {Transitivität} {} der Ordnung} {} {.}
}{Aus
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{b
}
{ \geq }{a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{a
}
{ = }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {dies nennt man die \stichwort {Antisymmetrie} {} der Ordnung} {} {.}
}{Aus
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{a+c
}
{ \geq }{b+c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {dies nennt man die \stichwort {Additivität} {} der Ordnung} {} {.}
}{Aus
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{c
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{ c \cdot a
}
{ \geq }{ c \cdot b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {dies nennt man die \stichwort {Multiplikativität} {} der Ordnung} {} {.}
}{Aus
\mavergleichskette
{\vergleichskette
{a
}
{ \geq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ c
}
{ \in }{ \Z_-
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {also $c$ negativ} {} {}
folgt
\mavergleichskette
{\vergleichskette
{ c \cdot a
}
{ \leq }{ c \cdot b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Bei der Multiplikation mit einer negativen Zahl dreht sich also die Ordnungsbeziehung um.
\zwischenueberschrift{Induktion}
Die natürlichen Zahlen sind dadurch ausgezeichnet, dass man jede natürliche Zahl ausgehend von der $0$ durch den Zählprozess \zusatzklammer {das sukzessive Nachfolgernehmen} {} {} erreichen kann. Daher können mathematische Aussagen, die von natürlichen Zahlen abhängen, mit dem Beweisprinzip der \stichwort {vollständigen Induktion} {} bewiesen werden. Das folgende Beispiel soll an dieses Argumentationsschema heranführen.
\inputbeispiel{}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {4Geraden6Schnittpunkte.png} }
\end{center}
\bildtext {} }
\bildlizenz { 4Geraden6Schnittpunkte.png } {} {Mgausmann} {CC-by-sa 4.0} {} {}
Wir betrachten in der Ebene $E$ eine Konfiguration von $n$ Geraden und fragen uns, was die maximale Anzahl an Schnittpunkten ist, die eine solche Konfiguration haben kann. Dabei ist es egal, ob wir uns die Ebene als einen $\R^2$
\zusatzklammer {eine kartesische Ebene mit Koordinaten} {} {}
oder einfach elementargeometrisch vorstellen, wichtig ist im Moment allein, dass sich zwei Geraden in genau einem Punkt schneiden können oder aber parallel sein können. Wenn $n$ klein ist, so findet man relativ schnell die Antwort.
\wertetabellesiebenausteilzeilen { $n$ }
{\mazeileundfuenf {0} {1} {2} {3} {4} }
{\mazeileundzwei {5} {n} }
{ $S(n)$ }
{\mazeileundfuenf {0} {0} {1} {3} {6} }
{\mazeileundzwei {?} {?} }
Doch schon bei etwas größerem $n$
\zusatzklammer {
\mavergleichskettek
{\vergleichskettek
{n
}
{ = }{5,10, \ldots
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {?} {}
kann man ins Grübeln kommen, da man sich die Situation irgendwann nicht mehr präzise vorstellen kann. Aus einer präzisen Vorstellung wird eine Vorstellung von vielen Geraden mit vielen Schnittpunkten, woraus man aber keine exakte Anzahl der Schnittpunkte ablesen kann. Ein sinnvoller Ansatz zum Verständnis des Problems ist es, sich zu fragen, was eigentlich passiert, wenn eine neue Gerade hinzukommt, wenn also aus $n$ Geraden $n+1$ Geraden werden. Angenommen, man weiß aus irgendeinem Grund, was die maximale Anzahl der Schnittpunkte bei $n$ Geraden ist, im besten Fall hat man dafür eine Formel. Wenn man dann versteht, wie viele neue Schnittpunkte maximal bei der Hinzunahme von einer neuen Geraden hinzukommen, so weiß man, wie die Anzahl der maximalen Schnittpunkte von
\mathl{n+1}{} Geraden lautet.
Dieser Übergang ist in der Tat einfach zu verstehen. Die neue Gerade kann höchstens jede der $n$ alten Geraden in genau einem Punkt schneiden, deshalb kommen höchstens $n$ neue Schnittpunkte hinzu. Wenn man die neue Gerade so wählt, dass sie zu keiner der gegebenen Geraden parallel ist
\zusatzklammer {was möglich ist, da es unendlich viele Richtungen gibt} {} {}
und ferner so wählt, dass die neuen Schnittpunkte von den schon gegebenen Schnittpunkten der Konfiguration verschieden sind
\zusatzklammer {was man erreichen kann, indem man die neue Gerade parallel verschiebt, um den alten Schnittpunkten auszuweichen} {} {,}
so erhält man genau $n$ neue Schnittpunkte. Von daher ergibt sich die
\zusatzklammer {vorläufige} {} {}
Formel
\mavergleichskettedisp
{\vergleichskette
{S(n+1)
}
{ =} { 1+2+3 + \cdots + n-2 + n-1 +n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
bzw.
\mavergleichskettedisp
{\vergleichskette
{S(n)
}
{ =} { 1+2+3 + \cdots + n-3 + n-2 + n-1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
also einfach die Summe der ersten $n-1$ natürlichen Zahlen.
}
Im vorstehenden Beispiel liegt eine Summe vor, wobei die Anzahl der Summanden selbst variieren kann. Für eine solche Situation ist das \stichwort {Summenzeichen} {} sinnvoll. Für gegebene reelle Zahlen
\mathl{a_1 , \ldots , a_n}{} bedeutet.
\mavergleichskettedisp
{\vergleichskette
{ \sum_{k = 1}^n a_k
}
{ \defeq} { a_1 + a_2 + \cdots + a_{n-1} + a_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dabei hängen im Allgemeinen die $a_k$ in einer formelhaften Weise von $k$ ab, beispielsweise ist im Beispiel
\mavergleichskette
{\vergleichskette
{ a_k
}
{ = }{ k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
es könnte aber auch etwas wie
\mavergleichskette
{\vergleichskette
{ a_k
}
{ = }{ 2k+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{a_k
}
{ = }{ k^2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
vorliegen. Der $k$-te Summand der Summe ist jedenfalls $a_k$, dabei nennt man $k$ den \stichwort {Index} {} des Summanden. Entsprechend ist das \stichwort {Produktzeichen} {} definiert, nämlich durch
\mavergleichskettedisp
{\vergleichskette
{ \prod_{k = 1}^n a_k
}
{ \defeq} { a_1 \cdot a_2 { \cdots } a_{n-1} \cdot a_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
\inputbeispiel{}
{
Wir möchten für die Summe der ersten $n$ Zahlen, die die maximale Anzahl der Schnittpunkte in einer Konfiguration aus $n+1$ Geraden angibt, eine einfachere Formel angeben. Und zwar behaupten wir, dass
\mavergleichskettedisp
{\vergleichskette
{ \sum_{k = 1}^n k
}
{ =} { { \frac{ n(n+1) }{ 2 } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Für kleinere Zahlen $n$ stimmt dies aus dem einfachen Grund, dass links und rechts dasselbe herauskommt. Um die Gleichung allgemein zu beweisen, überlegen wir uns, was links und was rechts passiert, wenn wir das $n$ um $1$ erhöhen, so wie wir in
Beispiel 1.1
die Geradenkonfiguration um eine zusätzliche Gerade verkompliziert haben. Auf der linken Seite kommt einfach der zusätzliche Summand $n+1$ hinzu. Auf der rechten Seite haben wir den Übergang von
\mathl{{ \frac{ n(n+1) }{ 2 } }}{} nach
\mathl{{ \frac{ (n+1)(n+1+1) }{ 2 } }}{.} Wenn wir zeigen können, dass die Differenz zwischen diesen beiden Brüchen ebenfalls
\mathl{n+1}{} ist, so verhält sich die rechte Seite genauso wie die linke Seite. Dann kann man so schließen: die Gleichung gilt für die kleinen $n$, etwa für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Durch den Differenzenvergleich gilt es auch für das nächste $n$, also für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
durch den Differenzenvergleich gilt es für das nächste $n$, u.s.w. Da dieses Argument immer funktioniert, und da man jede natürliche Zahl irgendwann durch sukzessives Nachfolgernehmen erreicht, gilt die Formel für jede natürliche Zahl.
}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Domen-indukto.gif} }
\end{center}
\bildtext {Eine Visualisierung des Induktionsprinzips. Wenn die Steine nah beieinander stehen und der erste umgestoßen wird, so fallen alle Steine um.} }
\bildlizenz { Domen-indukto.gif } {Joachim Mohr} {} {Commons} {CC-by-sa 3.0} {}
Die folgende Aussage begründet das Prinzip der vollständigen Induktion.
\inputfaktbeweis
{Zahlentheorie/Beweisverfahren/Induktionsprinzip/Fakt}
{Satz}
{}
{
\faktsituation {Für jede
\definitionsverweis {natürliche Zahl}{}{}
$n$ sei eine Aussage
\mathl{A(n)}{} gegeben.}
\faktvoraussetzung {Es gelte
\aufzaehlungzwei {$A(0)$ ist wahr.
} { Für alle $n$ gilt: wenn
\mathl{A(n)}{} gilt, so ist auch
\mathl{A(n+1)}{} wahr.
}}
\faktfolgerung {Dann gilt
\mathl{A(n)}{} für alle $n$.}
\faktzusatz {}
\faktzusatz {}
}
{
Wegen der ersten Voraussetzung gilt
\mathl{A(0)}{.} Wegen der zweiten Voraussetzung gilt auch
\mathl{A(1)}{.} Deshalb gilt auch
\mathl{A(2)}{.} Deshalb gilt auch
\mathl{A(3)}{.} Da man so beliebig weitergehen kann und dabei jede natürliche Zahl erhält, gilt die Aussage
\mathl{A(n)}{} für jede natürliche Zahl $n$.
Der Nachweis von
\mathl{A(0)}{} heißt dabei der \stichwort {Induktionsanfang} {} und der Schluss von
\mathl{A(n)}{} auf
\mathl{A(n+1)}{} heißt der \stichwort {Induktionsschritt} {.} Innerhalb des Induktionsschrittes nennt man die Gültigkeit von $A(n)$ die \stichwort {Induktionsvoraussetzung} {.} In manchen Situationen ist die Aussage
\mathl{A(n)}{} erst für
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{n_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für ein gewisses $n_0$
\zusatzklammer {definiert oder} {} {}
wahr. Dann beweist man im Induktionsanfang die Aussage
\mathl{A(n_0)}{} und den Induktionsschluss führt man für
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{n_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
durch.
Wir begründen nun die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ \sum_{k = 1}^n k
}
{ =} { { \frac{ n(n+1) }{ 2 } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
mit dem Induktionsprinzip.
Beim Induktionsanfang ist
\mavergleichskette
{\vergleichskette
{n
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
daher besteht die Summe links nur aus einem Summanden, nämlich der $1$, und daher ist die Summe $1$. Die rechte Seite ist
\mavergleichskette
{\vergleichskette
{ { \frac{ 1 \cdot 2 }{ 2 } }
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so dass die Formel für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
stimmt.
Für den Induktionsschritt setzen wir voraus, dass die Formel für ein
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt, und müssen zeigen, dass sie dann auch für
\mathl{n+1}{} gilt. Dabei ist $n$ beliebig. Es ist.
\mavergleichskettealign
{\vergleichskettealign
{ \sum_{k = 1}^{n+1} k
}
{ =} { { \left( \sum_{k = 1}^{n} k \right) } + n+1
}
{ =} { { \frac{ n(n+1) }{ 2 } } + n+1
}
{ =} { { \frac{ n(n+1) +2(n+1) }{ 2 } }
}
{ =} { { \frac{ (n+2)(n+1) }{ 2 } }
}
}
{}
{}{.}
Dabei haben wir für die zweite Gleichheit die Induktionsvoraussetzung verwendet. Der zuletzt erhaltene Term ist die rechte Seite der Formel für
\mathl{n+1}{,} also ist die Formel bewiesen.
Aussagen, die durch Induktion bewiesen werden können, können manchmal auch auf andere Art bewiesen werden. Im vorstehenden Beispiel gibt es die elegantere und einsichtigere Lösung,
die Zahlen einmal aufsteigend und einmal absteigend untereinander hinzuschreiben, also
\mathdisp {1 \, \,\, \, \, \, \, \,\, \, \, \, 2\, \, \, \,\, \, \, \,\, \, \, \, \, \, \, \,3 \, \, \, \, { \cdots }\, \, \, \, n-2 \, \, \, \, n-1\, \, \, \, n} { }
\mathdisp {n\, \, \, \, \, n-1 \, \, \, \, \, \, n-2 \, \,\, \, { \cdots }\, \,\, \, 3\, \, \, \, \, \,\, \, \, \, \, \, \, \, \, \, 2\, \, \, \, \, \, \, \, \,\, \, \, 1} { }
Spaltenweise ergibt sich
\mathl{n+1}{,} und diese Summe kommt $n$-mal vor. Also ist
\mavergleichskettedisp
{\vergleichskette
{ 2 { \left( \sum_{i= 1}^n i \right) }
}
{ =} { n { \left( n+1 \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
\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.
\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.}
{}
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.
\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 1.4
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 1.28.}
{}
Eine entsprechende Aussage gilt für jede Basis
\mavergleichskette
{\vergleichskette
{g
}
{ \geq }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
statt
\mavergleichskette
{\vergleichskette
{g
}
{ = }{ 10
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Bei
\mavergleichskette
{\vergleichskette
{g
}
{ = }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
spricht man vom \stichwort {Dualsystem} {,} die einzigen Ziffern sind
\mathkor {} {0} {und} {1} {,}
bei
\mavergleichskette
{\vergleichskette
{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}{.}
| Kurs:Vorkurs Mathematik (Osnabrück 2021) | >> |
|---|