Beweise zum ggT ohne Primfaktorzerlegung |
21.04.2010, 23:00 | einbandi | Auf diesen Beitrag antworten » | ||||
Beweise zum ggT ohne Primfaktorzerlegung 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 |
||||||
22.04.2010, 00:28 | 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..." Gruß, Carsten |
||||||
22.04.2010, 10:53 | Mystic | Auf diesen Beitrag antworten » | ||||
RE: Beweise zum ggT ohne Primfaktorzerlegung
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... |
||||||
22.04.2010, 13:11 | 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. |
||||||
22.04.2010, 13:19 | 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. |
||||||
22.04.2010, 13:39 | Mystic | Auf diesen Beitrag antworten » | ||||
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)?
Ja, und von mir aus kann das auch so bleiben, solange du die Hinweise der Helfer sowieso ignorierst... |
||||||
Anzeige | ||||||
|
||||||
22.04.2010, 15:48 | 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. |
||||||
22.04.2010, 17:33 | 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... |
||||||
22.04.2010, 20:11 | einbandi | Auf diesen Beitrag antworten » | ||||
Also etwa: ? Werd mich morgen noch etwas intensiever dran setzen. |
||||||
22.04.2010, 21:47 | Mystic | Auf diesen Beitrag antworten » | ||||
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... |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |
|