Beweis zu b-adischem periodischem Bruch

20.03.2021, 15:31

wunder-chris

Beweis zu b-adischem periodischem Bruch

Meine Frage:
Ein b-adischer Bruch
$\begin{eqnarray*} a_{-k}...a_0.a_1a_2a_3a_4... \end{eqnarray*}$

heißt periodisch wenn es natürliche Zahlen $\begin{eqnarray*} r,s \geq 1 \end{eqnarray*}$ gibt, so dass
$\begin{eqnarray*} a_{n+s} = a_n \end{eqnarray*}$ für alle $\begin{eqnarray*} n \geq r \end{eqnarray*}$ .

Zu Zeigen:
ein b-adischer Bruch ist genau dann periodisch, wenn er eine rationale Zahl darstellt.

Meine Ideen zur Hinrichtung habe ich notiert, das wurde auch schon ähnlich in einem anderen Beitrag behandelt. Aber wurde nicht der Grund genannt, wieso die Zahl nun rational sein muss.

Der andere Teil fiel mir dann schwerer. Meine Kernfrage ist:

Gegeben eine rationale Zahl:
Wie kann ich zeigen, dass ein r existiert, ab dem alle Glieder bis zu einem natürlichen Index s sich immer wieder wiederholen?

Meine Ideen:
Für die Hinrichtung ( Big Laugh

) habe ich angenommen, der Bruch sei periodisch und
die Darstellung von für ein x (ich darf es nicht als rational annehmen, dann als reell oder gar nichts?) geschrieben als:

$\begin{eqnarray*} \sum_{\mu=-k}^0 a_{\mu}*b^{-\mu} + \sum_{\mu=1}^{r-1} a_{\mu}*b^{-\mu} + \sum_{j=0}^{\infty} (a_{r+j*s}*b^{-r-j*s} + ... + a_{r+s+j*s}*b^{-r-s-j*s}) \end{eqnarray*}$

bzw.
$\begin{eqnarray*} \sum_{\mu=-k}^0 a_{\mu}*b^{-\mu} + \sum_{\mu=1}^{r-1} a_{\mu}*b^{-\mu} + \sum_{j=0}^{\infty} \sum_{k=r}^{r+s} a_{k+j*s}*b^{-k-j*s} \end{eqnarray*}$

Jetzt habe ich $\begin{eqnarray*} a_{k} = a_{k+j*s} \end{eqnarray*}$ für alle $\begin{eqnarray*} k = r,..,r+s \end{eqnarray*}$ gesetzt und.

$\begin{eqnarray*} \sum_{\mu=-k}^0 a_{\mu}*b^{-\mu} + \sum_{\mu=1}^{r-1} a_{\mu}*b^{-\mu} + \sum_{j=0}^{\infty} \sum_{k=r}^{r+s} a_{k+s}*b^{-k-j*s} \end{eqnarray*}$

Jetzt betrachte ich nur die letzte Summe und klammere die Summe mit $\begin{eqnarray*} a_{k+s}, b^{-k} \end{eqnarray*}$ aus.

$\begin{eqnarray*} \sum_{k=r}^{r+s} a_{k+s}*b^{-k} \sum_{j=0}^{\infty} b^{-j*s} \end{eqnarray*}$

und erhalte mit $\begin{eqnarray*} b^{-j*s} = b^{{-s}^{j}} \end{eqnarray*}$ den Grenzwert
$\begin{eqnarray*} \frac{1}{1-b^{-s}} = \frac{b^{s}}{b^{s}-1} \end{eqnarray*}$

Kann ich jetzt sagen, dass die Darstellung
$\begin{eqnarray*} \sum_{\mu=-k}^0 \frac{a_{\mu}}{b^{\mu}} + \sum_{\mu=1}^{r-1} \frac{a_{\mu}}{b^{\mu}} + \frac{b^{s}}{b^{s}-1} \sum_{k=r}^{r+s} \frac{a_{k+s}}{b^{k}} \end{eqnarray*}$

Ein rationale Zahl ist, da die Summanden alle rational ist und die Summe endlich?

Bei der Rückrichtung hatte ich Schwierigkeiten.

Sei z \in $\begin{eqnarray*} \mathbb{Q} \end{eqnarray*}$ eine rationale Zahl, also $\begin{eqnarray*} z=\frac{n}{m} \end{eqnarray*}$ mit $\begin{eqnarray*} n,m \in \mathbb{Q} \end{eqnarray*}$ .

Ich hab versucht z als 0<z<1 anzunehmen oder z darzustellen als $\begin{eqnarray*} z = q + \frac{r}{n} \end{eqnarray*}$ wobei ich dann q als den Teil entwickle der vor dem Komma steht und $\begin{eqnarray*} \frac{r}{n} \end{eqnarray*}$ als den letzteren Teil, aber da müsste ich ja jetzt wieder trennen zwischen dem nicht periodischen und dem periodischen Teil.

Wie kann ich zeigen, dass ein r existiert, ab dem alle Glieder bis zu einem natürlichen Index s sich immer wieder wiederholen?

20.03.2021, 17:48

Elvis

Auf diesen Beitrag antworten »

Die Rückrichtung ist besonders einfach, wenn man schriftlich dividieren kann. Bei der Division durch m können nur m verschiedene Reste auftreten, also kann die Vorperiode r und die Periodenlänge s nicht größer als m sein.

22.03.2021, 23:05

wunder-chris

Auf diesen Beitrag antworten »

Also ich verstehe, dass bei der Division durch m nur m verschiedene Reste auftreten, aber wie schließt du nun genau auf r und s?

Ich habs mir jetzt noch mithilfe des Algorithmus für die Dezimalentwicklung erklärt:
$\begin{eqnarray*} y_k = \frac{r}{m}*b \end{eqnarray*}$ ist kleiner als b. Den Koeffizienten der b-adischen Darstellung erhalte ich nun über die Rundung von y_k nach unten. $\begin{eqnarray*} a_k = floor(y_k) \end{eqnarray*}$ Im Anschluss berechne ich das nächste y über
$\begin{eqnarray*} y_{k+1} = (y_k - a_k)*b \end{eqnarray*}$ das wiederum kleiner b ist. Und da y_k rational ist, gibt es endlich viele Möglichkeiten für y_k kleiner als b. Damit muss y_k sich wiederholen und somit auch a_k
Das ist noch nicht ganz so griffig für mich, aber fast.

Undohne diesen Rückgriff auf den Algorithmus, wie schlussfolgerst du aus dem Rest die Periodizität?

23.03.2021, 08:52

Elvis

Auf diesen Beitrag antworten »

Das ist eine gute Frage. Am Beispiel der Division n/m im Dezimalsystem (b=10) erkenne ich, dass nicht mehr als m verschiedene Reste auftreten können und deswegen s und r nicht groesser als m sein können. Für einen rigorosen Beweis schreibe ich die schriftliche Division im b-adischen Zahlsystem als Euklidischen Algorithmus und argumentiere mit den dabei auftretenden Resten.
Oder z. B. so:
50:7=7 Rest 1
10:7=1 Rest 3
30:7=4 Rest 2
20:7=2 Rest 6
60:7=8 Rest 4
40:7=5 Rest 5
50:7=7 Rest 1
Also ist $\begin{eqnarray*} \frac 5 7=0,\overline {714285} \end{eqnarray*}$ mit s=0,r=6<7

23.03.2021, 09:37

HAL 9000

Auf diesen Beitrag antworten »

Zur Frage: Welche Periodenlänge hat ein Bruch $\begin{eqnarray*} \frac{p}{q} \end{eqnarray*}$ im $\begin{eqnarray*} b \end{eqnarray*}$ -adischen System?

Zunächst mal können wir getrost von teilerfremden $\begin{eqnarray*} p,q \end{eqnarray*}$ ausgehen. Weiterhin ist es ausreichend, auch nur teilerfremde $\begin{eqnarray*} q,b \end{eqnarray*}$ zu betrachten:

Zu diesem Zwecke verschiebt man das Komma so weit nach rechts (d.h. multipliziert den Bruch mit einer geeignet großen Potenz von $\begin{eqnarray*} b \end{eqnarray*}$ ), so dass sämtliche Primfaktoren von $\begin{eqnarray*} b \end{eqnarray*}$ durch Kürzen aus $\begin{eqnarray*} q \end{eqnarray*}$ verschwunden sind. Bleibt dann $\begin{eqnarray*} q=1 \end{eqnarray*}$ übrig, so ist die $\begin{eqnarray*} b \end{eqnarray*}$ -adische Bruchentwicklung endlich. Wir gehen im folgenden vom gegenteiligen Fall $\begin{eqnarray*} q>1 \end{eqnarray*}$ aus.

Und nun greift der Satz von Euler-Fermat: Gemäß dem ist $\begin{eqnarray*} b^{\varphi(q)}\equiv 1\bmod q \end{eqnarray*}$ , d.h., es gibt ein $\begin{eqnarray*} u \end{eqnarray*}$ mit $\begin{eqnarray*} b^{\varphi(q)}-1 = qu \end{eqnarray*}$ und es ist somit

$\begin{eqnarray*} \frac{p}{q} = \frac{pu}{b^{\varphi(q)}-1} = pu\sum_{k=1}^{\infty} b^{-k\varphi(q)} \end{eqnarray*}$ .

Damit besitzt $\begin{eqnarray*} \frac{p}{q} \end{eqnarray*}$ die Periodenlänge $\begin{eqnarray*} \varphi(q) \end{eqnarray*}$ , was wiederum bedeutet, dass die kleinste Periodenlänge von $\begin{eqnarray*} \frac{p}{q} \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} \varphi(q) \end{eqnarray*}$ ist.

Algebraisch ausgedrückt ist diese kleinste Periodenlänge die Ordnung von $\begin{eqnarray*} b \end{eqnarray*}$ in $\begin{eqnarray*} \left(\mathbb{Z}/q\mathbb{Z}\right)^* \end{eqnarray*}$ .

Beispiele:

$\begin{eqnarray*} b=10,q=7 \end{eqnarray*}$ , da ist die kleinste Periodenlänge sogar genau gleich $\begin{eqnarray*} \varphi(7)=6 \end{eqnarray*}$ .

Bei $\begin{eqnarray*} b=10,q=13 \end{eqnarray*}$ mit $\begin{eqnarray*} \frac{1}{13} = 0{,}\overline{076923} \end{eqnarray*}$ ist die kleinste Periodenlänge ebenfalls 6, diesmal also ein echter Teiler von $\begin{eqnarray*} \varphi(13)=12 \end{eqnarray*}$ .

P.S.: Genauer drüber nachgedacht kann man in den obigen Betrachtungen $\begin{eqnarray*} \varphi \end{eqnarray*}$ durch die Carmichaelfunktion $\begin{eqnarray*} \lambda \end{eqnarray*}$ ersetzen, das macht die Aussage für zusammengesetzte $\begin{eqnarray*} q \end{eqnarray*}$ etwas schärfer.

08.04.2021, 11:33

wunder-chris

Auf diesen Beitrag antworten »

RE: Beweis zu b-adischem periodischem Bruch
@Elvis

Zitat:

Am Beispiel der Division n/m im Dezimalsystem (b=10) erkenne ich, dass nicht mehr als m verschiedene Reste auftreten können...

Das Beispiel habe ich gut verstanden danke!

@HAL 9000

Es hat etwas gedauert bei mir, leider habe ich noch nicht alles ganz verstanden.

Also Zu deiner ersten Argumentation wir kürzen alle Primfaktoren die b teilen aus q raus.
Wenn ich das mit dem Algorithmus zur Bestimmung der Ziffern mache bekomme ich ja
$\begin{eqnarray*} y_1 = \frac{p}{q}*b \end{eqnarray*}$
Wenn sich b und q rauskürzen bekomme ich
$\begin{eqnarray*} \frac{p}{q}*b = p*b' = c \end{eqnarray*}$
Also irgendeine ganze Zahl c, sodass dann alle folgenden Vorfaktoren 0 werden und der Bruch sich allein
mit 0,c0000.. schreiben lässt.
Wir betrachten nicht diesen Fall und wir betrachten auch nicht die Fälle, wo das nach endlich vielen Schritten auftritt, also 0,abcdefgh00000...

Also nehmen wir ein q das nicht b teilt. Ich hatte es nicht komplett verstanden und hab als beispiel folgendes gemacht:
$\begin{eqnarray*} \frac{7}{18} = \frac{7}{2*3^{2}} \end{eqnarray*}$
$\begin{eqnarray*} \frac{7}{2*3^{2}}*10 = \frac{7}{2*3^{2}}*2*5 = \frac{7}{3^{2}}*5= \frac{35}{9} \end{eqnarray*}$

Dann gilt $\begin{eqnarray*} 10^{9-1} \equiv_p 1 \end{eqnarray*}$
So ist das gemeint oder? Also gilt der Satz von Fermat hier obwohl 9 keine Primzahl ist.

So weit so gut, dann setzen wir die Darstellung von q in unser ursprüngliche Zahl ein und erhalten
$\begin{eqnarray*} \frac{p}{q} = \frac{pu}{b^{\phi(q)}-1} = \sum_{k=1}^{n} {(b^{-\phi(q)}})^{k} \end{eqnarray*}$
Ich hab jetzt mal hier noch die Umformung der Reihe aufgeschrieben, damit mir da kein Fehler unterlaufen ist:
$\begin{eqnarray*} \frac{p}{q} = \frac{pu}{b^{\phi(q)}-1} = pu*\frac{b^{-\phi(q)}}{1-b^{-\phi(q)}}= pu*b^{-\phi(q)}*\sum_{k=0}^{n} {(b^{-\phi(q)}})^{k} = pu*b^{-\phi(q)}*\sum_{k=1}^{n} {(b^{-\phi(q)}})^{k-1}= pu*b^{-\phi(q)}*\sum_{k=1}^{n} {(b^{-\phi(q)}})^{k}*b^{\phi(q)}=pu*\sum_{k=1}^{n} {(b^{-\phi(q)}})^{k} \end{eqnarray*}$
So hab ichs gemacht.

Also jetzt interpretierst du den Ausdruck als b-adische Entwicklung und sagt die Periodenlänge ist $\begin{eqnarray*} \phi(q) \end{eqnarray*}$ . Mit Länge ist dann die Anzahl der Ziffern gemeint, aber irgendwie hab ich den Sprung nicht mitbekommen.
Also in der Darstellung $\begin{eqnarray*} pu*\sum_{k=1}^{\infty} {(b^{\phi(q)}}){(b^{-k}}) \end{eqnarray*}$ ist der Vorfaktor immer konstant aber ist der überhaupt noch kleiner als b? Nein, das ist nicht relevant du behauptest das phi(q) die Anzahl der Ziffern darstellt. Wie kommt man darauf?
Also es stimmt offensichtlich in deinen Beispielen, aber ich verstehe nicht ganz wieso.

Tut mir leid, ich musste erstmal den Beweisweg nachvollziehen, leider habe ich etwas aus den Augen verloren was speziell dann die Umformung der rationalen Zahl aussagen soll.

Die Carmichaelfunktion ist mir leider völlig unbekannt Big Laugh

08.04.2021, 11:40

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von wunder-chris
Also gilt der Satz von Fermat hier obwohl 9 keine Primzahl ist.

Nicht der Satz von Fermat, sondern der Satz von Euler-Fermat:

$\begin{eqnarray*} b^{\varphi(q)} \equiv 1\bmod q \end{eqnarray*}$ unter der Voraussetzung $\begin{eqnarray*} \operatorname{ggT}(b,q)=1 \end{eqnarray*}$

Im Fall $\begin{eqnarray*} q=9,b=10 \end{eqnarray*}$ also $\begin{eqnarray*} 10^6\equiv 1\bmod 9 \end{eqnarray*}$ .

Wobei das ein wenig anschauliches Beispiel ist, da hier ja bereits $\begin{eqnarray*} 10^1\equiv 1\bmod 9 \end{eqnarray*}$ gilt.

P.S.: Hab jetzt den Rest deines Beitrags durchgelesen. Offenbar weißt du überhaupt nicht, was mit $\begin{eqnarray*} \varphi \end{eqnarray*}$ gemeint ist. Ohne die wird es natürlich schwierig, die Sache zu erklären. Und bevor du die kennst, hat es erst recht keinen Zweck, dass du dich mit der Carmichaelfunktion (steht in Wiki) befasst.

Zitat:

Original von wunder-chris
Also jetzt interpretierst du den Ausdruck als b-adische Entwicklung und sagt die Periodenlänge ist $\begin{eqnarray*} \varphi(q) \end{eqnarray*}$ .

Gemeint ist: Eine Periodenlänge ist $\begin{eqnarray*} \varphi(q) \end{eqnarray*}$ .

Es muss nicht die kürzeste Periodenlänge sein - von der wissen wir nach diesen Überlegungen nur, dass sie ein Teiler von $\begin{eqnarray*} \varphi(q) \end{eqnarray*}$ ist. Hab ich eigentlich alles oben schon geschrieben, aber manche brauchen wohl mehrere Wiederholungen, bis es durchdringt...

Das Beispiel $\begin{eqnarray*} q=9 \end{eqnarray*}$ zeigt es deutlich: $\begin{eqnarray*} \varphi(9)=6 \end{eqnarray*}$ ist eine Periodenlänge, aber gewiss nicht die kürzeste - denn die ist hier schlicht 1.

Generell brauchst du diese detaillierte Diskussion zur Periodenlänge nicht wirklich zur Bewältigung dieser Aufgabe, dazu reicht die Idee von Elvis vollkommen aus. Ich hab das nur als Zusatzinformation zur Vertiefung dieser Problemstellung angebracht - also verzettele dich nicht darin, wenn dir die wichtigen Grundlagen dazu fehlen.

08.04.2021, 12:06

wunder-chris

Auf diesen Beitrag antworten »

Zitat:

P.S.: Hab jetzt den Rest deines Beitrags durchgelesen. Offenbar weißt du überhaupt nicht, was mit Æ gemeint ist. Ohne die wird es natürlich schwierig, die Sache zu erklären. Und bevor du die kennst, hat es erst recht keinen Zweck, dass du dich mit der Carmichaelfunktion (steht in Wiki) befasst.

Allerdings, da hatte ich naiverweise angenommen, das sei einfach q-1.

Zitat:

Generell brauchst du diese detaillierte Diskussion zur Periodenlänge nicht wirklich zur Bewältigung dieser Aufgabe, dazu reicht die Idee von Elvis vollkommen aus. Ich hab das nur als Zusatzinformation zur Vertiefung dieser Problemstellung angebracht - also verzettele dich nicht darin, wenn dir die wichtigen Grundlagen dazu fehlen.

Ok, trotzdem danke für die ausführliche Darstellung, ich komme noch einmal darauf zurück wenn ich weiter bin.

Neue Frage »

Antworten »

Beweis zu b-adischem periodischem Bruch

Verwandte Themen