Beweis jede rationale Zahl lässt sich als endliche oder periodische Dezimalzahl darstellen?
Ich muss den oben genannten Beweis durchführen. Hat jemand eine Lösung oder zumindest den Ansatz für mich?
3 Antworten
Hallo,
vielleicht geht es über einen Widerspruch:
Es gibt eine rationale Zahl, die sich nicht als endlicher oder periodischer Dezimalbruch darstellbar ist.
Wie müßte diese beschaffen sein?
Eine rationale Zahl ist so definiert, daß sie als Bruch zweier ganzer Zahlen m und n darstellbar ist.
Die gesuchte Zahl ist also x=m/n, wobei m und n Element von Z, der Menge der ganzen Zahlen sind.
Dabei müssen m und n teilerfremd sein, ansonsten wäre x=m/n eine ganze Zahl, die als endlicher Dezimalbruch oder periodischer Dezimalbruch darstellbar ist, wie etwa 4/2=2,0=1,p9 (1, Periode 9).
Wenn m>n und n kein Teiler von m, ergibt n/m=a+r/n, wobei a der ganzzahlige Anteil des Ergebnisses und r der Rest ist, wobei auch r Element Z und r<n.
Für diesen Rest gibt es zwei Möglichkeiten: r/n ist ohne Rest teilbar, dann ist m/n als endlicher Dezimalbruch darstellbar - oder r/n ergibt eine Zahl zwischen -1 und 1 plus Rest.
Wenn r/n als unendlicher nichtperiodischer Bruch darstellbar wäre, müßte es eine unendliche Anzahl von möglichen Restzahlen geben.
Als Beispiel diene das schriftliche Dividieren, etwa 10/7
Das ist 1+3/7, also 1, Rest 3.
Nun wird ein Komma gesetzt, dafür an den Rest eine 0 angehängt und der Vorgang des Dividierens beginnt von vorn. Entweder geht die Sache auf oder es bleibt ein neuer Rest, der wieder durch n geteilt wird (hier: n=7).
Da der Rest aber eine ganze, sogar eine natürliche Zahl ist, und da gilt: r<n, gibt es nur eine begrenzte Anzahl von möglichen Restzahlen. Irgendwann muß man bei einem Rest landen, der schon einmal vorgekommen ist. Von diesem Moment aber befindet man sich in einer Schleife - der Bruch wird periodisch.
Ein unendlicher nichtperiodischer Bruch als Ergebnis der Quotienten der beiden ganzen Zahlen m/n würde aber einen unendlichen Vorrat an unterschiedlichen r bei m/n=a+r/n voraussetzen, das ist aber wegen der Voraussetzung r<n und r und n Element Z unmöglich.
In dieser Richtung würde ich über den Beweis nachdenken und sehen, ob er etwas 'mathematischer' zu formulieren ist.
Herzliche Grüße,
Willy
Fixiere eine Basis b ∈ {2; 3; …} wie z. B. b=10.
Triviale Richtung. Jede Basis-b periodische Zahl (terminierende sind mit eingeschlossen—die Zahl endet halt mit …0˙), x, ist in ℚ, da sich die Zahl aufschreiben lässt als
x = s d[N]…d[1]d[0],d[-1]…d[-M](p[T–1]…p[1]p[0])˙
wobei s∈{±1}, N≥0, M ≥ 0, T≥1 und die d[i]’s und p[j]’s in {0; 1; …; b–1} kommen. Diese rechts dargestellte Zahl ist gleich
x = s·(D/bᴹ + ∑ P·b¯ᵏᵀ über k=1 … ∞) = s·(D/bᴹ + P/(bᵀ – 1)),
wobei D = d[-M]b⁰ + … + d[-1]bᴹ¯¹ + d[0]bᴹ + … + d[N]bᴹ⁺ᴺ ∈ IN und P = p[0]b⁰+p[1]b¹ + … + p[T–1]bᵀ¯¹ ∈ IN. Darum ist x s·(D/bᴹ + P/(bᵀ – 1)) in ℚ.
Umkehrschluss. Sei nun x = sp/q ∈ ℚ, wobei s ∈ {±1}, p, q ∈ IN und q > 0. Falls p=0 oder q=1 ist es offensichtlich, dass x eine periodische (tatsächlich terminierende) Darstellung. Wir schauen uns also den nicht trivialen Fall, wenn p > 0 und q > 1.
Defn. Sei r[N]…r[0] die Basis-b Darstellung der nicht negativen Zahl (p–mod(p,q))/q. Setze (p[n], d[n]) eine durch IN indizierte Folge, wie folgt rekursiv definiert:
p[0] := mod(p,q), d[0] := 0.
(♠︎) Angenommen, p[n] ∈ {0; 1; …; q–1} (gilt für n=0), dann setze
d[n+1] := floor(b·p[n]/q) ∈ {0; 1; …; b–1}
p[n+1] := b·p[n]–d[n+1]q = (bp[n]/q – d[n+1])·q = (r–floor(r))q, wobei r=bp[n]/q. Darum gilt p[n+1] ∈ {0; 1; …; q–1}, und (♠︎) bleibt für die ganze Rekursion bestehen.
Betrachte nun die Basis-b Darstellung
s r[N]…r[0], d[1]d[2] …
Behauptung 1. Dies stellt die (rationale) Zahl, x, dar.
Beweis (Beh. 1). Der Vorderteil ist per Wahl eine Darstellung der ganzen Zahl s(p–mod(p,q))/q. Es reicht aus, zu zeigen, dass der Nachkommateil 0, d[1]d[2] … gleich mod(p,q) also gleich p[0]/q ist. Da 0, d[1]d[2] … = ∑ d[k]/bᵏ über k=1…∞ = lim ∑ d[k]/bᵏ über k=1…n, reicht es zu zeigen, dass die partiellen Summen nach p[0] konvergieren. Es reicht hierfür aus zu zeigen, dass (♠︎♠︎) p[0]/q – 1/bⁿ⁺¹ < ∑ d[k]/bᵏ ≤ p[0]/q für die n-te Summe gilt für alle n.
Beobachtung Sei n≥0. Per Konstruktion (siehe oben) gilt b·p[n]/q = r = (r–floor(r))q/q + floor(r) = p[n+1]/q + d[n+1]. Darum gilt (p[n]/q)bⁿ = (p[n+1]/q)bⁿ⁺¹ + d[n+1]/bⁿ⁺¹ und somit d[n+1]/bⁿ⁺¹ = (p[n]/q)bⁿ – (p[n+1]/q)bⁿ⁺¹. Jetzt ist der Trick klar:
∑ d[k]/bᵏ über k=1…n= ∑ (p[k–1]/q)/bᵏ¯¹ – (p[k]/q)/bᵏ über k=1…n
= (p[0]/q)/b⁰ – (p[n+1]/q)/bⁿ⁺¹
= p[0]/q – (p[n+1]/q)/bⁿ⁺¹
und da nun p[n+1] ∈ {0;1;…q–1} erfüllt ∑ d[k]/bᵏ über k=1…n Ungleichung (♠︎♠︎) für alle n ≥ 1.
Also ist s r[N]…r[0], d[1]d[2] … gleich s·((p–mod(p,q))/q + p[0]/q) = s·p/q = x, da p[0] = mod(p,q). QED (Beh. 1)
Behauptung 2. Die Darstellung s r[N]…r[0], d[1]d[2] … ist periodisch. Zusammen mit Behauptung 1 bedeutet dies, dass x eine periodische Darstellung hat.
Beweis (Beh. 2). Es reicht aus zu zeigen, dass ab einem Punkt N≥1, die Folge (d[n]) sich mit einer endlichen Periode T≥1 wiederholt. Beachte, dass in der Folge (p[n], d[n]) gilt p[n]∈{0; 1; …; q–1}, d[n] ∈ {0; 1; …; b–1} und, dass (p[n+1], d[n+1]) komplett durch (p[n], d[n]) bestimmt wird. Da es nur endlich viele möglichen Wert von den (p[n], d[n])’s gibt, nämlich qb viele, existiert ein N≥1 und ein T≥1, so dass (p[N+T],d[N+T]) = (p[N],d[N]).
Sei n≥N. Angenommen, per Induktion gelte (p[n+T],d[n+T]) = (p[n],d[n]). Dann, da (p[n+1+T],d[n+1+T]) komplett durch (p[n+T],d[n+T]) induziert wird, und dies gleich (p[n],d[n]) ist, welches (p[n+1],d[n+1]) induziert, gilt (p[n+1+T],d[n+1+T])=(p[n+1],d[n+1]). Darum gilt per Induktion, dass (p[n+T],d[n+T]) = (p[n],d[n]) für alle n≥N. Also ist s·(r[N]…r[0], d[1]d[2] …) periodisch. QED (Beh. 2)
Man kann auch weiterhin zeigen, das rationale Zahlen nur periodische Darstellungen haben.
Definiere die Abbildung
Ф : t ∈ IR ⟼ frac(bt) ∈ [0, 1)
wobei frac(t) := t – floor(t) der Nachkommaanteil einer Zahl (en. fractional part).
Lemma 1. für alle p, q ∈ IN existiert ein p' ∈ {0; 1; …; q–1}, so dass Ф(p/q) = p'/q.
Beweis. Offensichtlich.
Es folgt, dass für x ∈ ℚ, die Folge (Фⁿ(|x|)) nur endlich viele Werte aufweisen kann. Insbesondere existieren N≥0 und T≥1, so dass Фᴺ⁺ᵀ(|x|) = Фᴺ(|x|).
Lemma 2. Für alle r∈ℚ und N≥0, T≥1, wenn Фᴺ⁺ᵀ(r) = Фᴺ(r), dann gilt (bᵀ–1)bᴺr ∈ ℤ.
Beweis. (bᵀ–1)bᴺr
= (bᵀ–1)Фᴺ(r) + (bᵀ–1)(bᴺr–Фᴺ(r))
= (bᵀФᴺ(r) – Фᴺ(r)) + (bᵀ–1)(bᴺr–Фᴺ(r))
= (bᵀФᴺ(r) – Фᴺ⁺ᵀ(r)) + (bᵀ–1)(bᴺr–Фᴺ(r))
= ∑ bᵏ⁺¹Фᴺ⁺ᵀ¯⁽ᵏ⁺¹⁾(r) – bᵏФᴺ⁺ᵀ¯ᵏ(r) über k=0…T–1
+ (bᵀ–1)·∑ bᵏ⁺¹Фᴺ¯⁽ᵏ⁺¹⁾(r) – bᵏФᴺ¯ᵏ(r) über k=0…N–1
Für k ∈ {0; 1;…; T–1} berechnet man
bᵏ⁺¹Фᴺ⁺ᵀ¯⁽ᵏ⁺¹⁾(r) – bᵏФᴺ⁺ᵀ¯ᵏ(r) = bᵏ(bs – Ф(s)),
wobei s = Фᴺ⁺ᵀ¯⁽ᵏ⁺¹⁾(r). Nun gilt bs – Ф(s) = bs – frac(bs) = floor(bs) ∈ ℤ. Darum ist bᵏ(bs – Ф(s)) ∈ ℤ.
Analog berechnet man für k ∈ {0; 1;…; N–1}, dass bᵏ⁺¹Фᴺ¯⁽ᵏ⁺¹⁾(r) – bᵏФᴺ¯ᵏ(r) = bᵏ(bs – Ф(s)) ∈ ℤ, wobei s := Фᴺ¯⁽ᵏ⁺¹⁾(r). Darum sind die Summanden und somit die o. s. Summen in ℤ. Also (bᵀ–1)bᴺr ∈ ℤ.
QED (Beh. 4)
Es folgt, dass a := (bᵀ–1)bᴺ|x| ∈ IN. Schreibe a als k·(bᵀ–1) + j, wobei k, j ∈ IN und j<(bᵀ–1). Dann gilt
x = s|x| = s(r + j/(bᵀ–1))/bᴺ,
wobei s ∈ {±1} je nach Vorzeichen von x. Da r≥0 eine ganze Zahl ist, existiert eine Basis-b Darstellung r[n]…r[1]r[0] für r und ein n≥0. Da 0≤j<bᵀ<bᵀ–1 und j ganzzahlig ist, existiert eine Basis-b Darstellung der Länge T von j, nämlich j[T–1]…j[1]j[0]. Es ist einfach zu zeigen, dass
r + j/(bᵀ–1) = r[n]…r[1]r[0],(j[T–1]…j[1]j[0])˙
D. h. r + j/(bᵀ–1) hat eine periodische Darstellung. Für den Ausdruck x = s·(r + j/(bᵀ–1))/bᴺ muss man die o. s. Basis-b Darstellung lediglich nach rechts um N Stellen verschieben und mit dem Vorzeichen s ausstatten. Dies bleibt eine periodische Basis-b Darstellung.
Also hat jedes x∈ℚ eine periodische Basis-b Darstellung.
Siehe auch Satz 1-15 (samt den 3 vorangehenden Lemmata) in §1·3 in dem auf meinem Profil verlinkten Dokument.
Eine Beweisskizze anhand eines Beispiels, etwa x = 5 / 26
Zunächst ist 26 = 2 * 13. Entscheidend ist, im Nenner die Zweien und Fünfen abzuspalten, denn diese führen trivialerweise zu abbrechenden Dezimalbrüchen. Man hat also
x = 5 / 26 = 5 / (2 * 13), also
2x = 5 / 13.
Nun nehmen wir die Zehnerpotenzen, 10^1 = 10, 10^2=100 und dividieren dies durch die Zahl 13 und schauen uns den Rest an. Keine der Zahlen ist durch 13 teilbar, denn durch das Abspalten der 2en und 5en sind diese Zehnerpotenzen alle teilerfremd zu 13. Es gibt nur 12 verschiedene Reste also bei Division durch 13, von Rest 1 bis Rest 12. Irgendwann lässt also eine Zahl 10^t bei Divison durch 13 auch den Rest 1 (dies müsste man auch noch beweisen, ist nicht schwierig, lasse ich aber jetzt gerade weg), und so kommt man zur Lösung.
Am Beispiel von oben. Wenn man 10^1, 10^2, 10^3 usw. durchprobiert, lassen sie alle einen anderen Rest als 1 bei Division durch 13, erst 10^6 = 1000000 lässt den Rest 1, denn es ist 1000000 - 1 = 13 * 76923, also haben wir
999999 = 13 * 76923. Damit gilt
2x = 5 / 13, also
2x = 5 * 76923 / 999999, also
2x = 384615 / 999999, das heißt
x = 1/2 * 384615 / 999999
x= 1/10 * 5 * 384615 / 999999
x= 1/10 * (1923075 / 999999) = 1/10 * ( 1 + 923076 / 999999) und damit
x = 1/10 * (1 + 0,Periode923076)
x= 0,1Periode923076
Dieses Verfahren symbolisiert das allgemein Beweisverfahren