Ringe und Restklassenringe

Neue Frage »

Mijo Auf diesen Beitrag antworten »
Ringe und Restklassenringe
Hallo miteinander,

ich habe ein kleines Problem mit zwei Aufgaben.

1)

2)


Zu 1) habe ich folgendes gemacht:

Ich habe den ggt(602,784) berechnet.
Dann kam raus: ggt(602,784) = 14. Mit rückwärts einsetzen lässt sich das dann so schreiben:



Dann habe ich das mit 22 mulitpliziert, um links 308 stehen zu haben.



Mit mod784 ergibt sich folgendes:



An diesem Schritt komme ich jetzt nicht mehr weiter.

zu 2)
Hier hab eich leider gar keine Idee, wie man überhaupt an so eine Aufgabe rangeht. Leider geht das auch nicht aus dem Vorlesungsskript hervor...

Kann mir jemand helfen?

Viele Grüße
Mijo
galoisseinbruder Auf diesen Beitrag antworten »

Hallo,

bei der 1) hast du zu weit gerechnet. Schau dir mal diese deine Zeile an:

im vergleich zur Aufgabenstellung:

Zur 2) Nach der 1 weißt du wie man Inverse Elemente ausrechnet. Welche Elemente von R sind denn keine Einheiten weil sie Nullteiler sind?
 
 
Mijo Auf diesen Beitrag antworten »

Hallo,
okay...


Soll das bedeuten, dass die Lösung ist? im Grunde kann ich es da ja direkt ablesen...

Mir was bisher gar nicht klar, dass ich mit dieser Rechnung ein Inverses ausrechne... Was ist ist denn dann das Inverse und zu welchem Element gehört es?

zu 2)

Also, Nullteiler sind laut Definition ja diejenigen Elemente aus R für die folgendes gilt: Wenn es ein Element b aus R gibt, für das gilt a*b = 0, dann ist a ein Nullteiler von R.
R enthält alle Elemente von 1 bis 29.

Hier verstehe ich nicht, welche b ich nun nehmen kann. Nichts aus multipliziert mit etwas aus ergibt 0 ?!?!

Tut mir leid, wenn ich mich total bescheuert anstelle...
galoisseinbruder Auf diesen Beitrag antworten »

Zitat:
Mir was bisher gar nicht klar, dass ich mit dieser Rechnung ein Inverses ausrechne... Was ist ist denn dann das Inverse und zu welchem Element gehört es?

Normalerweise führt man den erweiterten euklidischen Algorthmus nur aus wenn der ggT 1 ist.
Und dann liefert die darstellung ein Inverses zu y.

zu 2) R enthält 30 Elemente, in der Aufzählung vergisst du das wichtigste Element.

Zitat:
Nichts aus multipliziert mit etwas aus ergibt 0 ?!?!

Ich widerspreche dir da: 22 Elemente sind Nullteiler. Versuch mal ein paar und bedenke
Mijo Auf diesen Beitrag antworten »

Zitat:
Original von galoisseinbruder
Zitat:
Mir was bisher gar nicht klar, dass ich mit dieser Rechnung ein Inverses ausrechne... Was ist ist denn dann das Inverse und zu welchem Element gehört es?

Normalerweise führt man den erweiterten euklidischen Algorthmus nur aus wenn der ggT 1 ist.
Und dann liefert die darstellung ein Inverses zu y.


Okay, das versuche ich dann, wenn ich gleich hoffentlich mich den Einheiten durch bin.

Zitat:
Original von galoisseinbruder
zu 2) R enthält 30 Elemente, in der Aufzählung vergisst du das wichtigste Element.

Ich widerspreche dir da: 22 Elemente sind Nullteiler. Versuch mal ein paar und bedenke


Hm, okay, der Ring enthält die Elemente von 0 bis 29.

Ich sehe auch gerade, dass die Lösung eingetragen ist: Laut Lösung sind 1,7,11,13,17,19,23 und 29 Einheiten des Ringes.

Okay, ich verstehe, dass zum Beispiel 2 und 15 Nullteiler sind, weil das Produkt 30 ergibt und ich somit wieder bei 0 lande. Ah, ich wollte gerade fragen, warum 4, 21 etc. nicht drin sind, aber das sind ja alles Vielfache der anderen Nullteiler. Was jetzt übrig bleibt, sind Primzahlen....

Kann ich jetzt mit dem erweitertern Euklidischen Algorithmus die Inverse zum Beispiel von 7 wie eben von dir angesprochen ausrechnen?
galoisseinbruder Auf diesen Beitrag antworten »

Zitat:
Was jetzt übrig bleibt, sind Primzahlen....

Das ist reiner Zufall, und manche Primzahlen, wie die 2,3,5 sind nicht dabei. Das könnte dich auf den Gedanken womit es wirklich zusammenhängt.
(z.B. sind modulo 5 die Restklassen 1,2,3 und 4 invertierbar)
Zitat:
nicht drin sind, aber das sind ja alles Vielfache der anderen Nullteiler

ist schon die richtige Richtung.

Zitat:
Kann ich jetzt mit dem erweitertern Euklidischen Algorithmus die Inverse zum Beispiel von 7 wie eben von dir angesprochen ausrechnen?

Das ist das Verfahren das man standard mäßig verwendet (außer natürlich man sieht die Inversen so).
Mijo Auf diesen Beitrag antworten »

Zitat:

Zitat:
Was jetzt übrig bleibt, sind Primzahlen....

Das ist reiner Zufall, und manche Primzahlen, wie die 2,3,5 sind nicht dabei. Das könnte dich auf den Gedanken womit es wirklich zusammenhängt.
(z.B. sind modulo 5 die Restklassen 1,2,3 und 4 invertierbar)


So ganz ist mir das noch nicht klar gerade...

Zitat:

Zitat:
nicht drin sind, aber das sind ja alles Vielfache der anderen Nullteiler

ist schon die richtige Richtung.


Die Vielfachen einer Restklasse gehören doch auch dazu, deshalb sind es in dem Fall doch auch alle Nullteiler, oder?

Zitat:

Zitat:
Kann ich jetzt mit dem erweitertern Euklidischen Algorithmus die Inverse zum Beispiel von 7 wie eben von dir angesprochen ausrechnen?

Das ist das Verfahren das man standard mäßig verwendet (außer natürlich man sieht die Inversen so).


Also ich spinne hinsichtlich der Inversen jetzt mal ein wenig rum, wenn das erlaubt ist.

Ich nehme mir zum Beispiel die 7 raus... Jetzt muss ich mit wieder so hinkommen, dass der Rest ein Vielfaches von 30 ist oder?
Und weil ich das z.b. bei 29 nicht schaffe, muss ich die 29 als Inverse nehmen, weil mit das bei 0 liefert, oder?

Vielen, vielen Dank für deine Hilfe übrigens. Ich habe langsam das Gefühl, dass es bei mir dämmert. Ich finds klasse, dass es so ein Forum und vor allem so engagierte Leute gibt.
galoisseinbruder Auf diesen Beitrag antworten »

Ein Inverses b von 7 modulo 30 muss folgende Gleichung erfüllen:
,
also nach der vorigen Überlegung ist gesucht:

Die 29 ist natürlich auch invertierbar mit einem auch ohne EEA(erweiterter euklidischer Algorithmus) auffindbarem Inversen.

zu den Nullteilern:
Schreib sie dir mal auf und schau was diese mit 30 gemeinsam haben.


P.S. Dank nehm ich, und der Rest hier auch, immer gern entgegen. Freue mich wenn´s was hilft.
Mijo Auf diesen Beitrag antworten »

Zitat:
Original von galoisseinbruder
Ein Inverses b von 7 modulo 30 muss folgende Gleichung erfüllen:
,
also nach der vorigen Überlegung ist gesucht:

Die 29 ist natürlich auch invertierbar mit einem auch ohne EEA(erweiterter euklidischer Algorithmus) auffindbarem Inversen.


Jetzt stehe ich wieder auf dem Schlauch. Warum muss b*7 kongruent 1 modulo 30 sein?
Ich denke, dass Inverse eines Element a sei b, wenn gilt: a*b = b*a = neutrales Element. Unser neutrales Element ist doch die 0 in Z.

Warum ist es b*7 kongruent 1 mod 30 und nicht b*7 kongruent 0 mod 30?

Zitat:

zu den Nullteilern:
Schreib sie dir mal auf und schau was diese mit 30 gemeinsam haben.


Ich habe es getan und lande nach wie vor bei meiner alten Aussage. Es sind die Restklassen, die miteinander multipliziert 30 oder ein Vielfaches davon ergeben.

Langsam fühle ich mich blöd...
galoisseinbruder Auf diesen Beitrag antworten »

In Ringen bezeichnet eine Einheit ein multiplikativ invertierbares Element. (das ist ja was "besonderes", additiv invertierbar sind sie alle). D.h. wann immer auch hier von Inversen gesprochen habe war multiplikativ Inverses gemeint (deswegen ja auch ggT =1)

Zitat:
Ich habe es getan und lande nach wie vor bei meiner alten Aussage. Es sind die Restklassen, die miteinander multipliziert 30 oder ein Vielfaches davon ergeben.

Das ist ja auch nicht falsch, aber verständlicher wird´s wohl in dieser Formulierung:
Eine Restklasse ist dann Nullteiler wann ein Representant (und damit alle) nicht zu 30 teilerfremd ist, sprich:
Mijo Auf diesen Beitrag antworten »

Uh, du hast ja vollkommen Recht... Natürlich ist das dann 1...

Stimmt, das klingt schon deutlich besser. Ich werde erstmal eine Nacht drüber schlafen und mich morgen mit diesem Wissen nochmal an eine ähnliche Aufgabe wagen. Wenn ich darf, werde ich meine Überlegungen zu der neuen Aufgabe dann nochmal kurz hier reinposten. Nur um sicher zu gehen, ob ich es wirklich verstanden habe.

Danke nochmals!!!
Mijo Auf diesen Beitrag antworten »

So, ich habe mich nochmal an einer anderen Aufgabe mit anderen Werten probiert. Es wäre toll, wenn ich kurz eine Rückmeldung dazu bekommen könnte. smile


1)

2)

zu 1)



zu 1)

Ich habe für alles jezt folgende Tabelle rausbekommen:



Wäre das so richtig?
galoisseinbruder Auf diesen Beitrag antworten »

Die 2) stimmt die 1) stimmt bis auf den Antwortsatz:
Hast du mal die Probe gemacht?
Wie kommst du von deiner Rechnung auf diese Antwort?
Mijo Auf diesen Beitrag antworten »

Bei der Antwort zu 1) bin ich mir noch unsicher. Mache ich die Probe für stimmt es auf jeden Fall...

Auf die Antwort bin ich durch die Musterlösung der vorherigen Aufgabe gekommen. Da hatten wir ja folgendes raus:





Also ergab sich .
In meinen Lösungen stand dazu nun folgendes:

alle x: [498, 554, 610, 666, 722, 778, 50, 106, 162, 218, 274, 330, 368, 442]

Naja, und ich hatte da geschaut, wie groß die Differenz zwischen 286 und 784 ist. Dann kam 498 raus, also eine richtige Lösung und ich dachte, dass man das jetzt ähnlich machen kann.
Ich weiß, dass diese Erklärung totaler Schrott ist, aber ich verstehe jetzt nicht, wie ich von auf die Lösungen von x komme.
galoisseinbruder Auf diesen Beitrag antworten »

Zitat:
Also ergab sich .

-286 ist eine richtige Lösung. Nur bevorzugt deine Vorlage offenbar die Darstellung einer Restklasse durch positive Zahlen. Es ist (denn die Differenz von -286 und 498 ist (ein Vielfaches) von 784).
Dagegen ist , jedoch .

Um alle Lösungen zu finden müsstest du hier etwas anders vorgehen, es ist aber nur je eine Lösung gefragt.
Mijo Auf diesen Beitrag antworten »

Ah, okay, das leuchtet ja auch ein...

Ich habe gerade nochmal eine Aufgabe ähnlicher Art gerechnet und eine kurze Nachfrage. Es geht um:



Also, ich habe den ggt(276,246) ausgerechnet:

ggt (276,246) = 6 = -8 * 276 + 9 * 246

Okay, dann das übliche:

6 = -8 * 276 + 9 * 246 | *5
30 = -40*276 + 45*246 | mod 246


Dann würde ja theoretisch -40 bzw. wenn man es positiv haben will, 206 rauskommen.

Ich habe jetzt zwei Fragen:
1. Macht es tendenziell einen Unterschied, ob da steht?

2. Wie ist das in der letzten Zeile der Rechnung mit dem . Muss ich das quasi noch durch 246 teilen und den Rest hinschreiben, oder kann ich das auch einfach so stehen lassen? Bin mir gerade etwas unsicher, weil das ja von den beiden vorherigen Aufgaben leicht abweicht.
Mijo Auf diesen Beitrag antworten »

Und eine Sache ist mir noch aufgefallen:

"Bestimmen Sie alle Einheiten von .

Gibt es einen Trick, um das schnell bei großen Zahlen zu sehen?
HAL 9000 Auf diesen Beitrag antworten »

Wenn du alle aufschreiben willst, geht das am besten mit einer Art "Sieb des Erathostenes":

Es ist , also schreibst du alle Zahlen 0,1,...,245 auf und streichst alle Vielfachen von 2, 3 und 41 raus - der Rest sind deine Einheiten.

Bleibt immer noch eine Menge übrig. Augenzwinkern
Mijo Auf diesen Beitrag antworten »

In der Tat, da bleibt immer noch ne Menge übrig. Alleine, bis man die alle Primzahlen überprüft hat...

Ich meine, für eine Klausuraufgabe finde ich das schon bisschen übertrieben. Ist ja nicht unbedingt schwer, aber kostet Zeit. Bei Z_50 oder so gehts ja noch, aber das...
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Mijo
Alleine, bis man die alle Primzahlen überprüft hat...

Also irgendwas hast du falsch verstanden: Es geht ausschließlich um die Vielfachen von 2, 3 und 41, um nichts sonst, also auch keine Primzahlüberprüfung.
Mijo Auf diesen Beitrag antworten »

Ja, stimmt irgendwie. Ich wollte jetzt anführen, dass ich ja auch die Produkte von Primzahlen testen müsste, aber die sind ja eh immer ungerade, weil Primzahlen immer ungerade sind. Bis auf die 2 natürlich. Dann muss man halt nur auf die 41 kommen...
HAL 9000 Auf diesen Beitrag antworten »

Um es nochmal klarzustellen: Es ist nicht schwer, die 80 gesuchten Zahlen zu finden, aber todlangweilig und öde, die dann alle aufzuzählen. Ich kann mir kaum vorstellen, dass einem sowas in einer Klausur zugemutet wird. Augenzwinkern
Mijo Auf diesen Beitrag antworten »

Ersterem stimme ich vollkommen zu.
Bei zweiterem muss ich dir leider sagen, dass du dich täuschst. Die Aufgabe liegt mir hier so in einer alten Klausur vor. Big Laugh
Neue Frage »
Antworten »



Verwandte Themen

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