Ringe und Restklassenringe

28.01.2012, 21:22

Mijo

Auf diesen Beitrag antworten »

Ringe und Restklassenringe

Hallo miteinander,

ich habe ein kleines Problem mit zwei Aufgaben.

1) $\begin{eqnarray*} \text{Geben Sie in } \mathbb{Z}_{784} \text{ eine Lösung von } x \cdot \overline{602}= \overline{308} \text{an}. \end{eqnarray*}$

2) $\begin{eqnarray*} \text{Bestimmen Sie alle Einheiten des Ringes } \mathbb{R}= \mathbb{Z}_{30} \text{ und geben Sie zu jeder Einheit das inverse Element an.} \end{eqnarray*}$

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:

$\begin{eqnarray*} ggt(602,784) = 14 = 10 \cdot 784 - 13 \cdot 602 \end{eqnarray*}$

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

$\begin{eqnarray*} 308 = 220 \cdot 784 - 286 \cdot 602 \end{eqnarray*}$

Mit mod784 ergibt sich folgendes:

$\begin{eqnarray*} \overline{308} = 0 - \overline{286} \cdot \overline{602}\\ \overline{308} = -\overline{172172}\\ \overline{308} = - \overline{476} \end{eqnarray*}$

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

28.01.2012, 21:50

galoisseinbruder

Auf diesen Beitrag antworten »

Hallo,

bei der 1) hast du zu weit gerechnet. Schau dir mal diese deine Zeile an:
$\begin{eqnarray*} \overline{308} = 0 - \overline{286} \cdot \overline{602} \end{eqnarray*}$
im vergleich zur Aufgabenstellung:
$\begin{eqnarray*} \text{Geben Sie in } \mathbb{Z}_{784} \text{ eine Lösung von } x \cdot \overline{602}= \overline{308} \text{an}. \end{eqnarray*}$
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?

28.01.2012, 22:04

Mijo

Auf diesen Beitrag antworten »

Hallo,
okay...
$\begin{eqnarray*} \overline{308} = 0 - \overline{286} \cdot \overline{602} \end{eqnarray*}$

Soll das bedeuten, dass $\begin{eqnarray*} - \overline{286} \end{eqnarray*}$ 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 $\begin{eqnarray*} \mathbb{Z}_{30} \end{eqnarray*}$ multipliziert mit etwas aus $\begin{eqnarray*} \mathbb{Z}_{30} \end{eqnarray*}$ ergibt 0 ?!?!

Tut mir leid, wenn ich mich total bescheuert anstelle...

28.01.2012, 22:13

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 $\begin{eqnarray*} 1=ax+by\equiv by \mod x \end{eqnarray*}$ ein Inverses zu y.

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

Zitat:

Nichts aus $\begin{eqnarray*} \mathbb{Z}_{30} \end{eqnarray*}$ multipliziert mit etwas aus $\begin{eqnarray*} \mathbb{Z}_{30} \end{eqnarray*}$ ergibt 0 ?!?!

Ich widerspreche dir da: 22 Elemente sind Nullteiler. Versuch mal ein paar und bedenke $\begin{eqnarray*} 30 \equiv 0 \mod 30 \end{eqnarray*}$

28.01.2012, 22:30

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 $\begin{eqnarray*} 1=ax+by\equiv by \mod x \end{eqnarray*}$ 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 $\begin{eqnarray*} 30 \equiv 0 \mod 30 \end{eqnarray*}$

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?

28.01.2012, 22:38

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).

Anzeige

28.01.2012, 22:52

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 $\begin{eqnarray*} 7 \equiv b mod 30 \end{eqnarray*}$ 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 $\begin{eqnarray*} 29 \equiv 29 mod 30 \end{eqnarray*}$ 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.

28.01.2012, 23:08

galoisseinbruder

Auf diesen Beitrag antworten »

Ein Inverses b von 7 modulo 30 muss folgende Gleichung erfüllen:
$\begin{eqnarray*} b\cdot 7 \equiv 1 \mod 30 \end{eqnarray*}$ ,
also nach der vorigen Überlegung ist gesucht:
$\begin{eqnarray*} 1= a \cdot 30 +b\cdot 7 \end{eqnarray*}$
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.

28.01.2012, 23:25

Mijo

Auf diesen Beitrag antworten »

Zitat:

Original von galoisseinbruder
Ein Inverses b von 7 modulo 30 muss folgende Gleichung erfüllen:
$\begin{eqnarray*} b\cdot 7 \equiv 1 \mod 30 \end{eqnarray*}$ ,
also nach der vorigen Überlegung ist gesucht:
$\begin{eqnarray*} 1= a \cdot 30 +b\cdot 7 \end{eqnarray*}$
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...

28.01.2012, 23:32

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: $\begin{eqnarray*} ggT(a,30)\neq 1 \end{eqnarray*}$

28.01.2012, 23:55

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!!!

29.01.2012, 11:44

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

smile

1) $\begin{eqnarray*} \text{Geben Sie in } \mathbb{Z}_{825} \text{ eine Lösung von } x \cdot \overline{682}= \overline{616} \text{an}. \end{eqnarray*}$

2) $\begin{eqnarray*} \text{Bestimmen Sie alle Einheiten des Ringes } \mathbb{R}= \mathbb{Z}_{16} \text{ und geben Sie zu jeder Einheit das inverse Element an.} \end{eqnarray*}$

zu 1)

$\begin{eqnarray*} ggt(682,825) = 11 = 23 \cdot 682 - 19 \cdot 825 \\ \\ 11 = 23 \cdot 682 - 19 \cdot 825 | \cdot 56 \\ \\ 616 = 1288 \cdot 682 - 1064 \cdot 825 | mod 825 \\ \\ \overline{616} = \overline{463} \cdot \overline{682} - 0 \\ \\ \text{Eine Lösung für x müsste also 362 sein.} \end{eqnarray*}$

zu 1)

Ich habe für alles jezt folgende Tabelle rausbekommen:

$\begin{eqnarray*} \begin{tabular}{ l | l | l| l| l| l| l| l| l} $x \in \mathbb{R}*$ & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 \\ \hline $x^{-1}$ & 1 & 11 & 13 & 7 & 9 & 3 & 5 & 15\\ \end{tabular} \end{eqnarray*}$

Wäre das so richtig?

29.01.2012, 12:38

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?

29.01.2012, 12:46

Mijo

Auf diesen Beitrag antworten »

Bei der Antwort zu 1) bin ich mir noch unsicher. Mache ich die Probe für $\begin{eqnarray*} \overline{463} \end{eqnarray*}$ stimmt es auf jeden Fall...

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

$\begin{eqnarray*} \text{Geben Sie in } \mathbb{Z}_{784} \text{ eine Lösung von } x \cdot \overline{602}= \overline{308} \text{an}. \end{eqnarray*}$

$\begin{eqnarray*} \overline{308} = 0 - \overline{286} \cdot \overline{602} \end{eqnarray*}$

Also ergab sich $\begin{eqnarray*} -\overline{286} \end{eqnarray*}$ .
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 $\begin{eqnarray*} \overline{286} \end{eqnarray*}$ auf die Lösungen von x komme.

29.01.2012, 13:00

galoisseinbruder

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} \text{Geben Sie in } \mathbb{Z}_{784} \text{ eine Lösung von } x \cdot \overline{602}= \overline{308} \text{an}. \end{eqnarray*}$ $\begin{eqnarray*} \overline{308} = 0 - \overline{286} \cdot \overline{602} \end{eqnarray*}$ Also ergab sich $\begin{eqnarray*} -\overline{286} \end{eqnarray*}$ .

-286 ist eine richtige Lösung. Nur bevorzugt deine Vorlage offenbar die Darstellung einer Restklasse durch positive Zahlen. Es ist $\begin{eqnarray*} -286 \equiv 498 \mod 784 \end{eqnarray*}$ (denn die Differenz von -286 und 498 ist (ein Vielfaches) von 784).
Dagegen ist $\begin{eqnarray*} 463 \not\equiv 362 \mod 825 \end{eqnarray*}$ , jedoch $\begin{eqnarray*} 463 \equiv -362 \mod 825 \end{eqnarray*}$ .

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

01.02.2012, 16:52

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:

$\begin{eqnarray*} <br /> Seien n = 246 und a = 276. \\ \\<br /> \text{Geben Sie in } \mathbb{Z}_{n} \text{ eine Lösung von } \overline{a} \cdot x = \overline{30} \text{an}. \end{eqnarray*}$

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
$\begin{eqnarray*} \overline{30}= -\overline{40} \cdot \overline{276} \end{eqnarray*}$

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 $\begin{eqnarray*} \overline{a} \cdot x = \overline{30} oder x \cdot \overline{a} = \overline{30} \end{eqnarray*}$ steht?

2. Wie ist das in der letzten Zeile der Rechnung mit dem $\begin{eqnarray*} \overline{276} \end{eqnarray*}$ . 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.

01.02.2012, 18:18

Mijo

Auf diesen Beitrag antworten »

Und eine Sache ist mir noch aufgefallen:

"Bestimmen Sie alle Einheiten von $\begin{eqnarray*} Z_{246} \end{eqnarray*}$ .

Gibt es einen Trick, um das schnell bei großen Zahlen zu sehen?

01.02.2012, 18:29

HAL 9000

Auf diesen Beitrag antworten »

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

Es ist $\begin{eqnarray*} 246 = 2\cdot 3\cdot 41 \end{eqnarray*}$ , 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

Augenzwinkern

01.02.2012, 18:34

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...

01.02.2012, 18:47

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.

01.02.2012, 18:54

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...

01.02.2012, 19:03

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

Augenzwinkern

01.02.2012, 19:06

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

Big Laugh

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »