Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Quasie Assoziativgesetz für ggTeiler

Quasie Assoziativgesetz für ggTeiler

Universität / Fachhochschule

Sonstiges

Tags: Sonstiges, Teiler

Underfaker aktiv_icon

19:08 Uhr, 07.12.2011

Hallo,

Meine Aufgabe lautet, dass ich für

x, y, z \neq 0

zeigen soll:

ggT(x,ggT(y,z)) = ggT(ggT(x,y),z)

Um mich ein bisschen ran zu tasten habe ich ertsmal Zahlen benutzt um zu sehen wie das Ganze aussieht also bspw.

ggT(56,ggT(48,16)) = ggT(ggT(56,48),16)

= ggT(56,16) = ggT(8,16)

= 8 = 8

und nun mit Variablen:

ggT(x,ggT(y,z)) = ggT(ggT(x,y),z)

ggT(y,z) sei

p

und ggT

(x, y)

sei

q

\Rightarrow

ggT(x,p) = ggT(q,z) (sei ggT(x,p)und ggT(q,z)=n)

= n

unsere Notation von teilen sieht vor

2 | 4 (= 2

teilt

4)

Also sihet man:

n | x \land n | p

sowie

n | q \land n | z

und somit:

p | y \land p | z

sowie

q | x \land q | y

jetzt sehe ich ja durchaus auf beiden Seiten dass in der Kette

x, y

undz geteilt werden. Bringt mir das denn für einen Beweis etwas oder wie fange ich einen solchen Beweis am Besten an?

Vielen Dank schonmal :-)

michaL aktiv_icon

20:14 Uhr, 07.12.2011

Hallo,

ach, die kann man so schön komprimieren, diese Aufgabe!

Zu zeigen ist

ggT (x, ggT (y, z)) = ggT (ggT (x, y), z)

Zeige einfach:
-

ggT (x, ggT (y, z)) \leq ggT (ggT (x, y), z)

und
-

ggT (x, ggT (y, z)) \geq ggT (ggT (x, y), z)

;-)

Mfg Michael

Ok, anbei noch ein (kryptischer Tipp): Gilt

d ∣ x

und

d ∣ y

, dann gilt schon

d \leq ggT (x, y)

(warum?).

Underfaker aktiv_icon

20:31 Uhr, 07.12.2011

Hallo nochmal,

"Ok, anbei noch ein (kryptischer Tipp): Gilt d∣x und d∣y, dann gilt schon d≤ggT(x,y) (warum?)."

Wenn

d

sowohl Teiler von

x

als auch von

y

ist und wir wissen das der ggT

(x, y)

der größte aller gemeinsamen Teiler von

x

und

y

ist ist, so kann

d

nur kleiner als dieser Teiler sein oder aber gleich diesem Teiler, nämlich wenn

d

der ggT selbst ist.

Kurzum, es ist nicht möglich einen größeren Teiler zweier Zahlen zu finden als den ggT, sonst verdiente er diesen Namen ja nicht.

Soweit schonmal korrekt?

(ich probier mal den Ansatz aus den du angeboten hast, allerdings frage ich mich doch wo die Komprimierung ist, da ich nun zwei statt einer "Sache" zu zeigen habe :-D), sicher liegt das in der Beweisführung die ich jetzt noch nciht erkenne?!)

michaL aktiv_icon

20:35 Uhr, 07.12.2011

Hallo,

ja, das "warum?" hast du korrekt beantwortet.

Was die Komprimierung anbelangt, das ist eine Frage des eigenen Könnens.
Wenn du also die Gleichung in einem Zuge und direkt beewisen kannst, dann los. Aber dann hättest du nicht gepostet, oder?
Die meisten versuchen es über die Teilereigenschaft(en). Damit geht es, ist aber ein bisschen umständlich. Dem gegenüber ist der Weg, den ich durch den Tipp angedeutet habe, echt eine Abkürzung!

Mfg Michael

Underfaker aktiv_icon

20:58 Uhr, 07.12.2011

Mir leuchtet die Vorgehensweise durchaus ein.

Ich hab das mal durchgespielt

ggT(x,ggT(y,z)) = ggT(ggT(x,y),z)

sei ggT(y,z)=p und ggT(x,y)=q

sei ggT(x,p)

= m

und ggT(q,z)=n

p | y

und

p | z \Rightarrow

p<=ggT(y,z)

m | x

und

m | p \Rightarrow

m<=ggT(x,p)

dann aber auch m<=ggT(y,z)

(m \leq x, y, z, p)

rechte Seite:

q | x

und

q | y \Rightarrow q \leq

ggT(x,y)

n | q

und

n | z \Rightarrow n \leq

ggT(q,z)

dann aber auch n<=ggT(x,y)

(n \leq x, y, z, q)

Und jetzt habe ich alle möglichen Relationen gezeigt aber das alles verwirrt mich mehr umso länger ich drauf schaue, kann ich aus dem was ich bisher habe schon etwas zeigen?

Oder bin ich (erwartungsgemäß :-) ) auf dem Holzweg?

Danke schonmal

=)

michaL aktiv_icon

21:05 Uhr, 07.12.2011

Hallo,

nein, es ließe sich etwas daraus machen, allerdings braucht man dazu letztlich mehr die Teilereigenschaft. Die hast du (noch) nicht wirklich eingebracht.

Ich würde es aber tatsächlich so machen:

Sei

t := ggT (x, ggT (y, z))

, d.h. (insbeosndere) gilt

t ∣ x

und

t ∣ ggT (y, z)

, also (wieder insbesondere)

t ∣ y

und

t ∣ z

.
Also gilt

t ∣ x

t ∣ y

und

t ∣ z

.
Daraus machen wir:

t ∣ ggT (x, y)

und

t ∣ z

. Ergo:

t ∣ ggT (ggT (x, y), z)

, also inbesondere

t \leq ggT (ggT (x, y), z)

bzw.

ggT (x, ggT (y, z)) \leq ggT (ggT (x, y), z)

Umgekehrt mit aber auch exakt der gleichen Schlussweise erhältst du

ggT (x, ggT (y, z)) \geq ggT (ggT (x, y), z)

.

Mfg Michael

Underfaker aktiv_icon

21:17 Uhr, 07.12.2011

Ok vielen Dank :-).

Ich hatte allerdings zwei Dinge die ich nciht verstanden habe, eins habe ich mittlerweile verstanden nicht jedoch das andere, könntest du mir das vielleicht erklären? (ist sicher trivial ich steh dennoch leider auf dem Schlauch).

Es handelt sich dabei um den Schritt:

Daraus machen wir: t∣ggT(x,y) und t∣z.

Was mir (noch) nicht einleuchtet ist, wieso

t

auch ein Teiler des ggTs von

x

und

y

sein muss...

hagman aktiv_icon

21:30 Uhr, 07.12.2011

Es geht auch so:
Bezeichnen wir mit

D (a) := {x \in ℤ : x | a}

die Menge der Teiler von

a,

so ist

g g T (a, b)

das größte Element von

D (a) \cap D (b)

.
Genauer gilt sogar

D (a) \cap D (b) = D (g g T (a, b))

(Achtung! das ist der Knackpunkt! Warum gilt er?)
Wenn man es sich jetzt genauer anschaut, folgt die Assoziativität von

g g T

direkt aus der Assoziativität von

\cap, d . h

g g T (g g T (a, b), c)

ist das größte Element von

(D (a) \cap D (b)) \cap D (c)

g g T (a, g g T (b, c))

ist das größte Element von

D (a) \cap (D (b) \cap D (c))

(D (a) \cap D (b)) \cap D (c) = D (a) \cap (D (b) \cap D (c)),

folgt die BEhauptung.

michaL aktiv_icon

21:40 Uhr, 07.12.2011

Hallo,

das Argument ist immer das gleiche:

t ∣ a

und

t ∣ b \overset{}{\Leftrightarrow} t ∣ ggT (a, b)

(weil der ggT eben der GRÖSSTE Teiler...)

Mfg Michael

Underfaker aktiv_icon

21:53 Uhr, 07.12.2011

@ michal

Danke, irgendwie fehlte mir das Verständnis dafür das wenn

t x

und

y

teilt das dann

t

auch den größten der beiden Teiler teilen muss.

Vielen Dank für deine Hilfe :-)

@ hagman

D (a) \cap D (b)

ist ja gerade die Menge aller Teiler die sowohl a als auch

b

teilen.
D(ggT(a,b)) ist die Menge aller Teiler des ggT(a,b).

Wenn

x

den ggT teilt dann muss dieses

x

ja auch zwangsläufig a und

b

teilen und ist entsprechend

\in D (a) \cap D 8 b)

.

Kann man das so ausdrücken? (Ist ja dem nicht unänlich was ich michal gefragt hatte)

Danke schonmal sehr für die Hilfe

michaL aktiv_icon

21:59 Uhr, 07.12.2011

Hallo,

wir brauchen nur diese beiden (wie ich finde unmittelbar einsichtigen) Eigenschaften:

(i)

t ∣ a

t ∣ b \overset{}{\Rightarrow} t \leq ggT (a, b)

(ii)

t ∣ ggT (a, b) \overset{}{\Rightarrow} t ∣ a

t ∣ b

zu (i): Wenn

t

sowohl ein Teiler von

a

UND von

b

ist (mit anderen Worten ein gemeinsamer Teiler von

a

und

b

ist), dann ist gilt sicher

t \leq ggT (a, b)

(der ggT ist von allen gmeiensamen Teilern eben der Größte).

Zu (ii): "Teilen" ist transitiv, d.h. der Teiler eines Teilers von

a

ist auch ein Teiler von

a

. Ebenso für

b

.

Mfg Michael

Underfaker aktiv_icon

22:12 Uhr, 07.12.2011

Ok verstanden :-)

Das war jetzt aber ein Zusatz zu deiner Ausführung?! Nicht das ich das falsch aufgefasst habe und das mit auf hagmans Lösung bezogen war, wobei ich finde das die Logik hinter der Teilbarkeit natürlich in beiden Wegen irgendwo relevant ist.

michaL aktiv_icon

22:57 Uhr, 07.12.2011

Hallo,

hagmans Lösung ist natürlich sehr elegant, aber es steckt auch schon viel Wissen dahinter.
Beispielsweise braucht man das Wissen, dass

(ℤ, +, \cdot)

ein Hauptidealring ist.

Dadurch kommt es, dass der Durchschnitt

D (a) \cap D (b)

(beides Ideale) wieder von der Form

D (ggT (a, b))

ist.

Mfg Michael

Underfaker aktiv_icon

08:11 Uhr, 08.12.2011

ok, das klingt in der Tat nach etwas was ich bisher nicht kannte :-)

@ hagman wie sieht es mit meiner Aussage aus?

würde das nämlich gern beides

100 %

verstehen (also mir dabei sicher sein)

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

949423

949221

	Status: nicht eingeloggt	Noch nicht registriert?