Beweise zum ggT ohne Primfaktorzerlegung

Neue Frage »

einbandi Auf diesen Beitrag antworten »
Beweise zum ggT ohne Primfaktorzerlegung
Meine Frage:
Hallo!

Wir machen in Lin. Alg. gerade etwas Zahlentheorie.
Ich muss einige Sachen zum Theam ggT beweisen und komm dabei einfach nicht weiter:

1. Seien und so, dass . Z.z.:


2. Seien (nicht beide 0) und sei . Ohne Verwendung der Primfaktorzerlegung ist z.z.:



Meine Ideen:
Zu 1: Hab schon versucht den ggT von a und b also Linearkombination zu schriben (sa+tb). Konnte aber nicht zeigen, dass s=u und t=v. Klar ist mir natürlich, dass x|ggT(a,b) gelten muss. Habe dann noch versucht zu zeigen, dass ggT(a,b)|x (würde ja für die Gleichheit genügen), hab ich aber nicht geschafft.

Zu 2: Was mich hier einfach stört ist, dass ich die Primfaktorenzerlegung nicht verwenden darf.Habe wieder versucht umzuformen und den ggT als Linearkombination zu schreiben, bin aber nicht weitergekommen.

Würde mich über jeden Tipp freuen.

lg, Andi
akechi90 Auf diesen Beitrag antworten »

Zu 1.: u und v sind nicht eindeutig bestimmt; auf diese Weise kannst du folglich nicht argumentieren.
Versuche mal etwas in der Richtung zu zeigen, dass dein kein echter Teiler von sein kann, das kannst du über einen Widerspruchsbeweis erledigen.

Zu 2.: "Wenn x ein Teiler von a und b ist, dann ist kx..." Augenzwinkern

Gruß,
Carsten
Mystic Auf diesen Beitrag antworten »
RE: Beweise zum ggT ohne Primfaktorzerlegung
Zitat:
Original von einbandi
Habe dann noch versucht zu zeigen, dass ggT(a,b)|x (würde ja für die Gleichheit genügen), hab ich aber nicht geschafft.


Nur um ganz sicher zu gehen: Es geht dir also darum, warum aus x=ua+vb folgt, dass d:=ggT(a,b) ein Teiler von



ist? Wenn meine Vermutung zutrifft, so fürchte ich, kann dir hier niemand helfen... Beweisen heißt ja, etwas auf etwas noch Einsichtigeres zurückführen, das geht hier aber einfach nicht... unglücklich
einbandi1 Auf diesen Beitrag antworten »

Hallo nochmal.

Konnte Nr. heute beweisen. War gar nicht so schwer. Es war einfach nur zu zeigen, dass jeder gem. Teiler von a und b auch x teilt.

Bei zwei steh ich allerdings immer noch auf der Leitung.
einbandi Auf diesen Beitrag antworten »

So ich bins nochmal. Konnte mich vorher nicht anmelden.


Also bei Nummer eins hab ich einen Beweis gefunden. Sei t so, dass t|a und t|b, dann gibt es f,g mit a=tf und b=tg. Also ist x=utf+vtg=(uf+vg)t. Es gilt also t|x für alle gemeinsamen Teiler t von a und b und damit ist x der ggT.

Bei zwei stehe ich allerdings immer noch auf der Leitung.

Hier weiß ich nur, wie man die Gleichheit der beiden Ausdrücke mit Hilfe der Primfaktorzerlegung zeigt. Aber ohne komm ich nicht weiter.
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von einbandi
Also bei Nummer eins hab ich einen Beweis gefunden. Sei t so, dass t|a und t|b, dann gibt es f,g mit a=tf und b=tg. Also ist x=utf+vtg=(uf+vg)t. Es gilt also t|x für alle gemeinsamen Teiler t von a und b und damit ist x der ggT.


Ist dir eigentlich schon aufgefallen, dass man das (ohne Einführung von vielen neuen Buchstaben) auch so schreiben kann:



d.h., exakt das, was ich oben geschrieben habe (mit d statt t)?

Zitat:
Bei zwei stehe ich allerdings immer noch auf der Leitung.

Ja, und von mir aus kann das auch so bleiben, solange du die Hinweise der Helfer sowieso ignorierst... unglücklich
 
 
einbandi Auf diesen Beitrag antworten »

Zunächst mal sorry, dass ich nicht gleich auf deine Antwort eingegangen bin. Ich hab deinen Beitrag gesehen, nachdem ich von der heutigen Vorlesung gekommen bin. Dort haben wir eigentlich den gleichen Satz nur über Polynome bewiesen. Ich hab den Beweis einfach übertragen und hier gepostet. Dass dieser offensichtlich dasselbe meint wie dein Post ist mir nicht gleich aufgefallen. Im übrigen hat mich die Division etwas irritiert.

Hätte ich nicht zufällig den Beweis von einer anderen Quelle früher gehabt, hätte ich mir sicherlich mehr Gedanken über deine Nachricht gemacht.
Mystic Auf diesen Beitrag antworten »

Okay, also dann hier noch ein Hinweis zur zweiten Aufgabe:

Versuche die Behauptung zu zeigen, indem von einer Darstellung



ausgehst und diese noch (in Hinblick auf die zu beweisende Teilbarkeitsrelation) geeignet umformst...Im Grunde "funktioniert" hier derselbe Trick, wie im ersten Teil der Aufgabe...
einbandi Auf diesen Beitrag antworten »

Also etwa:

?

Werd mich morgen noch etwas intensiever dran setzen.
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von einbandi
Also etwa:

?

Werd mich morgen noch etwas intensiever dran setzen.


Ja, bitte tu das, denn ich kann einfach nicht glauben, dass es daran scheitern soll, dass du die Gleichung



nicht korrekt mit k beidseitig multiplizieren kannst... unglücklich
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »