Darstellung natürlicher Zahlen < Analysis < Hochschule < Mathe < Vorhilfe
|
Hallo an Alle!!
Ich soll mir über folg. Gedanken machen:
Gegeben ist die Darstellung [mm] a_{n-1}a_{n-2}...a_{1}a{0_{r}} [/mm] einer natürlichen Zahl zur Basis [mm] r=q^{k} [/mm] mit Ziffern [mm] a_{i}\in Z_{r}={0,1,...,r-1} [/mm] und [mm] a_{n-1}\not= [/mm] 0, wobei [mm] q,k,r\in\IN\{0} [/mm] gilt. Wie sieht die Darstellung
[mm] b_{m-1}b_{m-2}...b_{1}b{0_{q}}
[/mm]
dieser Zahl zur Basis q mit Ziffern [mm] b_{i}\in Z_{q}={0,1,...,r-1} [/mm] und [mm] b_{m}\not= [/mm] 0 aus?
Außerdem soll man sich überlegen, warum [mm] m\le [/mm] nk gilt?
Ich soll da keinen Beweis liefern, die Sache nur irgendwie plausibel machen. Hat da vielleicht jemand ne Idee? Ich habe das schon mit einigen Zahlen durchprobiert und es stimmt, aber warum?
Freue mich über jede Antwort.
VG mathmetzsch
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:46 Do 17.11.2005 | | Autor: | Toellner |
Hallo Daniel,
> wobei
> [mm]q,k,r\in \IN- \{0\}[/mm] gilt.
Ich nehme an q > 1 ?
> Wie sieht die Darstellung
> [mm]b_{m-1}b_{m-2}...b_{1}b{0_{q}}[/mm]
> dieser Zahl zur Basis q mit Ziffern [mm]b_{i}\in Z_{q}={0,1,...,r-1}[/mm]
> und [mm]b_{m}\not=[/mm] 0 aus?
Nicht eher
[mm]b_{i}\in Z_{q}={0,1,...,q-1}[/mm] ?
Gruß, Richard
|
|
|
| |
|
Hallo Richard,
ja doch natürlich, da habe ich mich wohl vertippt.
Und kannst du mir helfen?
VG Daniel
|
|
|
| |
|
Hallo Daniel,
Dank für Deine Mail...
Du untersuchst erstmal die Darstellung der Zahl z zur Basis q:
z = [mm] \summe_{i=0}^{m-1} b_i q^{i}
[/mm]
indem Du sie beginnend mit dem kleinsten Summanden immer in k-Portionen "abgepackt" hinschreibst und für jedes Paket das maximale
[mm] q^{...} [/mm] ausklammerst. Da das i.A nicht glatt aufgeht, führst Du noch führende Potenzen mit Koeffizienten 0 ein, oder hörst bei [(m-1)/k] (= Ganzahlanteil) auf:
z = [mm] \summe_{j=0}^{[(m-1)/k]} (\underbrace{\summe_{i=0}^{k-1}b_{jk+i}*q^{i}}_{= a_j})*q^{kj}
[/mm]
Jetzt ist zu zeigen, dass die angegebenen Summen tatsächlich die [mm] a_j [/mm] sind:
Da innerhalb der Summe die [mm] b_{jk+i} [/mm] alle < q-1 sind kann die Summe maximal (q-1) [mm] \summe_{i=0}^{k-1}q^{i} [/mm] = [mm] q^{k}-1 [/mm] sein. Damit sind die [mm] a_j [/mm] tatsächlich zulässige Ziffern zur Basis [mm] q^{k}, [/mm] und weil sie mit reinen [mm] q^{k}-Potenzen [/mm] multipliziert werden, handelt es sich auch um eine [mm] q^{k}-adische [/mm] Darstellung von z. Die ist eindeutig, also handelt es sich um genau die in der Augabenstellung vorgegebene Darstellung und es gilt n = [(m-1)/k].
Jetzt haben wir mit [mm] a_j [/mm] = [mm] \summe_{i=0}^{k-1}b_{jk+i}*q^{i} [/mm] das Pferd vom Schwanz aufgezäumt, weil die [mm] a_j [/mm] gegeben sind und die [mm] b_{jk+i} [/mm] zu bestimmen. Die Formel zeigt aber, wie es rekursiv geht:
i=0: [mm] b_{jk} [/mm] := [mm] a_j [/mm] mod q.
seien für l < i die [mm] b_{jk+l} [/mm] alle bereits gegeben, dann ist
[mm] b_{jk+ i} [/mm] := [mm] ((a_j [/mm] - [mm] \summe_{l=0}^{i-1}b_{jk+l}*q^{l}) [/mm] mod [mm] q^{i+1})/q^{i}
[/mm]
Gruß, Richard
|
|
|
|
