Kurs:Vorkurs Mathematik (Osnabrück 2014)/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
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir erinnern an einige weitere Begriffe. Man sagt, dass eine ganze Zahl $a$ eine ganze Zahl $b$ \stichwort {teilt} {}
\zusatzklammer {oder dass $a$ ein \stichwort {Teiler} {} von $b$ ist oder dass $b$ ein \stichwort {Vielfaches} {} von $a$ ist} {} {,}
wenn es eine weitere ganze Zahl $c$ mit
\mavergleichskette
{\vergleichskette
{b
}
{ = }{ac
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt. Beispielsweise ist $3$ ein Teiler von $15$, aber $2$ ist kein Teiler von $15$. Eine \stichwort {gerade Zahl} {} ist eine ganze Zahl, die ein Vielfaches von $2$ ist, eine \stichwort {ungerade Zahl} {} ist eine ganze Zahl, die kein Vielfaches von $2$ ist. Wenn $a$ ein Teiler von $b$ ist,
so verwenden wir die Bezeichnung
\mathl{{ \frac{ b }{ a } }}{} für diejenige
\zusatzklammer {eindeutig bestimmte} {} {}
ganze Zahl $c$, für die die Gleichheit
\mavergleichskette
{\vergleichskette
{b
}
{ = }{ac
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
Auf den ganzen Zahlen ist auch 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
\mathl{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
}
{ = }{ 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}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Domen-indukto.gif} }
\end{center}
\bildtext {} }
\bildlizenz { Domen-indukto.gif } {Joachim Mohr} {} {Commons} {CC-by-sa 3.0} {}
Mathematische Aussagen, die von natürlichen Zahlen abhängen, können mit dem Beweisprinzip der \stichwort {vollständigen Induktion} {} bewiesen werden. Die folgende Aussage präzisiert und begründet dieses Prinzip.
\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 {}
}
{
Es sei
\mavergleichskettedisp
{\vergleichskette
{M
}
{ =} { { \left\{ n \in \N \mid A(n) \text{ ist wahr} \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wir wollen zeigen, dass
\mavergleichskette
{\vergleichskette
{M
}
{ = }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, denn genau dies bedeutet, dass die Aussage für alle $n$ gilt. Nach der ersten Bedingung ist
\mavergleichskettedisp
{\vergleichskette
{0
}
{ \in} {M
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Nach der zweiten Voraussetzung gilt für $M$, dass aus
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
stets
\mavergleichskette
{\vergleichskette
{n+1
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt. Damit erfüllt $M$ beide Voraussetzungen im Induktionsprinzip für Mengen, sodass
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
Der Nachweis von
\zusatzklammer {der Gültigkeit 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 {Induktionsschluss} {.} Innerhalb des Induktionsschlusses nennt man die Gültigkeit von
\mathl{A(n)}{} auch 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 alle
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{n_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
durch.
Das folgende Standardbeispiel für einen Induktionsbeweis verwendet das \stichwort {Summenzeichen} {.} 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. Entsprechend ist das \stichwort {Produktzeichen} {} definiert, nämlich
\mavergleichskettedisp
{\vergleichskette
{ \prod_{k = 1}^n a_k
}
{ \defeq} { a_1 \cdot a_2 { \cdots } a_{n-1} \cdot a_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Insbesondere sind für
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die \stichwort {Potenzen} {} durch
\mavergleichskettedisp
{\vergleichskette
{ a^n
}
{ =} { \prod_{i=1}^n a
}
{ =} { a^{n-1} \cdot a
}
{ =} { \underbrace{a \cdot a { \cdots } a}_{n\text{-mal} }
}
{ } {
}
}
{}{}{}
definiert. Dabei gelten die Konventionen
\mavergleichskette
{\vergleichskette
{0 a
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ a^0
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {die erste lässt sich auch über die Multiplikation begründen, die zweite ist aber auch sinnvoll} {} {.}
Als Rechenregeln für das Potenzieren gelten
\aufzaehlungdrei{
\mavergleichskettedisp
{\vergleichskette
{ (a\cdot b)^n
}
{ =} { a^n \cdot b^n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}{
\mavergleichskettedisp
{\vergleichskette
{ a^{n+m}
}
{ =} { a^n \cdot a^m
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}{
\mavergleichskettedisp
{\vergleichskette
{ (a^{n})^m
}
{ =} { a^{n m}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
\inputaufgabeloesung
{
Beweise durch Induktion die folgende Formel für
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\mavergleichskettedisp
{\vergleichskette
{ \sum_{k = 1}^n k
}
{ =} {{ \frac{ n(n+1) }{ 2 } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
{
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
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
sodass 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 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) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
\inputaufgabeloesung
{
Zeige durch vollständige Induktion, dass für jedes
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Zahl
\mathdisp {6^{n+2} + 7^{2n+1}} { }
ein Vielfaches von $43$ ist.
}
{
Induktionsanfang. Für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{6^2+7
}
{ =} {43
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ein Vielfaches von $43$. Induktionsschritt. Es sei nun die Aussage für $n$ bewiesen und betrachten wir den Ausdruck für
\mathl{n+1}{.} Dieser ist
\mavergleichskettealign
{\vergleichskettealign
{ 6^{n+1+2} + 7^{2(n+1)+1}
}
{ =} { 6 \cdot 6^{n+2} + 7^2 \cdot 7^{2n+1}
}
{ =} { 6 \cdot 6^{n+2} + (6+43) 7^{2n+1}
}
{ =} { 6 { \left( 6^{n+2} +7^{2n+1} \right) } + 43 \cdot 7^{2n+1}
}
{ =} { 6 \cdot 43 \cdot s + 43 \cdot 7^{2n+1}
}
}
{
\vergleichskettefortsetzungalign
{ =} { 43 \cdot { \left( 6 \cdot s + 7^{2n+1} \right) }
}
{ } {}
{ } {}
{ } {}
}
{}{,}
wobei im vorletzten Schritt die Induktionsvoraussetzung verwendet wurde
\zusatzklammer {nämlich die Eigenschaft, dass \mathlk{6^{n+2} +7^{2n+1}}{} ein Vielfaches von $43$ ist} {} {.}
Daher ist diese Zahl ein Vielfaches von $43$.
}
\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$, sodass 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.18.}
{}
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 2014) | >> |
|---|