Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Folge größter gemeinsamer Teiler

Folge größter gemeinsamer Teiler

Universität / Fachhochschule

Tags: Folge, ggT

Sukomaki aktiv_icon

19:33 Uhr, 20.02.2020

Hallo,

ich habe hier wieder etwas zum Thema "Größter gemeinsamer Teiler".

Sei

a \in ℕ

beliebig, aber fest.

Dann betrachte ich alle

b \in ℕ

, ob sie relativ prim zu

a

sind. Die Folge dieser

b

nenne ich

G_{a}

. So sind z.B.

G_{2} = (1, 3, 5, 7, 9, 11, 13, 15, \dots)

und

G_{3} = (1, 2, 4, 5, 7, 8, 10, 11, 13, 14, \dots)

Sei nun

D (G_{a})

die Differenzen-Folge von

G_{a}

.

Aus

g g T (a, b + m \cdot a) = g g T (a, b)

folgt sofort, dass

D (G_{a})

periodisch sein muss.
Außerdem folgt, dass die Perioden-Länge der Differenzen-Folge maximal (für Primzahlen)
gleich

a - 1

ist.

So ist z.B.

D (G_{3}) = 1, 2, 1, 2, 1, 2, 1, 2, \dots

Gegeben seien zwei Folgen

F_{1}, F_{2}

von jeweils paarweise verschiedenen Gliedern, die
dazu streng monoton steigend sind. Dann bezeichne

F := F_{1} \cap F_{2}

die Folge, die sich ergibt,
wenn Folgeglieder, die in sowohl

F_{1}

wie auch

F_{2}

enthalten sind, sukzessiv in

F

aufgenommen
werden.

Es gilt :

G_{a_{1} \cdot a_{2}} = G_{a_{1}} \cap G_{a_{2}}

So ist z.B.

G_{6} = G_{2} \cap G_{3} = (1, 5, 7, 11, 13, \dots)

Definition :

κ (n) := 1

wenn

n = 1

und

p_{1} \cdot \dots \cdot p_{r}

wenn

n = p_{1}^{e_{1}} \cdot \dots \cdot p_{r}^{e_{r}}

ι (n) := 1

wenn

n = 1

und

(p_{1} - 1) \cdot \dots \cdot (p_{r} - 1)

wenn

n = p_{1} \cdot \dots \cdot p_{r}

Dann ist die Länge der Periode der Differenzen-Folge von G_a gleich

ι (κ (a))

Desweiteren stimmt die Differenzen-Folge von

G_{a}

überein mit der von

G_{κ (a)}

Was meint Ihr : Lohnt es sich, da am Ball zu bleiben, oder ist das nur Spielerei?
Ich habe ja die Erfahrung gemacht, dass vieles interessant wird, wenn ich nur tief
genug in das Thema eindringe.

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."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Rechnen mit Klammern
Teilbarkeit natürlicher Zahlen

ledum aktiv_icon

19:59 Uhr, 20.02.2020

Hallo
so wie du

G_{a}

definiert hast, ist

G_{2} \cap G_{3} \neq G_{6}

denn zu

G_{6}

gehören ja alle Zahlen zwischen 0 und 6 dann alle zwischen 6 und12 usw.
Das mit der Länge der Differenzenfolge kapier ich nicht. oder du musst eben

G_{a}

anders definieren, eben als der Schnitt der

G

aller Primfaktoren? dann wäre aber

G_{p^{2}} = G_{p}

Spannend oder interessant finde ich das bisher nicht.
Gruß ledum

Sukomaki aktiv_icon

20:49 Uhr, 20.02.2020

> so wie du

G_{a}

definiert hast, ist

G_{2} \cap G_{3} \neq G_{6}

Ich bestehe darauf, dass

G_{2} \cap G_{3} = G_{6}

:-)

> denn zu

G_{6}

gehören ja alle Zahlen zwischen 0 und 6 dann alle zwischen 6 und12 usw

Hä? Wer hat Dir denn das erzählt?

G_{6}

ist laut meiner Definition die Folge aller Zahlen, für die

g g T (6, b) = 1

Also :

G_{6} = (1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, \dots)

Oder wie jetzt?

HAL9000

21:09 Uhr, 20.02.2020

Ja, ist schon alles sehr einleuchtend.

Klar ist, dass für alle

a, b

die Eigenschaft

g g T (a, b) = 1 \Leftrightarrow g g T (κ (a), b) = 1

gilt, woraus unmittelbar

G_{a} = G_{κ (a)}

und damit auch

D (G_{a}) = D (G_{κ (a)})

folgt.

ι (n)

entspricht der Eulerschen

φ

-Funktion

φ (n)

, gibt eben die Anzahl der zu

n

teilerfremden Zahlen des Bereichs

1 \dots n

an.

So bedeutsam die

G_{a}

in der Zahlentheorie sind - allgemein dürfte übrigens gelten

G_{a} \cap G_{b} = G_{k g V (a, b)}

- an den Differenzenfolgen

D (G_{a})

vermag ich abgesehen von der Periodizität nicht sonderlich viel Spannendes zu entdecken.

Sukomaki aktiv_icon

21:40 Uhr, 20.02.2020

Hallo,

hat Dir schon mal jemand gesagt, dass Du es echt drauf hast?

>

ι (n)

entspricht der Eulerschen

φ

-Funktion

Aber doch nur für

n

, deren sämtliche Primfaktoren die Vielfachheit

1

haben, oder?

Und warum entspricht

ι

der

φ

-Funktion?

>

G_{a} \cap G_{b} = G_{k g V (a, b)}

Hey, da habe ich etwas, das ich zur Übung beweisen kann.
Vielleicht mit

k g V (a, b) = \frac{a \cdot b}{g g T (a, b)}

. Mal schauen :-)

> Dann ist die Länge der Periode der Differenzen-Folge von

G_{a}

gleich

ι (κ (a))

Wäre ja schön, wenn Du mir da auch einen Hinweis geben könntest.
Bis jetzt habe ich für diese Behauptung nämlich noch keinen Beweis.

Danke aber erstmal so weit.

ledum aktiv_icon

22:50 Uhr, 20.02.2020

sorry, ich hatte die Definition von

G_{a}

falsch gelesen, du hast recht, das war dumm.
Gruß ledum

HAL9000

23:35 Uhr, 20.02.2020

> Aber doch nur für

n

, deren sämtliche Primfaktoren die Vielfachheit 1 haben, oder?

Für andere

n

hast du

ι (n)

doch gar nicht definiert, und nutzt es ja auch für keine anderen. Was spricht also dagegen, gleich das auf einer größeren Menge definierte

φ (n)

nehmen, wenn es doch auf der eingeschränkten Menge dieser Zahlen mit deinem

ι (n)

übereinstimmt?

> Wäre ja schön, wenn Du mir da auch einen Hinweis geben könntest.

Ich dachte, das sei jetzt soweit klar? Ordnet man die Werte in

G_{n}

der Größe nach an, d.h.

G_{n} = (a_{1}, a_{2}, \dots)

, dann gilt offenbar

a_{k + φ (n)} = n + a_{k}

(je

n

auf einander folgende ganze Zahlen enthalten genau

φ (n)

n

teilerfremde Zahlen, egal wo man sich auf dem Zahlenstrahl befindet), damit ist

a_{k + 1 + φ (n)} - a_{k + φ (n)} = n + a_{k + 1} - n - a_{k} = a_{k + 1} - a_{k}

und wir haben die

φ (n)

-Periodizität der Folge

D (G_{n})

. Das gilt natürlich speziell auch für

n = κ (a)

, fertig.

Übrigens: Das mit dem kgV war eigentlich unnötig, es gilt tatsächlich

G_{a} \cap G_{b} = G_{a b}

für alle

a, b

- wichtig ist nur, dass man die in

a

sowie

b

enthaltenen Primfaktoren (darunter ggfs. auch welche, die sowohl in

a

als auch

b

vorkommen) alle zusammenwürfelt.

Sukomaki aktiv_icon

16:59 Uhr, 21.02.2020

Ich habe noch nicht verstanden, warum

ι (n) = φ (n)

auf der eingeschränkten Menge gilt.

φ (n)

ist definiert als die Anzahl der zu

n

teilerfremden Zahlen zwischen

1

und

n

.

Jetzt ist

g g T (n, k) = g g T (n, k m o d n)

Deshalb ist

φ (n)

konstant, wenn man das Intervall in der Definition um

d

verschiebt.
Das heisst,

φ (n)

ist die Anzahl der zu

n

teilerfremden Zahlen zwischen

2

und

n + 1

und

φ (n)

ist die Anzahl der zu

n

teilerfremden Zahlen zwischen

3

und

n + 2

u.s.w.

Daraus folgt, dass

a_{k + φ (n)} = n + a_{k}

.

Weil ich den Index von

a

φ (n)

erhöhen muss, wenn ich

a_{k}

n

erhöhe.

Richtig soweit?

HAL9000

18:04 Uhr, 21.02.2020

> Ich habe noch nicht verstanden, warum

ι (n) = φ (n)

auf der eingeschränkten Menge gilt.

Schau dir mal an, wie

φ (n)

basierend auf der Primfaktorzerlegung von

n

ausgedrückt werden kann:

de.wikipedia.org/wiki/Eulersche_Phi-Funktion

Dann schau dir deine Definition von

ι (n)

an. Und dann überlegst du dir, ob du diese Frage wirklich nochmal stellen willst.

Sukomaki aktiv_icon

18:38 Uhr, 21.02.2020

> Schau dir mal an, wie

φ (n)

basierend auf der Primfaktorzerlegung von

n

ausgedrückt werden kann:

Hab ich gemacht.

> Dann schau dir deine Definition von

ι (n)

an.

Hab ich gemacht.

Und ich kam zu folgendem Schluß :

1. Ist

φ (p) = p - 1

für

p

prim
2. Ist

φ (n)

multiplikativ

\Rightarrow

3. Ist

φ (n) = (p_{1} - 1) \cdot \dots \cdot (p_{r} - 1) = ι (n)

:-D)

> Und dann überlegst du dir, ob du diese Frage wirklich nochmal stellen willst.

Nee, ist jetzt soweit richtig, oder?

Sukomaki aktiv_icon

22:45 Uhr, 22.02.2020

Hi Hal9000,

Du hast nicht geantwortet. Soll ich das so interpretieren, dass mein letzter Post falsch ist?

Übrigens : Hast Du gewusst, dass "HAL" um Eins im Alphabet verschoben "IBM" gibt?

Der Autor von

2001

Odyssey im Weltraum - ich glaube, er heisst Arthur C. Clarke - sagt, dass das Zufall sei :-)

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1495655

1495494

	Status: nicht eingeloggt	Noch nicht registriert?