Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Maximale Periode

Maximale Periode

Universität / Fachhochschule

Tags: Zahlentheorie

Sukomaki aktiv_icon

19:52 Uhr, 23.12.2017

Hallo, ich habe mir gerade das Buch "Mathematische Leckerbissen -
über 150 ungelöste Probleme" von C. Stanley Ogilvy gekauft. Unter
anderem ist darin das Problem der maximalen Periode zu finden. Dabei
geht es darum, für eine Primzahl

p

zu entscheiden, ob

\frac{1}{p}

im Zehner-System
eine maximale Periode hat, also deren Nachkommastellen eine Periode
der Länge

p - 1

haben.

Ich habe das Problem mal derart verallgemeinert, dass ich beliebige Zahlen-
Systeme betrachte. Bis jetzt habe ich herausgefunden (wenn ich mich nicht
vertue), dass für ein System Z, das eine Quadratzahl ist (z.B. das Vierer-System),
keine maximale Periode für

p > 2

existiert.

Hat jemand eine Idee, in welche Richtung ich nach einem Beweis suchen muss?

Gruß
Maki

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

anonymous

23:42 Uhr, 23.12.2017

Hallo
Überleg dir mal, welchen Rest die Ganzzahldivision

\frac{1}{p}

haben kann...

Sukomaki aktiv_icon

09:56 Uhr, 24.12.2017

Kannst Du das bitte etwas konkretisieren?
Ich verstehe das nicht so ganz.

1/7 ist z.B. Null Rest 1.
Und beim Divisionsverfahren können alle
Reste 1 bis p-1 auftreten, bevor sich
die Reste wiederholen.

Und meine Frage nach einem Beweis bezog
sich nur darauf, dass es in einem Quadrat-
Zahlensystem keine maximale Periode für
P größer Zwei gibt.

anonymous

10:27 Uhr, 24.12.2017

Hallo
Du hast anscheinend mir deine Fragestellung noch nicht recht klar gemacht.

a)

Dass wir uns recht verstehen: Was ist eine Quadratzahl?
Ich ahne:

> 4

ist eine Quadratzahl, denn

4 = 2^{2}

> 9

ist eine Quadratzahl, denn

9 = 3^{2}

> 16

ist eine Quadratzahl, denn

16 = 4^{2}

> 25

ist eine Quadratzahl, denn

25 = 5^{2}

b)

Du behauptest, dass für ein Zahlensystem, das eine Quadratzahl als Basis besitzt, keine Periode exisiert.

Na ja, also ich habe mal das Beispiel gewählt:

p = 7

im (von dir benannten) Vierer-ZahlenSystem:

\frac{1}{7} = \frac{1}{{(13)}_{4}} = {[0.0210210210210210210 ...]}_{4}

D . h

. die Periode betägt

3,

denn die drei Ziffern "210" wiederholen sich ständig.
??

Sukomaki aktiv_icon

10:59 Uhr, 24.12.2017

-> Du behauptest, dass für ein Zahlensystem, das eine Quadratzahl als Basis besitzt,
keine Periode exisiert.

Nein, was ich behaupte ist, dass für ein Zahlensystem, das eine Quadratzahl als
Basis besitzt, keine maximale Periode existiert.

\frac{1}{(13)_{4}}

hat nur eine Periode der Länge drei. Für eine maximale Periode müsste
die Nachkommastellenentwicklung die Länge sechs haben.

anonymous

11:07 Uhr, 24.12.2017

Lass es mich mal in meine Worte fassen...

Ich ahne, deine Behauptung wollte lauten:
In einem Zahlensystem, das eine Quadratzahl als Basis besitzt, wird die Periode stets kleiner als

(p - 1)

sein.

anonymous

12:29 Uhr, 24.12.2017

Meine wilde Probiererei mit dem Computer ergab bisher folgendes Bild, bzw. These:
In einem Zahlensystem, das eine Quadratzahl als Basis besitzt, wird die Periode der Kommadarstellung von

\frac{1}{p}

eine Periode

\frac{p - 1}{2}

aufweisen, oder ein Teiler hiervon.

So richtig in die Theorie dahinter habe ich mich noch nicht weiter eingedacht. Aber es mag schon sein, dass dieses "1/2" damit zusammenhängt, dass wir von Quadratzahlen

n^{2}

für die Basis ausgehen.

Sukomaki aktiv_icon

23:34 Uhr, 24.12.2017

-> Meine wilde Probiererei mit dem Computer ergab bisher folgendes Bild, bzw. These:
-> In einem Zahlensystem, das eine Quadratzahl als Basis besitzt, wird die Periode der
-> Kommadarstellung von

\frac{1}{p}

eine Periode

\frac{p - 1}{2}

aufweisen, oder ein
-> Teiler hiervon

Ich komme zu demselben Schluß.

In welcher Sprache programmierst Du (C++, MAPLE, Mathematika, ...)?

anonymous

13:40 Uhr, 25.12.2017

Dürfen wir das als Bestätigung der Fragestellung verstehen?

PS: Ich habe einfach ein Tabellenkalkulationsprogramm genutzt.

Sukomaki aktiv_icon

19:26 Uhr, 25.12.2017

Mir scheint, wir sind auf dem richtigen Weg :-)

Der von Dir gefundene Zusammenhang gilt sogar allgemeiner :

In einem beliebigen Zahlensystem wird die Periode der Kommadarstellung
von

\frac{1}{p}

- falls sie nicht abbricht - eine Länge aufweisen, die einem Teiler von

p - 1

entspricht.

Desweiteren habe ich entdeckt :
Sei Z eine Quadratzahl als Basis,

p > 2

eine Primzahl und

L_{p}

die Länge
der Periode von

\frac{1}{p} \Rightarrow \frac{p - 1}{L_{p}}

ist eine gerade Zahl (wenn die Kommadarstellung
von

\frac{1}{p}

nicht abbricht).

Gruß
Maki

michaL aktiv_icon

21:26 Uhr, 25.12.2017

Hallo,

zunächst noch fröhliche Weihnachten.

Viele Zusammenhänge sind schon bekannt.
Ich nenne einfach mal mal die Basis des Zahlensystems

g

(

g

-adische Brüche) und

L_{g} (p)

die Länge der Periode von

\frac{1}{p}

als

g

-adischen Bruch.

Klar ist, dass für Primzahlen

p

gilt:

1 \leq L_{g} (p) \leq p - 1

Selbst bei abbrechenden Brüchen kann ich eine Periode erzwingen:

\frac{1}{10} = 0, 1_{10} = 0, 0 {\overline{9}}_{10}

Ein schon bekannter Zusammenhang zur Gruppentheorie ist folgender:

L_{g} p = ord (g)

, wobei die Gruppe

(ℤ_{p}^{*}, \cdot, 1,^{- 1})

die zugrunde liegende Gruppe ist.

Mit diesem Zusammenhang kann an die obige Ungleichung erklären. Weiter folgt damit sogar die Teilereigenschaft, auf die kreadoor anspielt.

Klar ist:

L_{g^{2}} (p) = ord (g^{2}) = \frac{1}{2} ord (g) = \frac{1}{2} L_{g} (p)

Daraus folgt schon, dass bei Quadraten als Zahlsystembasis eine maximale Periodenlänge nicht erreicht werden kann. Analog schließt man für alle anderen Potenzen, die NICHT Vielfache von

p - 1

sind. Man beachte

g^{p} \equiv g

mod

p

.

Reicht das als Hinweis?

Mfg Michael

Sukomaki aktiv_icon

00:51 Uhr, 26.12.2017

Hallo,
Dir auch fröhliche Weihnachten.

-> Selbst bei abbrechenden Brüchen kann ich eine Periode erzwingen:

\frac{1}{10} = 0, 1_{10} = 0, 0 {\bar{9}}_{10}

Clever. Da habe ich nicht dran gedacht.

-> Ein schon bekannter Zusammenhang zur Gruppentheorie ist folgender :

L_{g} (p) = o r d (g)

Den Beweis dafür würde ich gerne sehen. Ist der lang oder kompliziert?

Die Ordnung eines Gruppenelementes ist definiert durch :

o r d (g) = min ({n \in ℕ ∣ g^{n} = e} \cup {\infty})

Was ist, wenn die Basis größer gleich ist als die Primzahl? Dann ist

g

doch nicht Bestandteil der Gruppe

(ℤ_{p}^{*}, \cdot, 1,^{- 1})

. Rechne ich dann einfach

o r d (g m o d p)

?

Und wenn

g = p

: Dann ist doch

g^{n}

nie

e

?

Die Teiler-Eigenschaft

L_{g} (p) ∣ p - 1

kommt daher, dass

\forall g \in G : o r d (g) ∣ ∣ G ∣

, stimmt's?

-> Klar ist:

L_{g^{2}} (p) = o r d (g^{2}) = \frac{1}{2} o r d (g) = \frac{1}{2} L_{g} (p)

Cool, das erklärt meine Vermutung.

Anscheinend hat sich in den 55 Jahren - seit das Buch von Herrn
C. Stanley Ogilvy erschienen ist - einiges getan.

Weisst Du auch etwas über asymptotische Dichte, bzw. Verteilung der
maximalen Periode oder ist das etwa noch ungelöst?

Und ja : das reicht erst mal als Hinweis. Du hast mir gut weiter geholfen.

Gruß
Maki

michaL aktiv_icon

10:53 Uhr, 26.12.2017

Hallo,

> -> Ein schon bekannter Zusammenhang zur Gruppentheorie ist folgender : Lg(p)=ord(g)
> Den Beweis dafür würde ich gerne sehen. Ist der lang oder kompliziert?

Weder lang, noch kompliziert. Eher ein genaues Hinschauen bei der schriftlichen Division.

Was passiert denn, wenn man 1 durch

p

g

-adischen System teilt?

Sieht ja erst einmal so aus:

\begin{array}{ccccc} 1 & \div & p & = & 0, \dots \\ 0 \\ 10 \\ ⋱ \end{array}

Offenbar hängt man immer eine Null an, was aber nichts anderes bedeutet, als dass man mit

g

multipliziert (

g

-adisches System!). Dann wird der Rest modulo

p

bestimmt.
Aufgrund von

(a mod p) \cdot (b mod p) = (a b) mod p

, bildet man also nur Potenzen von

g

mod

p

. Die Periode ist genau dann einmal erreicht, wenn

g^{n} \equiv 1

mod

p

. (Ein anderer Rest statt 1 kann nicht als erstes wieder auftreten. Denn: Wäre

1 \equiv / g^{n + k} \equiv g^{n}

mod

p

, so wär schon

g^{k} \equiv 1

mod

p

. Im Zusammenhang mit dem KLEINSTEN Exponenten, lässt sich daraus ein Widerspruch herleiten.)

Was haben wir also? Wir bilden Potenzen

g^{n}

mod

p

und wollen denjenigen kleinsten Exponenten

n_{0}

, sodass

g^{n_{0}} \equiv 1

mod

p

, also die Ordnung

ord (g)

mod

p

bestimmen.

> Was ist, wenn die Basis größer gleich ist als die Primzahl? Dann ist g doch nicht Bestandteil der Gruppe
> (ℤp∗,⋅,1,−1). Rechne ich dann einfach ord(gmodp)?

Genau. Mod

p

sind die beiden Elemente gleich.

> Und wenn g=p : Dann ist doch gn nie e?

Korrekt. (Es reicht auch schon

g ∣ p

oder noch allgemeiner

ggT (g, p) > 1

.)
Falls

g = p

gilt, so ist

p = 1 0_{g}

die

g

-adische Darstellung. Damit ist

\frac{1}{p} = \frac{1}{g} = 0, 1_{g} = 0, 0 {\overline{9}}_{g}

, wie schon oben erwähnt.

> Die Teiler-Eigenschaft Lg(p)∣p−1 kommt daher, dass ∀g∈G:ord(g)∣∣G∣, stimmt's?

Genau.

> Anscheinend hat sich in den 55 Jahren - seit das Buch von Herrn C. Stanley Ogilvy erschienen ist - einiges
> getan.

Dazu kann ich nichts genaueres sagen. Ich vermute, dass das Problem nicht darin besteht, diese Zusammenhänge zu finden. Es ist aber letztlich auch mit diesem Zusammenhang immer noch das gleiche, die Periodenlänge händisch auszurechnen. Nur de Art und Weise, es aufzuschreiben, ist leicht anders. Die Rechnungen sind die gleichen. Ich habe ein Zahlentheoriebuch hier (Bundschuh, Einführung in die Zahlentheorie, Springer-Verlag), in dem zwar die Zusammenhänge ebenfalls angedeutet sind (soweit ich das richtig überflogen habe), aber keine weiter führende Theorie dazu gezeigt wird. Es scheint, als sei das Problem also immer noch ungelöst.

> Weisst Du auch etwas über asymptotische Dichte, bzw. Verteilung der maximalen Periode oder ist das etwa noch
> ungelöst?

Davon weiß ich nichts. Dass ich ein Buch (s.o.) zum Nachschauen habe, ist eher Zufall. Den Zusammenhang mit der Ordnung habe ich mir selbst hergeleitet im Zusammenhang mit der Frage nach Länge der Vorperiode und Periode. In dem Zusammenhang habe ich mir auch Gedanken über Teilbarkeitsregeln (primär im Dezimalsystem, obwohl die Ergebnisse übertragbar sind) gemacht. Ic müsste erst einmal über asymptotische Verteilung (kenne das nur im Zusammenhang mit Primzahlen) nachlesen. Ob das aber ungelöst ist, entzieht sich meiner Kenntnis.

Mfg Michael

Sukomaki aktiv_icon

20:09 Uhr, 26.12.2017

L_{g} (p) = o r d (g)

habe ich jetzt verstanden :-)

> Ein anderer Rest statt 1 kann nicht als erstes wieder auftreten

Wenn

p

nicht prim ist, trifft das nicht notwendigerweise zu, oder?
Beispiel :

g = 10

p = 6

\Rightarrow

Die Vier tritt als erstes wieder als Rest auf.

Wenn

p

hingegen prim ist, hat die Kommadarstellung von

\frac{1}{p}

keine Vorperiode,
da die Reste die Eins durchlaufen müssen, bevor ein Rest, der vorher entstanden
ist, wieder auftritt?

Gruß
Maki

michaL aktiv_icon

12:58 Uhr, 27.12.2017

Hallo,

>> Ein anderer Rest statt 1 kann nicht als erstes wieder auftreten

> Wenn p nicht prim ist, trifft das nicht notwendigerweise zu, oder?

Korrekt.

Allerdings: Es geht ja um

(ℤ_{p}, \cdot)

im Wesentlichen. Dort gilt: Entweder ist ein Element eine Einheit oder ein Nullteiler (oder Null).
Bei den Nullteilern kann es tatsächlich dazu kommen, dass sich eine Periode einstellt, ohne dass der Rest 1 wieder auftritt. Im Gegenteil: Wenn es sich um einen Nullteiler handelt, KANN der Rest 1 NICHT wieder auftauchen, weil dann

g

invertierbar wäre (was er aber als Nullteiler nicht sein kann).

> Wenn p hingegen prim ist, hat die Kommadarstellung von 1p keine Vorperiode

Nun, im Falle

g = p

schon! In allen anderen Fällen (in der Sprache

(ℤ_{p}^{*}, \cdot, 1,^{- 1})

g

invertierbar) taucht auf jeden Fall der Rest 1 wieder auf.
Und dann kann ein anderer Rest(!) vorher(!) nicht noch einmal auftreten, weil das zu einem Widerspruch zur Minimalität der Ordnung führte.

Mfg Michael

Sukomaki aktiv_icon

18:42 Uhr, 27.12.2017

Hallo,

Warum schreibst Du auf einmal

(ℤ_{p}, \cdot)

?
Bisher haben wir doch nur

(ℤ_{p}^{*}, \cdot)

betrachtet.

Für einen Nullteiler

a

muss gelten :

\exists b : a \cdot b \equiv 0 m o d p \land b \cdot a \equiv 0 m o d p

Betrachten wir

p = 9

2

ist eine Einheit und

3

ist ein Nullteiler

Allgemein sind Einheiten - unabhängig von p prim oder nicht :

1

, weil

1 \cdot 1 \equiv 1 m o d p

p - 1

, weil

(p - 1)^{2} \equiv 1 m o d p

Aber so wie ich das sehe, gibt es für p prim in

(ℤ_{p}^{*}, \cdot)

nur Einheiten.

Ein Element

a

ist Einheit oder Nullteiler und Nullteiler kann

a

nicht sein, da es dann ein

b

geben müsste, für das

a \cdot b \equiv 0 m o d p

Fallunterscheidung :

a = 1 \Rightarrow b = p \equiv 0 m o d p

, was aber laut Def. Nullteiler nicht sein kann.

a > 1 \Rightarrow a ∣ p

was im Widerspruch steht zu

p

prim.

> Wenn es sich um einen Nullteiler handelt, KANN der Rest 1 NICHT wieder auftauchen,
> weil dann g invertierbar wäre (was er aber als Nullteiler nicht sein kann).

D.h. wenn der Rest 1 wieder auftreten würde, hätten wir

g^{n} \equiv 1 \Leftrightarrow g \cdot g^{n - 1} \equiv 1

,
was so viel bedeutet wie

g

ist Einheit und somit kein Nullteiler.

Soweit alles richtig?

Gruß
Maki

michaL aktiv_icon

17:36 Uhr, 28.12.2017

Hallo,

ich denke schon:
* Bei primem Modul

p

sind alle Elemente außer Null Einheiten.
* Bei denen kann nur 1 der erste sich wiederholende Rest sein. (Beweis per Widerspruch)

Demnach kann das "Problem" nur bei Nicht-Einheiten, also den Nullteilern auftreten.
Dort kann wiederum nicht 1 der erste sich wiederholende Rest sein, da sonst der Nullteiler eine Einheit und damit kein Nullteiler wäre.

Null als Rest kann bei Nullteilern auftreten (aber nicht bei primem Modul [s.o.]), aber nur, wenn der Nullteiler sogar nilpotent ist (d.h. eine Potenz davon direkt Null ist).

Mfg Michael

Sukomaki aktiv_icon

10:59 Uhr, 30.12.2017

Hi,

ich habe noch mal eine Rückfrage :

Warum ist

o r d (g^{2}) = \frac{1}{2} o r d (g)

?

Es ist ja nicht z.B.

o r d (g^{3}) = \frac{1}{3} o r d (g)

.

Gruß
Maki

michaL aktiv_icon

09:31 Uhr, 03.01.2018

Hallo,

allen noch ein schönes und gesundes neues Jahr 2018.
Ich hatte in den letzten Tagen Schwierigkeiten, diese Seite aufzurufen.

> Warum ist

ord (g^{2}) = \frac{1}{2} ord (g)

?

Ehrlich gesagt, gilt das auch nicht immer, sondern nur, wenn

2 ∣ ord (g)

.
Wenn

3 ∣ ord (g)

, dann gilt auch

ord (g^{3}) = \frac{1}{3} ord (g)

!

Warum?

Ok, es sei

z := ord (g) := min {n \in ℕ^{*} ∣ g^{n} = 1}

.
Dass im Falle

m ∣ ord (g)

die Gleichung

ord (g^{m}) = \frac{1}{m} ord (g)

gilt, wird in zwei Schritten bewiesen:
(i)

ord (g^{m}) \leq \frac{1}{m} ord (g)

(ii)

ord (g^{m}) \geq \frac{1}{m} ord (g)

(i):

{(g^{m})}^{\frac{1}{m} ord (g)} = {({(g^{m})}^{\frac{1}{m}})}^{ord (g)} = g^{ord (g)} = 1

, d.h. es gilt

ord (g^{m}) ∣ \frac{1}{m} ord (g)

, also insbesondere

ord (g^{m}) \leq \ f a c 1 m ord (g)

.

(ii) Annahme:

ord (g^{m}) < \frac{1}{m} ord (g)

, dann folgt

m \cdot ord (g^{m}) < ord (g) = z

, was mit

1 \overset{(i)}{=} g^{m \cdot ord (g^{m})}

im Widerspruch zur Minimalität von

z

steht.

Zur Untersuchung steht wohl noch, was im Falle

n ∣ / ord (g)

los ist. In dem Falle wird wohl

ord (g^{n}) = \frac{ord (g)}{ggT (n, ord(g))}

gelten.
Ich denke, dass der Beweis sehr ähnlich ist zu dem obigen. Also (i) zeigen, dass dieser Exponent zur 1 führt. (Geeignete Zerlegung in Produkte ist hier hilfreich/notwendig!)
Anschließend die Annahme, dass die Ordnung kleiner ist zum Widerspruch führen. (Hier könnte es ein wenig schwieriger werden.)

Mfg Michael

Sukomaki aktiv_icon

11:29 Uhr, 04.01.2018

> Ich hatte in den letzten Tagen Schwierigkeiten, diese Seite aufzurufen.
Die hatte ich ebenso. Stand auch nichts dazu auf anderen Seiten.

Sei

p

prim

> 2

.
Es ist die maximale Periode =

p - 1

\frac{1}{p}

habe zur Zahlenbasis g maximale Periode.

p

ist prim

\Rightarrow p

ist ungerade

\Rightarrow p - 1

ist gerade.

\Rightarrow \forall p

prim

> 2 : 2 ∣ (p - 1) \Rightarrow

(weil

o r d (g) = p - 1

)

o r d (g^{2}) = \frac{1}{2} o r d (g)

\Rightarrow

es gibt keine maximale Periode.

Wie sieht es für die dritte Potenz von

g

aus?

\exists p : 3 ∣ (p - 1) \Rightarrow

(weil

o r d (g) = p - 1

)

o r d (g^{3}) = \frac{1}{3} o r d (g)

Es gibt aber auch

p

mit

(p - 1) m o d 3 \neq 0 \Rightarrow o r d (g^{3}) = o r d (g) = p - 1

\Rightarrow

es gibt noch Primzahlen

p

deren Entwicklung von

\frac{1}{p}

für die Basis

g^{3}

maximale Periode haben.

Deinen Beweis - denke ich - habe ich so weit verstanden.
Sieht simpel aus, ist aber gar nicht mal so einfach.
Es ist

(g^{m})^{o r d (g^{m})} = 1

. Und wir wissen

g^{z} = 1

mit der Annahme,
dass

z

minimal ist. Wenn also

m \cdot o r d (g^{m}) < z

sein soll,
verletzt das die Minimalität von z. Daraus folgt das Gegenteil, nämlich

o r d (g^{m}) \geq \frac{1}{m} o r d (g)

. Wenn

a \leq b

und

a \geq b \Rightarrow a = b

und in diesem
Fall :

o r d (g^{m}) = \frac{1}{m} o r d (g)

Du schreibst :

1 =^{(i)} g^{m \cdot o r d (g^{m})}

. Das

(i)

über dem Gleichheitszeichen
irritiert mich etwas, da das ja nicht aus

(i)

folgt, sondern aus der Definition von
der Ordnung.

Du benutzt das Symbol für "teilt nicht". Wie geht das mit LaTex?

Gruß
Maki

michaL aktiv_icon

11:53 Uhr, 04.01.2018

Hallo,

die (i) über dem Gleichheitszeichen sollte dir sagen, dass es her so verläuft wie bei (i). Dort wird die gleiche Rechnung vorgenommen.

Das "teilt nicht" gibt es zwar bei LaTeX (\nmid), was aber hier nicht umgesetzt wird.
Ich verwende für

3 ∣ / b

: "3\,|\!\!\!/\,b". Der Befehl "\!" bewirkt einen negativen Abstand von

\frac{3}{18}

em. "\," bewirkt denselben Abstand als positiven Abstand, d.h. "\!" und "\," müssten sich in der Wirkung aufheben.

Mfg Michael

Sukomaki aktiv_icon

14:40 Uhr, 05.01.2018

Vielen Dank für Eure Antworten. Insbesondere an michaL.
Du hast mir sehr geholfen. Danke unter anderem für das

L_{g} (p) = o r d (g)

:-)

1407844

1406930

	Status: nicht eingeloggt	Noch nicht registriert?