Rechnen im Restklassenkörper

Neue Frage »

blubbi Auf diesen Beitrag antworten »
Rechnen im Restklassenkörper
Hallo.
Ist jetzt bestimmt ne ganz einfache Frage ... ich komm aber im Moment einfach nicht auf die Lösung ...

Wenn ich im Z29 (Rechnen mod 29)
eine Zahl durch 19 teilen will muß ich ja das inverse von 19 rausfinden.

Wie mach ich das?

Danke für alle Antworten!
AD Auf diesen Beitrag antworten »
RE: Rechnen im Restklassenkörper
Zwei Möglichkeiten:

1) Systematisches Probieren: Also alle Produkte k*19 für k=2,...,28 ansehen und das nehmen, welches modulo 29 den Rest 1 lässt. Ist für kleine Module gar nicht so abwegig.

2) Erweiterter euklidischer Algorithmus, z.B. hier mit nettem WWW-Interface:
http://www.mirsky.de/ggt.php
blubbi Auf diesen Beitrag antworten »

hm aber der eea liefert mir 1 also ergebnis zurück ...

hier mal die "lösung" aus der ich nicht schlau werde

EEA (19,29) -->
26*19 + x * 29 = 1 (wieso 26??)
26 * 19 = 1 mod 29
26 = 19^-1 mod 29

y1 = 26*8 = 5mod 29
AD Auf diesen Beitrag antworten »

Es geht nicht um den ggT, die Seite liefert fast ganz unten die Zeile

code:
1:
1=2*29+-3*19 Erklaerung: y=ua+vb 


Wenn du jetzt modulo 29 bildest, erhältst du die Aussage



Na, klingelt's jetzt?
blubbi Auf diesen Beitrag antworten »

ne klingelt nicht wirklich ... wie komm ich denn auf die 5?
AD Auf diesen Beitrag antworten »

Wir waren oben bei der Lösung der Gleichung



und haben als Lösung rausbekommen

.

Was soll jetzt die 5 ?
 
 
jumaki Auf diesen Beitrag antworten »

die 5 ist das zu 19^-1 gehörende inverse element, mit dem dann der verankerungsvektor an 1. position bestückt wird....
AD Auf diesen Beitrag antworten »

Zitat:
Original von jumaki
die 5 ist das zu 19^-1 gehörende inverse element

Falsch. Das inverse Element zu 19^-1 ist die 19 selbst, und das inverse Element zu 19 ist 26 (wie oben berechnet).

Zitat:
Original von jumaki
mit dem dann der verankerungsvektor an 1. position bestückt wird....

Man lernt doch immer wieder neue Begriffe kennen: Was ist ein Verankerungsvektor?
jumaki Auf diesen Beitrag antworten »

hm, ich glaube wir reden hier alle ein bisschen aneinander vorbei. die aufgabe ist:
im rkk Z-29 soll man bei der gleichung
19x1 - 6x2 + 11x3 - 14x4 +21x5 = 8
alle lösungen bestimmen. die zahlen nach jedem x sind indexzahlen.

die gleichung hat 4 freiheitsgrade, d.h. man darf x2=x3=x4=x5=0 setzen.
wenn man das tut bleibt noch 19x1 = 8
also x1 = 19^(-1) * 8

jetzt sucht man das inverse von 19 in Z-29 und der tutor hat dazu die zeilen:

EEA (19,29) -->
26*19 + x * 29 = 1 (wieso 26??)
26 * 19 = 1 mod 29
26 = 19^-1 mod 29
y1 = 26*8 = 5mod 29

als lösungsschritte angeschrieben. nachdem er das von der lösung des dozenten hat, wird es wohl auch stimmen. damit ist der verankerungsverktor ygleich (5 0 0 0 0) vertikal geschrieben. der verankerungsverktor y ergibt mit vier teilräumen die lösung des linearen gleichuchngssystems.

nun verstehen wir nicht wie man in diesem lösungsschema auf die zahlen 26 und am ende auf die lösung 5 kommt....
AD Auf diesen Beitrag antworten »

Danke erst mal für die Aufgabenstellung - ich bin nämlich nicht mit hellseherischen Fähigkeiten gesegnet, als dass ich diese aus den spärlichen Angaben oben hätte erahnen können. Augenzwinkern

Also x2...x5 fort geräumt, bleibt übrig. Nun ist 29 Primzahl, also der Restklassenring modulo 29 ein Körper mit jeweils eindeutig bestimmter Inverser (außer der Null natürlich). Somit gilt



und diese Inverse haben wir ja oben bestimmt, das ist 26 (oder -3, wie man will). Es folgt



wo ist jetzt das Problem?


EDIT: Euch ist aber schon klar, dass (5, 0, 0, 0, 0) nicht die einzige Lösung von 19x1 - 6x2 + 11x3 - 14x4 +21x5 = 8 ist?
jumaki Auf diesen Beitrag antworten »

das problem war auf die 26 zu kommen, was ja anscheinend nur durch raten geht.

vielen dank für deine hilfe!

ps: ja das ist schon klar! deswegen gibts ja noch die homogenen lösungen die mit dem verankerungsvektor kombiniert alle lösungen repräsentieren.
AD Auf diesen Beitrag antworten »

Nicht nur raten, sondern auch mit dem erweiterten euklidischen Algorithmus (s.o.) !!!
Neue Frage »
Antworten »



Verwandte Themen

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