Teilerfremdheit und Restklassen

Neue Frage »

Doutzi Auf diesen Beitrag antworten »
Teilerfremdheit und Restklassen
Meine Frage:
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 smile

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!
MatheMaster_93 Auf diesen Beitrag antworten »

Hallo Doutzi,

also (i)->traurig ii) ist so richtig.

(i)->traurig ii): Versteh ich deine Argumentation nicht ganz.

EDIT: Der richtige Weg geht auch über die Darstellung des GGT als Linearkombination.
Doutzi Auf diesen Beitrag antworten »

Hallo MatheMaster_93,

Vielen Dank für den Tipp!

Zitat:
Der richtige Weg geht auch über die Darstellung des GGT als Linearkombination.


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...
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?
Doutzi Auf diesen Beitrag antworten »

Leider nicht so viel... traurig
MatheMaster_93 Auf diesen Beitrag antworten »

Das macht nichts, deswegen sind wir ja hier Freude

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?
 
 
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 ?
Doutzi Auf diesen Beitrag antworten »

Wie sieht es aus, stimmt meine Vermutung? Wäre sehr lieb, wenn mich jemand korrigieren könnte smile
Neue Frage »
Antworten »



Verwandte Themen

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