Teilerfremdheit und Restklassen |
17.09.2014, 22:06 | Doutzi | Auf diesen Beitrag antworten » | ||
Teilerfremdheit und Restklassen Hallo Zusammen! Bei einer Aufgabenserie in Algebra stecke ich beim Beweis einer Aufgabe fest. Ich weiss nicht, ob das was ich mache stimmt bzw. ob ich das so darf und wäre sehr froh um einen Tipp Die Aufgabe lautet: Es sei . Zeigen Sie, dass für folgende Aussagen äquivalent sind: 1) x ist teilerfremd zu n, 2) x besitzt ein Inverses für die Multiplikation in Z/nZ. Meine Ideen: Für die Richtung von 2) nach 1) habe ich bis jetzt: (x + nZ)(y + nZ) = xy + nZ = 1 + nZ (mit (y + nZ) Inverses bezüglich Multiplikation. Daraus folgt, xy = 1. Also muss x teilerfremd sein von n, da sonst xy + nZ = 0 + nZ ist und somit x kein Inverses bezüglich der Multiplikation hat. Für die Richtung von 1) nach 2) Da x teilerfremd zu n ist, ist der ggT(x,n) = 1. Daraus folgt: d = ax + bn = 1 (Da es ja eine Formel gibt, die besagt, dass wenn ggT(m,n) = d existieren mit d = am + bn). Da bn gleich 0 ist, muss ax = 1 sein, und da man ax als (a + nZ)(x + nZ) schreiben kann, bedeutet dies, dass x ein multiplikatives Inverses in Z/nZ hat. Vielen Dank für einen Tipp! |
||||
17.09.2014, 22:22 | MatheMaster_93 | Auf diesen Beitrag antworten » | ||
Hallo Doutzi, also (i)-> ii) ist so richtig. (i)-> ii): Versteh ich deine Argumentation nicht ganz. EDIT: Der richtige Weg geht auch über die Darstellung des GGT als Linearkombination. |
||||
17.09.2014, 23:43 | Doutzi | Auf diesen Beitrag antworten » | ||
Hallo MatheMaster_93, Vielen Dank für den Tipp!
Das heisst, ich müsste ja mit d = ax + bn etwas Schlaues hinbekommen, oder? Also bn ist wider Null, da bleibt mir noch ax. Nach Voraussetzung besitzt x ein Inverses für die Multiplikation in Z/nZ, d.h. ax kann man schreiben als (a + nZ)(x + nZ), und (a + nZ)(x + nZ) muss ja glech 1 + nZ sein, da (a + nZ) das multiplikative Inverse von x ist. Aber wie folgere ich jetzt daraus, dass x teilerfremd von n ist? Ich stehe etwas auf dem Schlauch momentan... |
||||
18.09.2014, 00:07 | MatheMaster_93 | Auf diesen Beitrag antworten » | ||
Ansatz: Besitze x also ein multiplikatives Inverse,y, in . Es ist . Nach Voraussetzung ist Was fällt dir jetzt auf? |
||||
18.09.2014, 14:12 | Doutzi | Auf diesen Beitrag antworten » | ||
Leider nicht so viel... |
||||
18.09.2014, 14:40 | MatheMaster_93 | Auf diesen Beitrag antworten » | ||
Das macht nichts, deswegen sind wir ja hier Also wir setzen Dann haben wir die Darstellung Mal ein konkretes Beispiel. Nehmen wir Dann können wir schreiben: . Dann können wir aber JEDES Vielfach vom GGT auch darstellen - indem wir die komplette Gleichung multiplizieren. Nehmen wir aber zum Beispiel . Dann ist und die Darstellung als Linearkombination ist . (Einfach glauben, die Darstellung kriegt man leicht mit dem euklidischen Algorithmus). Wieder können wir Vielfache von 2 auch darstellen. Aber die 1 - das geht nicht! Denn dazu müsstest du die Gleichung durch 2 teilen, und wir hätten , das ist aber ungültig, da . Wenn wir also eine ganzzahlige Linearkombination haben, was gilt für den GGT? |
||||
Anzeige | ||||
|
||||
18.09.2014, 15:29 | Doutzi | Auf diesen Beitrag antworten » | ||
Vielen Dank! Das würde doch bedeuten, dass der GGT(x,n) = 1 sein muss, was wiederum bedeutet, dass x und n teilerfremd sind. Korrekt so? Eine Frage habe ich noch zu Deiner Antwort: Wie kommst du auf diese Darstellung mit dem euklidischen Algorithmus? Also beim ersten Beispiel mit und , wie kommt man auf ? |
||||
21.09.2014, 20:25 | Doutzi | Auf diesen Beitrag antworten » | ||
Wie sieht es aus, stimmt meine Vermutung? Wäre sehr lieb, wenn mich jemand korrigieren könnte |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |