Darstellung natürlicher Zahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:45 So 15.10.2006 | | Autor: | gilles |
| Aufgabe | "Jeder kennt die Darstellung natürlicher Zahlen im Dezimalsystem. Mathematisch gesprochen, besitzt jede natürliche Zahl eine Darstellung der Form
[mm] n=\summe_{i=0}^{m}a_{i}\*10^{i}
[/mm]
mit [mm] a_{i}\in\{0,1,...,9\}. [/mm] Diese Darstellung ist (für n>0) eindeutig, wenn man [mm] a_{m}\not=0 [/mm] verlangt. Der Leser möge dies - etwa durch Division mit Rest und vollständige Induktion - wirklich beweisen. Dabei sollte er 10 durch eine beliebige Zahl [mm] d\in\IN_{2} [/mm] ersetzen.
Im Falle d=2 schreibt sich jede natürliche Zahl mit den Ziffern 0 und 1. Man spricht von Binärschreibweise.
Für allgemeine d spricht man von d-adischer Schreibweise. |
Ich bin diese Aufgabe folgendermassen angegangen:
Für eine natürliche Zahl n gibt eine Darstellung der Form
[mm] n=(a_{0}*10^{0}+a_{1}*10^{1}+\cdots)+a_{m}*10^{m}
[/mm]
wobei der Wert in der Klammer für den Rest r steht, also
[mm] n=r+a_{m}*10^{m}.
[/mm]
Nun kann man doch für n+1 schreiben:
[mm] n+1=r+1+a_{m}*10^{m}.
[/mm]
Ab diesem Punkt bin ich nicht mehr so sicher, wie es weitergehen soll. Könnt ihr mir einen Tipp geben?
Vielen Dank und Gruss
gilles
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:18 So 15.10.2006 | | Autor: | ullim |
Hi gilles,
da die Addition von 1 zu einem Übertrag führen kann, wenn es mindestens ein j gibt mit [mm] a_j=9 [/mm] , sind zwei Fälle zu unterscheiden.
1) Es gibt ein j mit [mm] a_j<9
[/mm]
In dem Fall bleibt die Darstellung wie angegeben bestehen.
2) Alle [mm] a_m [/mm] sind 9, dann ist die Darstellung
[mm] n=\summe_{i=0}^{m+1}a_{i}*10^{i} [/mm] mit [mm] a_{m+1}=1
[/mm]
also auch von der gesuchten Form.
mfg ullim
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 11:46 Mo 16.10.2006 | | Autor: | gilles |
Hallo zusammen,
Ich glaube, dann kann man folgendes sagen:
Wenn in [mm] n+1=r+1+a_{m}*10^{m} [/mm] r+1 kleiner als 9 ist, dann ist diese Darstellung für n+1 eindeutig, weil mit n+1 und [mm] 10_{m} [/mm] r und [mm] a_{m} [/mm] eindeutig bestimmt sind, richtig?
Und wenn nun r+1=10 sein sollte, erhält man mit Umformung [mm] (a_{m}+1)*10^{m}. [/mm] Auch hier ist die Darstellung eindeutig, weil auch hier mit [mm] 10^{m} [/mm] und n+1 r (das hier 0 ist) und [mm] a_{m}+1 [/mm] eindeutig defininiert sind, oder?
Was ist nun, wenn [mm] a_{m}+1=10 [/mm] ist? Dann ist doch [mm] 0+1*10^{m+1}, [/mm] was wiederum eine eindeutige Darstellung ist, richtig?
mfg
gilles
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Mi 18.10.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:05 So 15.10.2006 | | Autor: | gilles |
Vielen Dank für die rasche Antwort,
mfg gilles
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:48 Mo 16.10.2006 | | Autor: | felixf |
Hallo!
> "Jeder kennt die Darstellung natürlicher Zahlen im
> Dezimalsystem. Mathematisch gesprochen, besitzt jede
> natürliche Zahl eine Darstellung der Form
>
> [mm]n=\summe_{i=0}^{m}a_{i}\*10^{i}[/mm]
>
> mit [mm]a_{i}\in\{0,1,...,9\}.[/mm] Diese Darstellung ist (für n>0)
> eindeutig, wenn man [mm]a_{m}\not=0[/mm] verlangt. Der Leser möge
> dies - etwa durch Division mit Rest und vollständige
> Induktion - wirklich beweisen. Dabei sollte er 10 durch
> eine beliebige Zahl [mm]d\in\IN_{2}[/mm] ersetzen.
Ich wuerde das wie folgt beweisen: Zur Existenz:
Induktionsvoraussetzung: Die Aussage gilt fuer alle natuerlichen Zahlen $n < [mm] d^m$ [/mm] fuer ein festes $m [mm] \in \IN$.
[/mm]
Induktionsschritt: Sei $n < [mm] d^{m+1}$. [/mm] Schreibe $n = d n' + [mm] a_0$ [/mm] mit $0 [mm] \le a_0 [/mm] < d$. Nun ist $n' < [mm] d^m$, [/mm] womit es eine eindeutige Darstellung $n' = [mm] \sum_{i=0}^{m-1} a_i' d^i$ [/mm] gibt. Mit [mm] $a_i [/mm] := [mm] a_{i-1}'$ [/mm] fuer $1 [mm] \le [/mm] i [mm] \le [/mm] m+1$ gilt also $n = [mm] \sum_{i=0}^m a_i d^i$.
[/mm]
Zur Eindeutigkeit:
Sei $n = [mm] \sum_{i=0}^m a_i d^i [/mm] = [mm] \sum_{j=0}^{m'} a_i' d^i$. [/mm] Durch Fortsetzen der Folgen [mm] $(a_i)_i$ [/mm] und [mm] $(a_i')_i$ [/mm] durch $0$ kann man $n = [mm] \sum_{i=0}^k a_i d^i [/mm] = [mm] \sum_{j=0}^k a_i' d^i$ [/mm] schreiben mit $k [mm] \ge [/mm] m, m'$. Es reicht zu zeigen, dass [mm] $a_i [/mm] = [mm] a_i'$ [/mm] gilt fuer $0 [mm] \le [/mm] i [mm] \le [/mm] k$; dass dann $m = m'$ ist folgt aus der Bedingung [mm] $a_m \neq [/mm] 0 [mm] \neq a_{m'}$.
[/mm]
Dies kann man auch wieder per Induktion beweisen, und zwar, indem man zeigt, dass $n = [mm] (\sum_{i=1}^k a_i d^{i-1}) \cdot [/mm] d + [mm] a_0$ [/mm] die Division von $n$ durch Rest mit $d$ ist; daraus folgt [mm] $a_0 [/mm] = [mm] a_0'$, [/mm] und Anwenden des gleichen Arguments auf die Klammer liefert per Induktion die Eindeutigkeit der anderen Koeffizienten.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:17 Mo 16.10.2006 | | Autor: | gilles |
Hallo,
Ich blicke bei dieser Aufgabe noch nicht ganz durch. Was muss ich nun unter [mm] n=dn^{'}+a_{0} [/mm] im unten stehenden Beweis verstehen?
Gruss
gilles
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:38 Mo 16.10.2006 | | Autor: | felixf |
Hallo gilles!
> Ich blicke bei dieser Aufgabe noch nicht ganz durch. Was
> muss ich nun unter [mm]n=dn^{'}+a_{0}[/mm] im unten stehenden Beweis
> verstehen?
Divison mit Rest von ganzen Zahlen: Du teilst $n$ durch $d$ und erhaelst $n'$ mit Rest [mm] $a_0$.
[/mm]
LG Felix
|
|
|
|
