chinesischer Restsatz

30.08.2011, 17:40

Sinnlos

Auf diesen Beitrag antworten »

chinesischer Restsatz

Meine Frage:
Hi,
Ich bin hier an einer Aufgabe und weiß gar nicht wie ich sie angehen soll.

Bestimmen Sie alle Elemente $\begin{eqnarray*} x\in Z/1111Z \end{eqnarray*}$ mit $\begin{eqnarray*} x^{2} = x \end{eqnarray*}$ .
Verwenden Sie den chinesischen Restsatz.

Meine Ideen:
Der chin. Restsatz ist für simultane Kongruenz oder Berechnung von einem Inversen klar aber hier find ich keinen Zugang

30.08.2011, 17:49

tmo

Auf diesen Beitrag antworten »

Der chin. Restsatz besagt doch $\begin{eqnarray*} \mathbb Z/1111\mathbb Z \cong \mathbb Z/11\mathbb Z \times \mathbb Z/101\mathbb Z \end{eqnarray*}$

Sei $\begin{eqnarray*} \varphi \end{eqnarray*}$ nun ein Isomorphismus zwischen diesen Ringen.

Gilt also $\begin{eqnarray*} x^2=x \end{eqnarray*}$ , so ist auch $\begin{eqnarray*} \varphi(x)^2=\varphi(x) \end{eqnarray*}$ .

Nun kann man aber $\begin{eqnarray*} \varphi(x) = (a,b) \end{eqnarray*}$ schreiben...

30.08.2011, 18:39

Sinnlos

Auf diesen Beitrag antworten »

Also muss $\begin{eqnarray*} (a,b)^{2}=(a,b) \end{eqnarray*}$ gelten
was nichts anderes ist wie $\begin{eqnarray*} (a^{2},b^{2})=(a,b) \end{eqnarray*}$

und ich muss dann die simultane Kongruenz für
$\begin{eqnarray*} x\equiv x^{2}mod11 \end{eqnarray*}$
$\begin{eqnarray*} x\equiv x^{2}mod101 \end{eqnarray*}$
lösen.
kann das sein?

30.08.2011, 18:42

tmo

Auf diesen Beitrag antworten »

Letzteres macht irgendwie wenig Sinn, aber der Anfang ist vielversprechend.

Wann nun $\begin{eqnarray*} a^2=a \end{eqnarray*}$ und $\begin{eqnarray*} b^2=b \end{eqnarray*}$ in den jeweiligen Restklassenringen mod 11 und 101 gilt, ist ganz einfach. Schließlich sind das Körper. Da hat diese Gleichung nur genau 2 Lösungen. Welche?

Und wenn es in den jeweiligen Restklassenringen je 2 Lösungen gibt, erhalten wir so durch Paarbildung insgesamt 2*2=4 Lösungen in unserm ursprünglichen Ring. Und auf die kommst du z.b. mit dem Algorithmus des chin. Restsatz.

31.08.2011, 16:59

Juppie13

Auf diesen Beitrag antworten »

a²=a gilt in Z11 ja für 11, dh 11² = 121 = 11 = 0 und analog bei 101, oder?

Welches sind dann die zwei Lösungen in dem jeweiligen Ring? Das versteh ich noch nicht so ganz...
Wie muss ich den Algorithmus des chinesischen Restsatzes denn darauf anwenden?

31.08.2011, 17:03

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von Juppie13
a²=a gilt in Z11 ja für 11, dh 11² = 121 = 11 = 0 und analog bei 101, oder?

Das stimmt zwar, aber nicht wirklich ellegant.

Wir sind doch in einem Körper. Betrachte also in einem beliebigen Körper die Gleichung $\begin{eqnarray*} a^2=a \end{eqnarray*}$ . Welche Lösungen hat die?

Anzeige

31.08.2011, 17:09

Juppie13

Auf diesen Beitrag antworten »

Also sind die beiden Lösungen 1 und 11 in Z11 und 1 und 101 in Z101?

31.08.2011, 17:10

tmo

Auf diesen Beitrag antworten »

Warum nennst du die zweite Lösung denn stur 11 und 101?

Wie wärs mit 0? verwirrt

verwirrt

31.08.2011, 17:14

Juppie13

Auf diesen Beitrag antworten »

Hmm stimmt an die hatte ich nicht gedacht, sorry wenn ich mich hier etwas blöd anstelle ... Hammer

Hammer

Wie kann ich darauf dann den chinesischen Restsatz anwenden, ich stehe hier irgendwie auf'm Schlauch.

31.08.2011, 17:18

tmo

Auf diesen Beitrag antworten »

Du weißt jetzt, dass in den beiden Körpern $\begin{eqnarray*} a^2=a \end{eqnarray*}$ und $\begin{eqnarray*} b^2=b \end{eqnarray*}$ jeweils für a=0, 1 und b=0, 1 gelöst wird.

Also sind deine Lösungen von $\begin{eqnarray*} x^2=x \end{eqnarray*}$ (was äquivalent zu $\begin{eqnarray*} (a^2,b^2)=(a,b) \end{eqnarray*}$ war) in deinem ursprünglichen Ring:

(0,0)
(0,1)
(1,0)
(1,1)

jetzt musst du diese 4 Elemente aus $\begin{eqnarray*} \mathbb Z/11 \mathbb Z \times \mathbb Z/101 \mathbb Z \end{eqnarray*}$ nur noch vermöge dem Isomorphismus, den der chin. Restsatz liefert, nach $\begin{eqnarray*} \mathbb Z/1111 \mathbb Z \end{eqnarray*}$ bringen.

Wobei dabei die Sache bei der ersten und der vierten Lösung trivial ist.

31.08.2011, 17:33

Juppie13

Auf diesen Beitrag antworten »

Der Isomorphismus is ja:

$\begin{eqnarray*} f<img src="images2/smilies/frown2.gif" border="0" alt="unglücklich" title="unglücklich" /> \mathbb Z/1111\mathbb Z) isomorph (\mathbb Z/11\mathbb Z \times \mathbb Z/101\mathbb Z) \end{eqnarray*}$
mit $\begin{eqnarray*} f(x)^2 = f(x) \end{eqnarray*}$ ,
wie du gesagt hast.
Dann ist zum Beispiel:
$\begin{eqnarray*} f(x)^2=(a,b)^2=(a,b) = (0,1) \end{eqnarray*}$

Bei (0,0) ist die Lösung 0
Bei (1,1) ist die Lösung 1,
denke ich.

Bei (0,1) ist die 1 ein Element von $\begin{eqnarray*} \mathbb Z/101\mathbb Z \end{eqnarray*}$ , aber ich weiß nicht genau wie ich das hier interpretieren soll

31.08.2011, 17:35

Juppie13

Auf diesen Beitrag antworten »

Der Isomorphismus is ja:

$\begin{eqnarray*} f: (\mathbb Z/1111\mathbb Z) \cong (\mathbb Z/11\mathbb Z \times \mathbb Z/101\mathbb Z) \end{eqnarray*}$

mit
$\begin{eqnarray*} f(x)^2 = f(x) \end{eqnarray*}$

wie du gesagt hast.
Dann ist zum Beispiel:

$\begin{eqnarray*} f(x)^2=(a,b)^2=(a,b) = (0,1) \end{eqnarray*}$

Bei (0,0) ist die Lösung 0
Bei (1,1) ist die Lösung 1,
denke ich.

Bei (0,1) ist die 1 ein Element von $\begin{eqnarray*} \mathbb Z/101\mathbb Z \end{eqnarray*}$ , aber ich weiß nicht genau wie ich das hier interpretieren soll

edit tmo: Latex verbessert. Nutze den Vorschau-Button, bevor du abschickst.

31.08.2011, 17:42

Juppie13

Auf diesen Beitrag antworten »

Tut mir leid, dass die Lösungen so furchtbar aussehen, ich kann sie nicht mehr editieren.

31.08.2011, 17:49

tmo

Auf diesen Beitrag antworten »

Wenn du das Element $\begin{eqnarray*} (1,0) \in \mathbb Z /11 \mathbb Z \times \mathbb Z /101 \mathbb Z \end{eqnarray*}$ vermöge dem Isomorphismus nach $\begin{eqnarray*} \mathbb Z / 1111 \mathbb Z \end{eqnarray*}$ bringen willst, so musst du das System

$\begin{eqnarray*} x \equiv 1 \mod {11} \end{eqnarray*}$
$\begin{eqnarray*} x \equiv 0 \mod {101} \end{eqnarray*}$

lösen.

Da kommt nun erneut der chin. Restsatz ins Spiel.

Aber ehrlich gesagt würde ich hier eher alle Vielfachen von 101 durchgehen und schauen, wann bei Div. durch 11 der Rest 1 bleibt.
Schließlich ist ja $\begin{eqnarray*} c0c \equiv 2c \mod {11} \end{eqnarray*}$ , wobei bei $\begin{eqnarray*} c0c \end{eqnarray*}$ jetzt c die Hunderstelle und die Einerstelle sein soll.

31.08.2011, 18:03

Juppie13

Auf diesen Beitrag antworten »

606 ist zum Beispiel Rest 1 mod 11, aber bräuchte ich nicht auch ein Inverses von 11 in Z/101Z?
Wieso reicht es diese Vielfachen zu suchen?

31.08.2011, 18:05

tmo

Auf diesen Beitrag antworten »

Der chin. Restsatz besagt doch dass es genau eine Lösung mod 1111 gibt.

Ob du diese nun mit dem Alogrithmus berechnest oder sie einfach "errätst" ist doch völlig egal.

31.08.2011, 18:17

Juppie13

Auf diesen Beitrag antworten »

Ist 606 also schon die Lösung zu diesem Teil?

31.08.2011, 18:18

Juppie13

Auf diesen Beitrag antworten »

Also die 6 meine ich.

31.08.2011, 18:20

tmo

Auf diesen Beitrag antworten »

Ja. Überzeuge dich doch selbst (der Windowstaschenrechner kann das ganz gut) und berechne $\begin{eqnarray*} 606^2 \mod {1111} \end{eqnarray*}$ .

Jetzt fehlt noch die Lösung, die zu (0,1) gehört. Aber das kriegst du jetzt alleine hin.

31.08.2011, 18:36

Juppie13

Auf diesen Beitrag antworten »

Ja, vielen Dank für die nette Hilfe, ich habs jetzt :-)

Freude

Freude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »